레드-블랙 트리

개념

각 노드에 한 비트의 color 필드가 추가로 있으며 아래 레드-블랙 특성을 모두 만족하는 이진 탐색 트리를 말한다.

레드-블랙 특성

1. 각 노드 color는 '레드'이거나 '블랙'이다.
2. 루트와 외부 노드(NIL)의 color는 블랙이다.
3. 레드 노드의 부모 노드는 반드시 블랙이다.
4. 임의의 노드 x에서 후손 리프까지 가는 경로에 있는 블랙 노드의 개수는 같다. 이것을 black-height(x)라고 한다.

 

트리의 높이

• O(log n)
• n개의 키를 가진 레드-블랙 트리 T의 높이를 h라고 하면 h ≤ 2log(n+1) 이다.
• 높이차는 최대 2배 이상 커지지 않는다.

 

연산

O(log n)

• 탐색
• 최소값 찾기
• 최대값 찾기
• 선행자
• 후행자
• 삽입, 삭제 연산

알고리즘에서 수행하는 rotation은 최대 2회이다.

 

참고

• itstory.tk/entry/%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%ACRed-black-tree