AVL 트리 (AVL Tree)

개요

AVL 트리는 Georgy Adelson-Velsky와 Evgenii Landis가 발표한 최초의 균형잡힌 이진 탐색 트리입니다. 먼저 노드의 높이를 정의하는데, 이 노드에서 잎새 노드까지 거리 중 제일 긴 것으로 정의합니다. 잎새 노드의 높이는 1이고, 자식이 있는 노드이면 자식의 높이들 중 최댓값에 1 더한 것이 되겠죠. AVL 트리는 모든 노드에 대해 왼쪽 자식과 오른쪽 자식의 높이 차이가 1 이하일 것을 요구합니다. 이 성질을 이용해 강제로 트리 높이에 제한을 둡니다. 그냥 이진 탐색 트리처럼 모든 노드가 일자로 쭉 배열되는 상황이 일어날 수 없도록 하는 거죠.

AVL 트리 또한 검색, 삽입, 삭제 연산을 가지는데 검색 연산은 이진 탐색 트리와 다를 게 없으므로 삽입과 삭제 연산에서 어떻게 트리가 자동으로 균형을 맞추는지에 관심가져 봅시다.

저번 포스트와 동일한 트리입니다. 한 가지 차이라면 노드 왼쪽에 현재 노드의 높이가 적혀있다는 점이죠. (NIL 노드의 높이는 0이지만 너무 많은 관계로 생략했습니다.) 이 트리는 AVL 트리의 조건을 아주 잘 만족하고 있습니다. 그런데 여기에 12가 추가된다면 어떨까요?

먼저 12가 추가되었습니다. 새로 추가된 노드는 자식으로 NIL 노드 두 개만을 가지기 때문에 높이가 1입니다. 그 다음부터 루트로 가면서 각 노드의 높이 정보를 업데이트해야 합니다. 업데이트를 하면 높이는 1 증가하고, 만약 업데이트한 높이가 형제의 높이와 같으면 부모부터는 업데이트가 필요 없다는 뜻이므로 거기서 끝내면 됩니다. 자, 그래서 10의 높이를 2로 업데이트합니다. 문제는 15에서 일어나는데, 15의 높이를 업데이트하려고 보니 왼쪽 자식(10)의 높이는 2인데 오른쪽 자식(NIL)의 높이는 0입니다! 이는 AVL 트리의 성질을 위반하기 때문에 트리의 구조를 바꿔주어야 합니다. 이 상황을 어떻게 해결하는지 다뤄보겠습니다.

 

재배치 (Restructuring)

위 그림에서 새로 추가된 노드가 $Z$ 또는 $Z$의 자손이라고 합시다. 그후 루트로 올라가면서 $Z$와 그 부모인 $Y$를 업데이트했고, $Y$의 부모인 $X$를 업데이트하려고 보니 $Y$와 그 형제 $B$의 높이 차이가 2입니다. (이전까지 업데이트 과정에선 이런 일이 없었다고 가정합시다. 즉, 양쪽 자식의 높이 차이가 2인 노드는 $X$가 처음.) $B$의 높이를 $h$라고 하면 $Y$의 높이는 $h+2$죠. ($Y$의 높이가 $h-2$일 수는 없습니다. 그럼 업데이트 전엔 $Y$의 높이가 $h-3$이었을 텐데, 이는 AVL 트리의 조건에 어긋납니다.) 그러면 업데이트 전 $Y$의 높이는 $h+1$일 테고 $Z$의 업데이트 전 높이와 그 형제 $A$의 높이는 $h$ 이하입니다. 그런데 $Z$가 업데이트되었으므로 $Z$의 업데이트 후 높이는 $h+1$이어야 하고 $Y$는 두 자식의 높이 차가 2가 아니므로 (위에서 균형이 안 맞는 노드는 $X$가 처음이라고 가정했습니다.) $A$의 높이는 $h$가 됩니다. 굉장히 긴데, 이걸 그려놓은 게 바로 위 그림입니다.

