RB 트리 기본 개념 정리

RB 트리란?

• RB트리(Red-Black Tree)는 이진 탐색 트리(BST)의 일종으로서, BST의 worst case의 단점을 개선한 자료구조이다.

• 복잡한 자료구조이지만, 실 사용에서 효과적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

RB 트리의 특성

#1. 모든노드 RED / BLACK
#2. 루트노드는 BLACK
#3. 모든 NIL 노드는 BLACK
#4. 노드가 RED 면, 자녀는 BLACK (RED는 연속하면 안됨)
#5. 임의의 경로(자신을 제외)부터 **자손 NIL 까지 BLACK 개수는 동일

NIL 노드란?

NIL 노드는 RB 트리에만 존재하는 독특한 개념이다.

• NIL 노드는 존재하지 않음을 의미하는 노드

• 임의의 노드의 자식이 없을 때, 자녀를 NIL 노드로 표기한다.

• 값이 있는 노드와 동일하게 취급한다.

• 당연하게도, RB 트리에서의 leaf 노드는 NIL 노드이다.

RB 트리는 어떻게 균형을 잡을 수 있을까?

• 삽입/삭제시 #2, #4, #5 속성을 위반함. 이들을 해결하기 위해서 구조를 바꾸면, 자연스럽게 균형이 잡히게 된다.