: 이진 탐색 트리(BST)는 조회, 삽입, 삭제시 O(logN)== O(h) == O(depth) 의 시간이 걸린다. 그런데, 운이 좋지 않아 편향된 모양을 갖게 되면 될수록 시간복잡도는 O(N)에 가까워진다. 따라서 균형잡힌 이진탐색트리를 유지하는게 좋은데, 그 중 하나로 대표적인게 RBT이다.
특징
- 자가 균형잡힌 이진트리
- 실 사용에서 효율적
- 실제로 실무에 많이 사용된다고 함.
- 항상 O(logN)
- Leaf 노드는 NIL값을 저장.
- 최소경로와 최대경로 비율이 최대 2로 유지
- Java에서 ArrayList의 경우 내부적으로 RBT로 구현되어있다고 함.
규칙
- 각 노드는 Red 혹은 Black
- Root와 Leaf 노드(NIL) 는 Black.
- 모든 Leaf 는 NIL을 자식으로 갖는다.
- Red노드의 두 자식노드는 Black이다.
- Root에서 임의의 Leaf(NIL)까지 가는 경로에서 만나는 Black 노드의 수는 같다.
- 그냥 노드의 수는 다를 수 있음.
- 이 것을 Black Height 라고 한다.
- Black height: 노드 x 로부터 노드 x 를 포함하지 않은 Leaf 까지의 simple path 상에 있는 Black 노드들의 개수
삽입
- 삽입된 노드를 Red로 지정.
- Black height 변경을 최소화하기 위해
- 삽입 결과 규칙을 위배해버리면(double red) uncle노드의 색깔에 따라 어떻게 변경할지 정책을 정함
- uncle black - Restructuring
- uncle red - Recoloring
Restructuring (이걸 rotation이라고 함)
- 나와 부모와 부모의 부모 노드를 정렬해, 가운데 노드를 Root로 만들어버림
- 다른 서브트리에 영향을 미치지 않음. 따라서, 한번의 restructuring이면 끝남. 따라서
O(1).- 그러나, 삽입 자체의 시간복잡도가 있기 때문에 전체 시간복잡도는
O(logN)
- 그러나, 삽입 자체의 시간복잡도가 있기 때문에 전체 시간복잡도는
Recoloring
- 부모와 uncle을 Black으로, 부모의 부모를 Red로 바꿔버림.
- 한번에 끝나지 않을 수도 있음.
- 이유: 위의 경우에서 부모의 부모가 전체의 root가 아니었뎐 경우에 변경 후 또 double red가 나올 가능성이 있다.
- 최악의 경우 root까지 Propagation되고, 이 때
O(log N)이 걸리게 될 듯
Reference)
https://zeddios.tistory.com/237
https://velog.io/@agugu95/%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B7%A%ED%98%95-RED-BALCKAVL
https://itstory.tk/entry/%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%ACRed-black-tree
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure