0909_rb트리란 무엇인가

RBtree란 무엇인가?

Red-Black Tree 란 ???

- self-balancing binary search tree의 일종이다.
- 각 노드당 한 비트의 추가 기억 공간을 가지는데, 이 비트는 노드의 색상 정보를 빨간색 혹은 검은색으로 저장한다.
- 루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써, 경로 중 어떤 것도 다른것보다 두 배이상 길지 않음을 보장하게 되어 근사적으로 균형을 이룬 트리가 된다.
- 트리를 self-balancing 하게 해주어 검색, 삽입, 삭제 연산을 모두 O(logn)의 시간복잡도를 보장하며, 이진 탐색 트리와 달리 최악의 경우에도 균형이 깨지지 않도록 보장한다.

RB tree의 규칙

1. 모든 노드의 색깔은 빨간색 아니면 검정색이다.
2. 루트노드는 검은색이다
3. 모든 리프노드는 검은색이다(NIL 노드를 리프 노드로 취급한다)
4. 빨간색 노드의 부모노드와 자식 노드는 모두 검정색이다
5. 어떤 노드에서 시작해서 해당 노드의 하위트리에 속한 모든 경로는 해당 노드에서부터 시작하여 리프노드까지 이동하는 모든 경로와 같은 수의 검정색 노드를 가진다


= RBT의 “균형조건”이라 한다.

NIL 노드

- rb 트리에서 리프노드는 nil노드로 표시한다.
- nil 노드는 일종의 가상 노드로서, 실제로 존재하지않는 노드이다.
- 색깔은 항상 블랙이다.
- nil노드를 트리의 리프노드들에 대한 포인터로 간주하고, 키를 가지고있는 노드들만 트리의 내부 노드로 간주한다.

nil node를 활용하는 이유

• 효율적인 메모리 사용 : 보통의 BST에서는 NULL leaf 를 사용하여 리프노드를 표현한다. 그러나 모든 리프노드가 하나의 NULL 값을 가지게 되면 메모리공간이 낭비됨. 반면에 nil node를 이용해서 모든 리프노드들이 하나의 nil node를 가리킨다면 메모리 공간을 절약할 수 있다.

RB tree 구현

• 결국 rb tree의 균형조건을 지키는 환경아래에서 새로운 노드를 추가하거나, 삭제하는 것이다.
• 구현을 하면서 포인터로 ‘가리킨다’ 라는 개념을 확실히 알게 되었다.