[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)

이진 탐색 트리 (BST, Binary Search Tree)

이진탐색트리는 저장과 동시에 정렬하는 트리입니다. 어느 노드를 선택하든 해당 노드의 left subtree에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 노드의 right subtree에는 그 노드의 값보다 큰 값들을 지닌 노드들로만 이루어져 있습니다.

 

이진 탐색 트리의 데이터 저장 규칙

규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

 

시간복잡도

검색, 저장, 삭제 : O(log N)

최악의 경우에 트리가 한쪽으로 치우쳐져있다면 O(n) 이다. 이런 경우를 편향 트리라고 한다. 편향 트리 링크드 리스트와 다를바가 없어지므로, 탐색 시에 O(log N)이 아니라 O(n)이 된다.

 

이진 탐색 트리의 최악의 경우 시간복잡도가 O(n)인데, 이를 해결하는 방법은?

자가 균형 이진 탐색 트리를 사용하면 됩니다.

자가 균형 이진 탐색 트리(Self-Balancing BST)는 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지하여, 높이를 가능한 낮게 유지하는 트리입니다. 대표적인 균형 이진 트리로는 AVL 트리와 Red-black Tree, Map 이 있습니다.

 

이러한 트리의 균형을 잡기 위해 트리 구조를 재조정하는 것을 Rebalancing 이라고 합니다.

 

이진 트리란 무엇인가요?

모든 노드의 자식 노드 개수가 2 이하인 트리를 이진 트리라고 합니다.

즉, 루트 노드를 중심으로 두 개의 서브트리로 나뉘어지며, 나뉘어진 두 서브 트리도 모두 이진 트리인 자료구조를 말합니다.

 

포화 이진 트리(Perfect Binary Tree) : 모든 레벨이 꽉 찬 이진 트리

완전 이진 트리(Complete Binary Tree) : 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리

정 이진 트리(Full Binary Tree) : 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리

 

AVL 트리

AVL 트리는 스스로 균형을 잡는 자가 균형 이진 탐색 트리입니다. 한쪽으로 치우처진 편향 이진 트리가 되면, 트리의 높이가 높아져 검색 시 O(N)의 시간복잡도를 가지므로, 이를 방지하기 위해 트리의 균형을 유지하는 AVL 트리를 사용하게 됩니다.

 

특징

AVL 트리는 이진 탐색 트리의 속성을 가져 왼쪽, 오른쪽 서브트리의 높이 차이가 최대 1 입니다. 만약, 어떤 시점에서 높이 차이가 1보다 커지면 회전을 통해 균형을 잡아 높이 차이를 다시 줄입니다. 이러한 AVL 트리는 높이를 log N으로 유지하기 때문에 삽입, 삭제, 검색의 시간복잡도는 O(log N)이 됩니다.

 

Balance Factor(BF)

AVL 트리의 높이는 Balance Factor(균형인자)를 통해 구합니다. Balance Factor는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값으로 구합니다.

AVL 트리에서는 모든 노드의 균형인자가 -1, 0, +1 임을 보장합니다.

 

회전

검색 및 순회 연산은 BF를 변경하진 않지만, 삽입/삭제에서는 BF가 변경될 수 있습니다. 삽입/삭제 시에 BF가 -1, 0, 1이 아닌 경우 즉, 불균형 상태가 되는 경우엔 불균형 노드를 기준으로 서브트리의 위치를 변경하는 회전 작업을 수행하여 트리의 균형을 맞추게 됩니다.

 

노드들의 배열에 따라 왼쪽 회전(LL), 오른쪽 회전(RR), 왼쪽-오른쪽 회전(LR), 오른쪽-왼쪽 회전(RL)의 4가지 불균형이 발생할 수 있으며 각 상황마다 회전 방향을 달리하여 균형을 맞춥니다.

 

Red-Black 트리

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

 

레드블랙 트리는 자가 균형 이진 트리입니다. 모든 노드는 빨간색 혹은 검은색으로 이루어져있고 노드의 특징마다 색상이 결정됩니다.

 

레드블랙 트리는 루트노드부터 리프노드까지의 모든 경로 중, 최소 경로와 최대 경로의 크기 비율이 2보다 크지 않습니다. 이러한 상태를 Balanced 상태라고 합니다.

 

(참고: 해시 맵에서의 Separate Chaining 방식에서도 레드블랙 트리가 사용된다)

 

노트 색상 결정 방법

1. 루트 노드와 모든 리프 노드는 검은색입니다.

2. 빨간색 노드의 자식은 검은색입니다.

    즉, 빨간색 노드가 연속으로 나올 수 없습니다. (빨간색이 연속으로 나오면 Double Red 문제)

3. 모든 리프노드에서 Black Depth는 같습니다.

    즉, 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수는 모두 같습니다.

 

> 리프노드

리프노드 : 자료를 갖지 않고 트리의 끝을 나타내는 노드

 

Double Red 문제

레드블랙 트리에 새로운 노드를 삽입할 때는 항상 빨간색으로 삽입합니다. 만약 이때 Double Red가 발생하면 이러한 문제를 해결하기 위해 Restructuring과 Recoloring 전략을 사용합니다.

 

새로 삽입되는 노드의 부모 노드 중, 형제노드가 존재한다면 해당 노드를 '삼촌 노드'라고 하고, 삼촌 노드가 빨간색이라면 Recoloring을, 삼촌 노드가 검은색이라면 Restructuring을 수행하면 된다.

 

Restructuring

1. 새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬한다.
2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고, 나머지 자식들을 빨간색으로 만든다.

 

Recoloring

1. 새로운 노드의 부모와 삼촌을 검은색으로 바꾸고, 조상을 빨간색으로 바꾼다.
    1-1. 조상이 루트노드라면 검은색으로 또 바꾼다.
    1-2. 조상을 빨간색으로 바꿨을 때 Double Red가 발생하면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

---

https://yoongrammer.tistory.com/72

[자료구조] AVL 트리(Tree)

https://code-lab1.tistory.com/62

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기