Self-Balancing Binaray Search Tree - (AVL tree, Red-Balck Tree)

Self-balancing binary search tree - Wikipedia

Self-balancing BST는 트리의 높이를 가능한 작게 유지하여 트리의 성능을 보장한다.

---

BST의 문제점

BST는 최악의 경우에서 O(N)의 시간복잡도를 가지게 된다. 해당 케이스는 바로 아래와 같다.

 

https://www.quora.com/What-is-the-worse-case-time-complexity-for-a-binary-search-tree-for-searching

모든 노드가 일렬로 자리 잡아서 이진 트리의 장점을 누리지 못하는 상태가 된 모습이다. 이진 탐색 트리의 시간 복잡도가 O(log N)이 될 수 있는 이유는 현재 노드를 기준으로 선택지의 반을 제거 해나가면서 탐색할 수 있기 때문이다. 하지만 위와 같은 케이스는 선택지 없이 전체 노드를 탐색하게 된다. 그리고 이때 전체 노드의 개수는 트리의 높이와 같다.

 

Self-Balancing BST

Self-balancing BST(자가 균형 이진 탐색 트리)는 트리의 높이를 가능한 작게 유지하는 방법으로 BST가 최악의 구성이 되는 것을 방지하여 O(log N)의 시간 복잡도를 보장한다. 

 

자가 균형 이진 탐색 트리의 구현 방법

 

1. AVL Tree

2. Red-Balck Tree

 

AVL Tree

두 자식 서브 트리의 높이를 항상 1보다 크지 않게 유지해서 균형을 유지한다.

https://en.wikipedia.org/wiki/AVL_tree#/media/File:AVL_Tree_Example.gif

 

Red-Black Tree

이진 탐색 트리가 다음과 같은 추가 조건을 가진다.

 

1. 노드는 Red or Black 중 하나의 색을 가진다.
2. 루트 노드는 Black이다.
3. 모든 leaf 노드(NIL)은 블랙이다.
4. Red 노드의 자식 노드 양쪽은 항상 모두 블랙이다.
5. 어떤 노드에서 시작해서 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다.

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#/media/File:Red-black_tree_example_with_NIL.svg

 

위 구현의 핵심은 레드 노드가 연달아 등장할 수 없고, 최단 경로는 블랙 노드로만 구성이 되어 있다. 그리고 모든 경로에서 블랙 노드의 수가 같으므로 최단 경로와 최장 경로의 길이가 최대 두 배를 넘어갈 수 없다. (최장 경로는 블랙, 레드 노드가 번갈아서 등장하므로 최단 경로가 블랙 노드 3개로만 구성된 경우, 최장 경로는 블랙 노드3 개 레드 노드 3개로 구성될 것이다.)

 

 

AVL tree, Red-Balck tree 모두 트리의 회전을 이용해서 트리의 균형을 맞춰주는 작업이 추가된다. 따라서 각 구현마다 이 회전 규칙이 포인트다.  (AVL tree가 균형을 더 엄격하게 잡는다. )

---