AVL 트리는 이 상황을 트리의 노드를 재배치하여 해결합니다. (Restructuring, 구조조정이라고 불러도 되지만 여기선 그냥 재배치 정도로 불렀습니다.) 부모-자식 관계로 묶인 $X$, $Y$, $Z$를 크기 순으로 정렬한 뒤, 양 끝을 가운데의 자식으로 넣어버리는 거죠. 이를 위 그림을 예로 들면, 셋의 크기 관계가 $Z<Y<X$이므로 $Y$를 루트로 하고 $Y$의 왼쪽 자식에 $Z$, 오른쪽 자식에 $X$를 배치합니다. 그러면 $A$와 $B$가 어디에 들어가야 하냐는 문제가 생기는데, $A$는 $Y$보다 크고 $X$보다 작으므로 $X$의 왼쪽 자식으로, $B$는 $X$보다 크므로 $X$의 오른쪽 자식으로 넣습니다.

이렇게 트리를 재구성하면 위 그림과 같은 모양이 됩니다. $Z$, $A$, $B$의 높이는 그대로고, 높이가 바뀌는 건 $X$와 $Y$로 각각 높이가 $h+1$, $h+2$가 됩니다. 결과적으로 트리의 균형이 맞춰집니다. 이 과정을 트리의 회전이라고 합니다.

왼쪽에서 오른쪽으로 가면 $X$에 대한 우회전, 오른쪽에서 왼쪽으로 가면 $Y$에 대한 좌회전이라 부릅니다. 즉, AVL 트리는 회전을 이용해 트리의 균형을 자동으로 맞춰줍니다. (이는 뒤에 설명할 레드 블랙 트리에서도 마찬가지입니다.) #GIF

이제 높이 업데이트를 어떻게 하냐가 남는데, 생각해보면 노드를 추가하기 전 $X$를 루트로 하는 서브트리의 높이는 $h+2$였는데 노드를 추가하고 우회전해서 $Y$를 루트로 하는 서브트리로 바꿔도 서브트리의 높이는 여전히 $h+2$입니다. $Y$의 부모(회전 전에는 $X$의 부모)부터는 높이가 변하지 않으니 업데이트는 여기서 끝내도 됩니다.

여기까지가 $Z<Y<X$인 경우에 대한 설명입니다. $X<Y<Z$인 경우는 좌우대칭으로, 이때는 $X$에 대해 좌회전 한 번만 해주면 균형이 맞습니다. 나머지 두 경우는 $Y<Z<X$와 $X<Z<Y$이고 좌우대칭이기 때문에 $Y<Z<X$만 설명하겠습니다.

가정은 똑같습니다. 새로 추가된 노드는 $Z$ 또는 그 자손이고, $X$를 업데이트하려고 보니 $Y$와 $D$의 높이 차이가 2만큼 나는 상황입니다. 이때 AVL 트리는 마찬가지로 $X$, $Y$, $Z$를 크기순으로 나열하고 가운데인 $Z$를 루트로 만든 뒤 제일 작은 $Y$는 $Z$에 왼쪽에, 제일 큰 $X$는 $Z$의 오른쪽에 배치합니다. 마지막으로 나머지 $A$, $B$, $C$, $D$도 잘 연결해주면 오른쪽 그림이 됩니다. 이렇게 재배치하면 균형이 맞냐고요? 세 가지 경우로 나눠봅시다.

  1. 새로 삽입한 노드가 $Z$인 경우: $h=0$이고, $A$, $B$, $C$, $D$ 모두 NIL 노드가 됩니다.
  2. 새로 삽입한 노드가 $B$ 또는 그 자손인 경우: $Z$의 업데이트 후 높이가 $h+1$이므로 $B$의 업데이트 후 높이는 $h$, $C$의 높이는 $h-1$입니다. ($Y$, $Z$, $A$의 관계가 $Z$, $B$, $C$의 관계와 똑같습니다.)
  3. 새로 삽입한 노드가 $C$ 또는 그 자손인 경우: 2번과 정반대입니다. $B$의 높이는 $h-1$, $C$의 업데이트 후 높이는 $h$가 됩니다.

