Self-balancing Binary Search Tree 요약

석형원·2024년 10월 9일

BST 자료구조

📕 Binary Search Tree란?

정의하자면,

"Linked List로 Binary Tree를 만들어 삽입과 삭제를 용이하게 하고, Binary Search의 탐색 방식을 사용하여 효율적으로 탐색하는 자료구조" 입니다.

Binary Search 방식을 사용하기 때문에 정렬이 되어있어야합니다.

Left subtree는 현재 노드보다 값이 작은 것
Right subtree는 현재 노드보다 값이 큰 것들만 가질 수 있습니다.

📃 Binary Tree 유형

Binary Tree란?
모든 노드들이 둘 이하의 자식을 가진 트리
Full Binary Tree란?
모든 노드가 0 혹은 2개의 자식을 가진 트리
Complete Binary Tree (완전이진트리)란?
가장 깊은 depth를 제외한 모든 구간이 완전히 채워져 있는 Binary Tree로,
노드가 반드시 왼쪽에서 오른쪽으로 채워져야 합니다.
Perfect Binary Tree (포화이진트리)란?
모든 내부 노드가 2개의 자식을 갖으며,
모든 leaf 노드가 동일한 depth를 갖습니다.

=> perfect binary tree는 가장 깊은 depth의 노드들은 자식이 없고, 다른 모든 node들은 두 개의 자식을 가집니다.

📃 Binary Search(이진 탐색, 이분 탐색)란?

정렬되어 있는 데이터에서 탐색 범위를 계속해서 반으로 나누어 범위를 좁혀가는 방식입니다.
( 정렬된 구조에서만 사용 가능 )

Binary Search의 시간 복잡도는 O(log N)입니다.

Binary Search Tree의 시간복잡도

Linked List의 삽입, 삭제는 O(1)지만,
탐색은 O(N)로 상대적으로 오래걸립니다.

이 탐색 시간을 줄이기 위해,
Linked List로 만든 Binary Tree 위에
Binary Search 방식으로 탐색을 할 수 있게 만든다면,

탐색
- Tree가 Balanced할 때 : O(log N)
- Tree가 Balanced하지 않을 때 : 최대 O(N)
  
  탐색 방식이 루트 노드에서 depth를 따라 내려가기 때문에 높이를 h라고 한다면 O(h)의 시간이 걸리게 됩니다.
  
  여기서, Tree가 Balanced하다면 최소 높이를 가지게 되기 때문에 O(log N)이 되는 것이고,
  
  Tree가 Balanced하지 않다면 최대 높이를 가지게 되는 것이기 때문에 높이는 N, 즉 O(N)이 되는 것입니다.
삽입, 삭제
- O(log N) ~ O(N)
  
  노드를 삽입, 삭제하는 행위 자체는 O(1)에 불과하지만, 삽입 혹은 삽입을 위해 노드를 탐색하는 과정이 필요하므로 O(log N) ~ O(N)이라고 할 수 있습니다.

📕 Balanced Binary Search Tree

Balanced BST는 Height Balanced Tree로도 불립니다.

정의하자면,

Left Subtree와 Right Subtree의 높이 차이가 m이하인 Binary Tree를 뜻합니다.

여기서 m은 일반적으로 1을 의미합니다.

높이 차이가 1이하인 Binary Tree라는 것은 한쪽으로 편향되지 않고 골고루 노드가 분산된 형태라고 볼 수 있습니다.

Balanced Binary Search Tree의 시간복잡도

균형을 이루고 있기에 탐색에 대한 시간복잡도는 항상 O(log N)입니다.

📕 Self-balancing Binary Search Tree

Balanced Binary Search Tree와 형태가 동일하지만,
노드가 삽입 혹은 삭제될 때 높이를 최소화하는 방향으로 스스로 구조를 변경하여 균형을 유지하는 트리입니다.

그 예로는 AVL Tree, Red Black Tree가 있습니다.

탐색 뿐 아니라 삽입, 삭제로 인한 불균형 상태에서 균형 상태로 노드들을 재연결하는 과정도 모두 O(log N)입니다.

삽입, 삭제 자체에 대한 시간복잡도는 O(1) + 삽입, 삭제 위치까지 탐색하는 시간복잡도 O(log N) + 불균형을 확인하러 Root까지 탐색하는 시간 O(log N) + re-balancing 하는 시간 O(1) or O(log N)
=> O(log N)

