알고리즘 분석 | AVL 트리 | 재편성(restructuring)

이전 포스팅

알고리즘 분석 | Linked Structure | 이진 탐색 알고리즘 구현

AVL알고리즘이란?

Fig. 1. AVL알고리즘

AVL 알고리즘은 자가 균형 이진 검색 트리(self-balancing binary search tree)입니다. 즉, 트리에 삽입되는 요소들이 랜덤 하게 분포하지 않을 때도 트리의 불균형을 최소화하여 검색 시간을 일정하게 유지하는 것입니다.

AVL 트리는 높이 균형을 유지하기 위해 노드 삽입 및 삭제 시 회전(rotations)을 수행합니다. 노드를 삽입하면 AVL 트리는 삽입된 노드에서 루트 노드까지 거슬러 올라가면서 노드들의 높이 차이가 1보다 크게 되는 지점을 찾아 해당 노드를 중심으로 회전합니다. 이러한 회전을 통해 높이 균형을 맞추고, AVL 트리의 불균형을 최소화합니다.

 

AVL 알고리즘의 시간 복잡도는 \(O(log n)\)으로, 이진 검색 트리의 시간 복잡도와 같습니다. 하지만 AVL 트리는 이진 검색 트리보다 검색 시간이 더 일정하며, 삽입 및 삭제 시간도 \(O(log n)\)으로 보장됩니다.

이러한 AVL 알고리즘을 이용하여 구현한 AVL 트리는 많은 애플리케이션에서 사용됩니다. 예를 들어, 데이터베이스 인덱스와 같은 대용량 데이터 처리 시스템에서 AVL 트리는 빠른 검색 속도와 데이터의 동적인 추가 및 삭제를 지원합니다

---

 

AVL 트리 삽입과 삭제

AVL트리에서 노드 삽입과 삭제를 진행하다보면 높이 차이가 1이어야 한다는 규칙을 깨고 구조가 불균형하게 되는 경우가 있습니다. 이런 경우 AVL트리는 자체적으로 재편성(restructuring)을 수행합니다. 

다음과 같은 알고리즘으로 진행이 됩니다.

1. 먼저, 노드 \(x, y, z\)를 중위 순서에 따라 좌측에서 우측으로 나열하여 \(a, b, c\)로 지정합니다. 또한, \(x, y, z\)의 서브트리 중 \(x, y, z\) 자신을 루트로 갖지 않은 4개의 서브트리를 중위 순서에 따라 좌측에서 우측으로 나열하여 \(T_0, T_1, T_2, T_3\)로 지정합니다.

2. 그 다음, \(z\)를 루트로 하는 서브트리를 새로운 루트가 \(b\)인 서브트리로 대체합니다.

3. \(b\)의 왼쪽 자식을 \(a\)로 지정하고, \(a\)의 왼쪽 서브트리를 \(T_0\)으로, 오른쪽 서브트리를 \(T1\)로 지정합니다.

4. \(b\)의 오른쪽 자식을 \(c\)로 지정하고, \(c\)의 왼쪽 서브트리를 \(T_2\)로, 오른쪽 서브트리를 \(T_3\)으로 지정합니다.

 

Fig. 2. AVL tree 불균형

다음 Fig. 2. 에서 볼 수 있듯이 불균형에는 두 가지 경우가 존재하는데,

Single rotation 과 double rotation을 볼 수 있습니다

Single rotation과 double rotation은 비슷한 개념을 가지고 있지만, 상황에 따라 다르게 적용됩니다

Single rotation은 노드의 서브트리가 한쪽으로 치우쳐진 경우에 사용되며, 해당 노드를 중심으로 왼쪽과 오른쪽 자식 노드들이 회전됩니다.

Double rotation은 노드의 서브트리가 더 복잡하게 치우쳐진 경우에 사용되며, 두 번의 회전을 통해 서브트리를 균형 잡힌 상태로 만듭니다. 따라서 Double rotation은 Single rotation에 비해 더 많은 회전 작업이 필요하며, 더 복잡한 상황에서 적용됩니다.

 

AVL 트리 삽입 예시

노드\(44\)가 루트인 다음과 같은 트리가 있습니다.

Fig. 노드 54 삽입

다음 트리를 보면 노드 \(54\) 를 삽입하게 되면서 불균형이 생기게 되고,

우리는 불균형이 생기기 시작한 \(78 = z, 50 = y, 62 = x\)이라고 지정해 줄 수 있습니다.

또한 알고리즘에 따라 왼쪽부터 \(y = a, x = b, z = c\)라고 지정해 줄 수 있고,

각각 \(z , y , x\)를 루트로 하지 않는 서브 트리 \(T_0, T_1, T_2, T_3\) 를 지정해 줬습니다

Fig. 4. 노드 54 삽입

그다음 규칙에 따라 \(z\)를 루트로 하는 서브트리를 \(b\) 서브트리로 대체해 주고, 

\(b\)의 왼쪽 자식 \(a\)에 오른쪽에는 서브트리 \(T_0\) 을 \(a\)의 왼쪽에는 \(T_1\) 을 지정하고,

\(b\)의 오른쪽 자식 \(c\)에 오른쪽에는 서브트리 \(T_2\) 를 \(c\)의 왼쪽에는 \(T_3\) 를 지정하면,

트리의 균형을 잡아 줄 수 있습니다

 

AVL트리의 삭제도 삽입과 크게 다르지 않아서 따로 설명하지는 않겠습니다

 

---

AVL 성능

AVL 트리의 성능은 다음과 같습니다:

1. 단일 재구성(restructure)은 \(O(1)\)입니다. AVL 트리의 노드가 삽입 또는 삭제될 때, AVL 트리는 회전 또는 다른 단일 재구성을 통해 균형을 유지합니다. 이러한 회전과 단일 재구성은 각각 \(O(1)\)의 시간 복잡도를 가지므로, 단일 재구성은 \(O(1)\)입니다.
2. 검색은 \(O(log n)\)입니다. AVL 트리는 이진 검색 트리이므로 검색은 노드의 수에 비례하는 높이\((log n)\)에서 수행됩니다.
3. 트리의 높이는 \(O(log n)\)입니다. AVL 트리는 균형을 유지하므로, 트리의 높이는 항상 \(O(log n)\)이 됩니다.
4. 삽입은 \(O(log n)\)입니다. AVL 트리에 노드를 삽입하려면, 먼저 이진 검색 트리에서 노드를 삽입하고, 그다음 AVL 균형을 유지하기 위해 단일 재구성을 수행합니다. 노드를 찾는 검색이 \(O(log n)\)이므로, 삽입도 \(O(log n)\)입니다.
5. 삭제는 \(O(log n)\)입니다. AVL 트리에서 노드를 삭제하려면, 먼저 이진 검색 트리에서 노드를 삭제하고, 그 다음 AVL 균형을 유지하기 위해 단일 재구성을 수행합니다. 노드를 찾는 검색이 \(O(log n)\)이므로, 삭제도 \(O(log n)\)입니다.

---