따라서 어느 경우든 오른쪽 그림에서 균형이 잘 맞습니다.

이 재배치 방법은 두 번의 회전을 필요로 합니다. 첫 번째로 $Y$에 대해 좌회전을 하고 두 번째로 $Z$에 대해 우회전을 합니다.

정리하자면 다음과 같습니다.

  1. 노드를 삽입하고, 루트로 올라가면서 높이를 업데이트 합니다.
  2. 업데이트하려는 노드의 양쪽 자식의 높이 차이가 2가 된다면, 이 노드를 $X$라 하고 $X$의 두 자식 중 높이가 큰 쪽을 $Y$, $Y$의 두 자식 중 높이가 큰 쪽을 $Z$라고 합니다.
  3. $X$, $Y$, $Z$를 대소관계에 따라 잘 재배치합니다. 이후 높이 업데이트는 없습니다.

 

이제 제일 처음 예시로 돌아가봅시다. 현재 15의 양쪽 자식이 균형이 맞지 않으니 $X=15$, $Y=10$, $Z=12$이고, 그러므로 두 번 회전을 해서 12 밑에 10과 15가 오도록 재배치합니다.

이번엔 9를 넣어봅시다.

 

높이를 업데이트하면 4의 양쪽 자식의 높이 차이가 2가 납니다. $X=4$, $Y=8$, $Z=12$이고 한 번 회전하여 8을 루트 노드로 만들어 줍니다.

삭제도 비슷합니다. 이진 탐색 트리와 동일하지만 추가적으로 높이 업데이트와 회전을 해주면 됩니다. 12를 지운다고 하면 12 자리에 15를 넣고 제일 오른쪽 15를 지우면 되죠. 이를 지우면 그 부모인 15(원래는 12)의 양쪽 자식의 높이 차이가 2가 되므로 오른쪽으로 한 번 회전해주면 됩니다. $X$, $Y$, $Z$는 삽입과 동일한 방법으로 구합니다.

 

시간 복잡도

먼저 AVL 트리는 정말로 높이가 제한되는지 봅시다. 트리 높이가 제한되지 않는다면 쓸 이유가 없죠. 전체 높이가 $h$인 AVL 트리에 들어갈 수 있는 노드 개수의 최솟값을 $T(h)$라고 하면 다음이 아주 자명하게 성립합니다.

\[
\begin{align*}
T(1) &= 1 \\
T(2) &= 2 \\
T(h) &= T(h-1) + 1 + T(h-2), \qquad h \ge 3
\end{align*}
\]

여기서 $T(h) \ge 2^{h/2-1}$이라는 사실을 수학적 귀납법으로 증명할 수 있습니다.

  1. $h=1, 2$일 때 성립합니다.
  2. $h=k, k+1$일 때 성립한다고 하면 ($k \ge 1$)
    \[T(k+2)=T(k+1)+1+T(k) \ge 2^{(k+1)/2-1}+1+2^{k/2-1} \ge 2\cdot 2^{k/2-1} = 2^{(k+2)/2-1}\]
    이므로 $h=k+2$일 때에도 성립합니다.

높이 $h$인 AVL 트리에 들어갈 수 있는 노드의 개수 $n$은 정의에 의해 $T(h)$ 이상이므로

\[ n \ge T(h) \ge 2^{h/2-1} \]

\[ \therefore h \le 2 \log{n} + 2 \]

따라서 $h=O(\log n)$입니다. 그렇다면 검색의 시간 복잡도는 확실히 $O(h)=O(\log n)$이고, 삽입과 삭제의 시간 복잡도를 구해야 합니다. 회전 연산은 $O(1)$의 시간이 걸리기 때문에 삽입과 삭제의 시간 복잡도는 노드 찾는 것이 $O(h)$, 높이 업데이트가 $O(h)$, 필요할 경우 최대 두 번 회전하는 데 $O(1)$이 필요하여 총 $O(h)=O(\log n)$이 됩니다. 즉, AVL 트리는 이진 탐색 트리를 보완하는 데 성공했습니다!

남은 것은 구현인데… 복잡합니다.