이전에 구현한 이진 트리는 일반적인 경우 어떠한 값을 찾는데 걸리는 시간이 O(logN)이다. 하지만 최악의 경우에 O(N)이 된다.
이때 최악의 경우는 이진 탐색 트리가 하나의 방향으로만 이어져 있는 경우로 다음과 같은 사진으로 확인할 수 있다.
편향 트리의 한 모습
이 경우 1을 찾기 위해서는 좌측으로만 편향된 모든 노드를 거쳐 들어가야하기 때문에 O(N)이 걸리게 된다. 이러한 구조는 좋지 않다. 이러한 구조를 미연에 방지하여 트리가 자동으로 균형을 잡아주는 트리를 AVL(Adelson - Velsky - Landis)트리 라고 한다.
이때 균형이 깨졌다는 것은 어떻게 판단할 것인가를 생각해볼 수 있다. 균형의 판단은 다음과 같이 이루어진다.
어떤 노드의 높이는 그 노드의 좌측 서브트리의 높이와 우측 서브트리의 높이 중 더 큰 트리의 높이 + 1로 정의된다.
이때 어떤 노드의 균형 상태는 그 노드의 좌측 서브트리의 높이 - 우측 서브트리의 높이로 정의되며 이 값이 -1, 0, 1인 경우 "균형잡혀 있다" 라고 한다. 즉 균형 상태가 -1보다 작거나 1보다 크다면 균형이 깨져있는 상태가 된다.
이번에는 이런 균형이 깨져있는 상태에 대해 AVL트리가 어떻게 균형을 다시 맞추는지에 대해 살펴본다.
자가 수복 연산 - LL 회전 연산
아래와 같은 트리가 존재한다고 가정하자
LL(left left)트리의 한 종류
해당 트리는 좌측으로 두 자식이 연달아 존재한다. 이때 루트의 벨런스는 2 - 0으로 2가 되며 벨런스 수치가 1보다 크므로 균형이 깨져있는 상태이다. 이때 사용하는 연산이 LL 회전 연산이다.
이름에서 알 수 있듯이 이는 트리의 두 노드를 회전시키는 것이며 위 트리에서 LL회전 연산의 대상은 루트노드 10과 그 좌측 자식 5이다.
LL 회전 연산의 회전 영역
LL 회전 연산은 해당 회전 영역에 대하여 "우측"으로 회전시킨다. 위 사진에서 LL 회전 연산의 결과는 다음과 같다.
LL 회전의 결과
회전 이후 루트 노드는 5로 변경되며 회전이 수행된 노드들의 높이 값이 재계산된다. 편향된 트리가 다시 안정화된것을 확인할 수 있다.
자가 수복 연산 - RR 회전 연산
RR은 우측으로 편향된 트리에 대한 회전 연산이다. 예시로 아래와 같은 트리가 존재한다고 가정한다.
우측 편향 트리의 일종
위 상태에서 루트 노드의 벨런스 상태는 0 - 2 = -2로 -1보다 작으므로 벨런스가 깨져있다.
해당 편향 트리를 정상으로 되돌리기 위해서는 cur와 cur.right를 좌측으로 회전시켜야 한다.
RR 회전 연산의 영역
회전의 원리는 이전에 보았던 LL 회전 연산과 다른게 없으며 오직 회전 방향만 차이가 있다.
RR 회전 연산이 수행된 트리
회전 이후 LL 회전 연산과 동일하게 회전이 수행된 노드들에 대해 높이가 재계산되며 루트 노드는 20이 된다.
자가 수복 연산 - LR 회전 연산
LR 연산은 다음과 같은 트리의 상태일 때 적용되는 연산이다.
LR 회전 연산이 적용될 트리
위 상태에서 루트 노드의 벨런스 상태는 2 - 0으로 2가 되며 1보다 크므로 벨런스가 깨져 있다.
해당 트리의 구조를 정상화 시키기 위해서는 우선 트리의 구조를 LL 또는 RR 연산이 되도록 먼저 조정해줄 필요가 있다.
여기서 cur.left와 그 우측 자식을 보자. 이 둘을 RR 회전을 시킨다면 10 - 7 - 5로 LL 회전 연산을 할 수 있어 보인다.
첫 번째 회전의 회전영역
여기서 루트 노드인 10은 생각하지 않고 5와 7만 좌측회전 즉 RR회전 연산을 적용해보자
그럼 트리가 다음과 같이 변경된다.
회전한 이후의 결과
회전한 이후의 트리는 LL 회전 연산을 적용시킬 수 있어 보인다.
LL 회전 연산 영역
위에서 봤던 LL 회전 연산을 회전 영역에 대해 적용한다.
LL 회전 연산 결과
연산의 결과 7을 루트로 하여 균형이 맞춰진 트리가 나온다.
자가 수복 연산 - RL 회전 연산
RL 회전 연산은 다음과 같은 트리에서 적용될 수 있는 연산이다.
RL 회전 연산이 적용될 트리
위에 LR 연산에도 보았듯 우선 트리의 구조를 LL 또는 RR 연산을 하기 적합하도록 만들어야 할 필요가 있다.
여기에서 cur.right와 그 좌측 자식을 LL 연산을 통해 우측 회전을 시키면 10 - 15 - 20의 구조로 RR 연산을 적용시킬 수 있어 보인다.
20, 15노드에 대해 LL연산을 적용한 모습
회전 연산을 통해 얻어진 트리를 다시 RR 연산으로 좌측으로 회전시킨다.
두 번째 회전의 회전 영역회전 영역에 대해 RR 회전 연산을 수행한 결과
연산 결과 15를 루트로 하여 균형이 맞춰진 트리가 완성되었다.
정리
균형이 깨진 트리에 대해 AVL트리에서 어떤 연산을 통해 균형을 복구하는지에 대해 그 원리를 알아보았다.