📃 AVL Tree

AVL Tree는 Self-balancing Binary Search Tree로,

"Left Subtree의 높이 - Right Subtree의 높이를 뺀 값"인 Balance Factor(BF)라는 값을 사용합니다.

BF가 (-1,0,1)이면 균형을 유지하고 있다고 판단하고, 그외의 값이면 불균형이라 판단하여

삽입 혹은 삭제로 인해 불균형 상태가 됐을 때, Rotation을 통해 트리를 균형 상태로 만들어줍니다.

불균형 상태의 종류는 LL, RR, LR, RR 총 4가지 형태가 존재합니다.

불균형 상태에 대한 판단은 삽입 혹은 삭제 시 해당 노드의 위치부터 루트 노드로 따라 올라가며 BF를 측정하여 불균형 여부를 검사합니다.

기본적으로 루트와 해당 노드까지의 경로 내 노드들의 높이만 바뀌므로, 노드마다 높이를 캐싱하면 효율적인 계산이 가능합니다.

( Rotation에 대해 정리가 잘 된 포스팅 : https://yoongrammer.tistory.com/72 )

AVL Tree의 Re-balancing 시간 복잡도 : O(log N)

AVL Tree는 height 혹은 Balance Factor 값을 노드 별로 가지고 있어야합니다. (공간 소모)

📃 Red Black Tree

Red Black Tree는 균형을 유지하기 위해 Red와 Black 두 가지 색상을 이용합니다.

그리고 특수한 속성을 통해 자가 균형을 유지합니다.

모든 노드는 Red or Black

Root node와 NIL node들은 항상 Black

Red node의 자식은 항상 Black

Black node의 자식은 모두 포함

모든 Leaf node에 대해 Root node까지의 경로에 존재하는 Black node의 숫자는 모두 같습니다.

여기서 NIL node(Leaf node)란? :
- Red Black Tree에서 자식 노드가 존재하지 않을 경우, NIL node라는 특수 노드가 있다고 가정합니다.
- 따라서, 모든 leaf node는 NIL node가 됩니다.
- 이 NIL node는 key나 data를 포함하지 않고 실제 코드에서도 구현되지 않습니다.

이제 삽입 혹은 삭제로 인해 불균형 상태가 된다면,
위 속성을 만족시키기 위해

삽입의 경우 : Restructing 혹은 Recoloring을 진행해줍니다.

Restructing :
삽입된 노드를 자식이라 했을 때, 그 부모와 조부모 노드를 오름차순으로 정렬하여 가운데 값을 부모로 만들고 나머지를 자식으로 만들어 해당 서브트리를 재구성합니다.
( 부모 : Black, 자식 : Red )
Recoloring :
- 삽입된 노드 기준 삼촌 노드가 Red일 때 사용 가능한 스킬입니다.
- 부모와 삼촌을 Black으로 조부모를 Red로 색을 변경합니다.
- 만약 Double Red 상황이 발생한다면, 그 위로 Recoloring 과정을 반복하고 마지막에 루트 노드가 Red가 되면 Black으로 색을 변경해주며 종료합니다.

( 정리가 잘 된 포스팅 : https://suhwanc.tistory.com/197 )

삭제의 경우 : Binary Search Tree와 동일한 방식으로 삭제 후 Re-balancing

삭제 자체는 일반적인 BST와 동일합니다.

삭제할 노드의 자식이 둘인 경우 :
successor 혹은 Predecessor와 값을 교환한 후 그 위치의 노드를 삭제합니다.
( 노드의 값만 교환했으므로, 노드의 색은 유지됩니다. 소실된 건 기존 successor의 색 )
삭제할 노드의 자식이 하나인 경우 :
대상 노드의 부모와 대상 노드의 자식을 연결 후 대상 노드를 삭제합니다.
( 대상 노드를 삭제한 것이므로, 소실된 건 대상 노드의 색 )
삭제할 노드의 자식이 없는 경우 :
대상 노드를 삭제합니다.

여기서 삭제된 색을 기준으로, Black을 삭제하게되면 특수한 상황을 제외하고 속성 5번을 어기게되는 Doubly Black이 발생하게됩니다.

이 Doubly Black을 해소시키는 방법엔 총 4가지 case가 있는데, 이는 아래 포스팅들에서 잘 정리되어있기에 첨부했습니다.