[자료구조] Red Black Tree

Red Blacke Tree는 Binary Search Tree(이진 탐색 트리)에서 skewed tree(편향된 트리) 한마디로 균형이 잡히지 않고 한쪽으로만 노드가 다 몰리게 되면 시간복잡도가 O(n)이 되는데 이러한 점을 해결하기 위해 나왔다.

 

=> 이 트리는 search , insert, delete 모두 O(log n)의 시간 복잡도를 가진다. 

 

Red Black Tree의 특징

1. 이 트리의 노드들은 모두 red이거나 black이다.

2. Root 노드와 leaf노드들은 black 이다.

3. 만약 노드가 red이면 그 노드들의 child노드들은 모두 black이다.

4. 자식노드가 없는 노드의 경우(leaf node)를 Nil 노드라고 부른다.

5. 한 노드에서 nil노드까지 갈때 나오는 Black 노드의 개수는 같다. 

6. 모든 노드들은 black height이 있다.

Black Height => Root 노드에서 Nil노드까지 갈때 나오는 Black노드의 갯수

 

 

 

그 외의 특징

- 노드들은  색을 보관하기 위한 1 bit공간이 필요하다.

- root node에서 nil node까지 가장 긴 경로와  가장 짧은 경로는 2배 밑으로 차이난다.

 

즉, 가장 짧은경로: 다 black node 

      가장 긴 경로: black & red 섞여있음

 

참고자료

https://www.youtube.com/watch?v=qvZGUFHWChY&t=125s

https://velog.io/@ehehdgus11/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Red-Black-Tree-1