이 섹션에서는 Red-Black Tree가 무엇인지 볼 것입니다. Red-Black Tree는 자체 균형 이진 탐색 트리입니다. 각 노드에는 몇 가지 조건이 있습니다. 다음과 같습니다 -
-
각 노드에는 색상이 있습니다. 빨강 또는 검정
-
루트는 항상 검은색입니다.
-
인접한 두 개의 레드 노드가 없습니다.
-
노드(루트 포함)에서 하위 NULL 노드까지의 모든 경로에는 동일한 수의 블랙 노드가 있습니다.
적흑나무의 예
잎에 널 노드가 있는 레드-블랙 트리
AVL 트리와의 비교
AVL 트리는 Red-Black 트리보다 더 균형이 잡혀 있습니다. 그러나 주요 단점은 삽입 및 삭제 중에 더 많은 회전이 있다는 것입니다. 다중 삽입 및 삭제의 경우 Red-Black 트리가 도움이 됩니다.