[자료구조] 4-5. 레드-블랙 트리(Red Black Tree)

레드-블랙 트리는 스스로 균형을 잡는 자가 균형 이진 탐색 트리(Self - Balancing Binary Search Tree)이다.

[그림1] 레드-블랙 트리.

레드-블랙 트리에는 다음과 같은 조건들이 있다:

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 리프 노드(NIL : Null Leaf)는 검은색이다.
4. 빨간 노드의 자식 노드는 검은색이다(No Double Red, 빨간 노드가 연속으로 있을 수 없다)
5. 어떤 노드에서 리프 노드까지 가는 검은 노드의 개수는 같다.
   + 레드-블랙 트리에서, 어떤 노드의 두 자녀가 같은 색이면 부모와 두 자녀의 색을 바꿔도 5번 규칙이 성립된다.
   ++ 추가되는 노드는 무조건 빨간색 노드이다. 5번 규칙을 충족시키기 위해서이다.

 

 

레드-블랙 트리의 높이

 

레드-블랙 트리의 높이 중에는 Black height라는게 있다.

자기 자신을 제외하고, 리프 노드까지의 검은 노드의 수를 말한다.

한 노드에서 어느 리프 노드까지 내려가도 같은 높이이다.(5번 규칙)

 

 

다음 글에서는 레드-블랙 트리의 삽입과 삭제에 대해서 알아보겠다.