AVL tree
27 Oct 2017 | Binary Search Tree
이번 글에서는 AVL 트리에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고하였습니다. 그럼 시작하겠습니다.
concepts
AVL 트리란 서브트리의 높이를 적절하게 제어해 전체 트리가 어느 한쪽으로 늘어지지 않도록 한 이진탐색트리(Binary Search Tree)의 일종입니다. 트리의 높이가 $h$일 때 이진탐색트리의 계산복잡성은 $O(h)$이기 때문에 균형된 트리를 만들어 $h$를 줄이고자 하는 발상에서 비롯됐습니다.
AVL 트리의 핵심 개념 가운데 하나가 Balance Factor(BF)입니다. 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 것입니다. 두 서브트리의 높이가 같거나 잎새노드라면 BF는 0입니다(empty tree의 BF는 -1로 정의). 다음 그림을 보겠습니다.
위 이진탐색트리의 루트노드의 BF는 -1입니다. 왼쪽 서브트리의 높이는 1, 오른쪽은 2이기 때문입니다. 9의 BF는 1입니다. 9의 왼쪽 서브트리의 높이는 1, 오른쪽 서브트리는 존재하지 않아 0이기 때문입니다. 잎새노드인 3, 5, 7은 서브트리가 전혀 없기 때문에 BF는 0이 됩니다. BF가 클 수록 불균형 트리라고 할 수 있겠습니다.
AVL 트리는 요소를 삽입(insert)하거나 삭제(delete)하는 과정에서 서브트리를 재구성해 트리 전체의 균형을 맞춥니다. 삽입/삭제 연산시 BF가 일정 값 이상(보통 2) 혹은 이하(-2)로 바뀐 노드를 기준으로 그 서브트리들의 위치를 rotation하는 방식을 취합니다. rotation에는 두 가지 방식이 있는데 삽입 연산을 중심으로 살펴 보겠습니다.
single rotation
삽입 연산시 single rotation은 다음과 같은 방식으로 수행합니다. $U$는 주어진 이진탐색트리의 루트노드, $V$는 $U$의 왼쪽 자식노드, $Z$는 $U$의 오른쪽 서브트리입니다. $X$와 $Y$는 각각 $V$의 왼쪽, 오른쪽 서브트리를 가리킵니다. $X$, $Y$, $Z$의 높이가 모두 $h$라고 가정해 보겠습니다. 여기에서 $X$에 새로운 요소를 하나 추가해 보겠습니다. 이 경우 $V$와 $U$의 BF는 각각 1, 2가 됩니다.
$U$는 ‘BF가 2 이상, 2 이하일 때 rotation을 실시한다’는 조건에 부합합니다. $U$의 왼쪽 자식노드인 $V$를 기준으로 single rotation을 아래와 같이 실시해 줍니다. 기존 트리 구조에서 $Z$를 잡아 당겨 내려서 $V$를 새로운 루트노드로 만드는 겁니다. 요소 하나가 추가된 $X$의 높이만 $h+1$이고 나머지는 모두 $h$인 점을 감안하면 rotation 실시 후의 $U$, $V$의 BF는 각각 0, 0이 되어 균형 트리를 이룹니다.
single rotation을 일반화한 그림은 다음과 같습니다.
요소 하나 추가하는 데 이렇게까지 복잡하게 할 필요가 있을까 싶기도 합니다. 하지만 AVL 트리는 기본적으로 이진탐색트리라는 점에 유의해야 합니다. 삽입 연산을 수행하더라도, 부모노드는 왼쪽 자식노드보다 크거나 같고, 오른쪽 자식노드보다는 작거나 같다는 성질이 깨지지 않도록 해야 한다는 이야기입니다.
구체적인 예를 들어 볼까요. 아래 트리에서 0.8을 삽입해 보겠습니다. 0.8은 5보다 작으므로 3과 비교하고, 3보다 작으므로 1과 비교하고, 1보다 작고 1의 자식노드가 없습니다. 따라서 0.8이 들어갈 위치는 1의 왼쪽 자식노드가 됩니다. 기존의 이진탐색트리라면 여기에서 삽입 연산을 마칩니다.
하지만 서브트리 $X$에 0.8이 추가되면서 $V$와 $U$의 BF는 각각 1, 2이 됐습니다. $V$를 기준으로 rotation을 해줍니다. 이를 수행한 결과는 상단 우측 그림과 같습니다. 우선 모든 노드의 BF가 1 이하여서 균형을 이루고 있는 점을 확인할 수 있습니다.
이번엔 rotation 수행 결과로 이진탐색트리 속성이 깨졌는지 여부를 살펴볼까요? ‘중위탐색(inorder traverse) 결과가 정렬된 리스트를 이룬다’는 이진탐색트리의 기본 속성을 활용해 보겠습니다. 중위탐색은 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식입니다. 상단 우측 그림을 중위탐색으로 읽은 결과 요소 하나를 추가했는데도 이진탐색트리의 속성을 만족하고 있음을 살펴볼 수 있습니다.
0.8, 1, 3, 4, 5, 8
single rotation은 rotation을 한 차례 수행해 위와 같이 원하는 결과를 얻을 수 있는 경우를 가리킵니다. 삽입 연산의 single rotation은 다음 두 가지 경우에 $V$($U$의 자식노드, BF 절대값이 1이하)를 중심으로 실시합니다. ($U$는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드)
- $V$가 $U$의 왼쪽 자식노드, $V$의 왼쪽 서브트리에 새 노드 삽입 : $V$를 기준으로 right rotation
- $V$가 $U$의 오른쪽 자식노드, $V$의 오른쪽 서브트리에 새 노드 삽입 : $V$를 기준으로 left rotation
left/right rotation를 직관적으로 나타낸 그림은 각각 다음과 같습니다.
single rotation의 파이썬 구현
left rotation의 파이썬 코드는 다음과 같습니다.
def lrotate(self):
# 현재 트리의 기존 root를 A라고 두자
A = self.node
# 기존 root의 right child를 B라고 두자
B = self.node.right.node
# B의 left child(위 그림에서 베타)를 T라고 두자
T = B.left.node
# B를 새로운 root로 지정
self.node = B
# A를 root(B)의 새로운 left child로 지정
B.left.node = A
# T(위 그림에서 베타)를 A의 새로운 right child로 지정
A.right.node = T
right rotation은 위의 반대로 수행하면 됩니다.
def rrotate(self):
A = self.node
B = self.node.left.node
T = B.right.node
self.node = B
B.right.node = A
A.left.node = T
double rotation
rotation 한 차례만으로 원하는 삽입 결과를 내지 못하는 케이스가 존재합니다. 다음 두 가지 경우 double rotation을 수행해 줍니다. ($U$는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드, $V$는 $U$의 자식노드이면서 BF 절대값이 1이하)
- $V$가 $U$의 왼쪽 자식노드, $V$의 오른쪽 서브트리에 새 노드 삽입
- $V$가 $U$의 오른쪽 자식노드, $V$의 왼쪽 서브트리에 새 노드 삽입
아래 그림과 같은 트리 구조에서 $B$에 새로운 요소를 추가한다고 가정해 보겠습니다 (동그라미는 노드, 세모는 서브트리를 가리킵니다) 이렇게 되면 요소 하나를 삽입한 후의 $U$, $V$, $W$의 BF는 각각 2, -1, 1이 됩니다. 따라서 $U$를 루트노드로 하는 서브트리가 재구성 대상이 되겠습니다.
그런데 $V$는 $U$의 왼쪽 자식노드이고, 새 노드는 $V$의 오른쪽 서브트리에 추가됐으므로 double rotation을 수행해 줍니다. 여기에서 $W$는 $V$의 오른쪽 자식노드입니다. 다음과 같습니다.
- 첫번째 : $W$를 중심으로 left rotation 수행 ($A$를 잡아 당겨 내리는 과정)
- 두번째 : $W$를 중심으로 right rotation 수행 ($D$를 잡아 당겨 내리는 과정)
요소 삽입 후 서브트리들 가운데 $C$의 높이만 $h-1$이고 나머지는 모두 $h$인 점을 감안하면 double rotation 수행 후 $U$, $V$, $W$의 BF는 각각 -1, 0, 0이 되어서 균형을 이룹니다. 다음 그림과 같습니다.
구체적인 예를 들어보겠습니다. 하단 좌측그림과 같은 트리에 3.5를 추가한다고 가정해 봅시다. 3.5는 5보다 작으므로 3과 비교하고, 3보다 크므로 4와 비교하고, 4보다는 작고 4의 자식노드가 없습니다. 따라서 3.5가 들어갈 위치는 4의 왼쪽 자식노드가 됩니다. 기존의 이진탐색트리라면 여기에서 삽입 연산을 마칩니다.
하지만 3.5가 추가되면서 $V$와 $U$의 BF는 각각 -1, 2가 됐습니다. $U$를 루트노드로 하는 서브트리가 재구성 대상입니다. 그런데 $V$는 $U$의 왼쪽 자식노드이고, 새 노드(0.8)는 $V$의 오른쪽 서브트리에 추가됐므로 double rotation을 수행해 줍니다. $W$를 중심으로 left rotation을 수행한 뒤 다시 $W$를 중심으로 right rotation을 합니다. 이렇게 트리를 재구성하면 $W$가 루트노드가 됩니다.
이를 수행한 결과는 상단 우측 그림과 같습니다. 삽입이 우리가 원하는 대로 됐는지 볼까요? 우선 모든 노드의 BF가 1 이하여서 균형을 이루고 있는 점을 확인할 수 있습니다. 상단 우측 그림의 트리를 중위탐색으로 읽은 결과는 다음과 같습니다. 정렬된 순서대로 출력돼 이진탐색트리의 속성을 만족하고 있음을 살펴볼 수 있습니다.
1, 3, 3.5, 4, 5, 8
시나리오별 rotation
지금까지 설명한 내용을 네 개 시나리오별로 정리하면 다음과 같습니다. ($U$는 BF의 절대값이 2 이상인 노드)
- 시나리오1 : $U$의 왼쪽 자식노드의 왼쪽 서브트리 $A$에 새 노드 삽입 : single right rotation
- 시나리오2 : $U$의 왼쪽 자식노드의 오른쪽 서브트리 $B$에 새 노드 삽입 : double rotation(left-right)
- 시나리오3 : $U$의 오른쪽 자식노드의 왼쪽 서브트리 $C$에 새 노드 삽입 : double rotation(right-left)
- 시나리오4 : $U$의 오른쪽 자식노드의 오른쪽 서브트리 $D$에 새 노드 삽입 : single left rotation
이를 구현한 파이썬 코드는 다음과 같습니다.
def rebalance(self):
# 현재 노드(루트)~잎새노드에 이르는 경로의
# 모든 노드에 대해 Balance Factor 업데이트
self.update_heights(False)
self.update_balances(False)
# 현재 노드(루트, 위 그림에서 U)의 BF 절대값이 2 이상이면
# 불균형트리이므로 rotation 수행
while self.balance < -1 or self.balance > 1:
# U의 Balance Factor가 2 이상이면
# U의 왼쪽 서브트리 높이가 오른쪽보다 크므로
# 시나리오1 혹은 시나리오2에 해당
if self.balance > 1:
# U의 왼쪽 자식노드의 왼쪽 서브트리보다
# 오른쪽 서브트리의 높이가 클 경우 시나리오2에 해당
# 우선 single left rotation
if self.node.left.balance < 0:
self.node.left.lrotate()
# rotation이 됐으므로 BF 업데이트
self.update_heights()
self.update_balances()
# U의 왼쪽 자식노드의 왼쪽 서브트리가
# 오른쪽 서브트리보다 높이가 클 경우 시나리오1에 해당
# single right rotation (시나리오2도 이 작업 수행)
self.rrotate()
# rotation이 됐으므로 BF 업데이트
self.update_heights()
self.update_balances()
# U의 Balance Factor가 -1 이하이면
# U의 오른쪽 서브트리 높이가 왼쪽보다 크므로
# 시나리오3 혹은 시나리오4에 해당
if self.balance < -1:
# U의 오른쪽 자식노드의 오른쪽 서브트리보다
# 왼쪽 서브트리의 높이가 클 경우 시나리오3에 해당
# 우선 single right rotation
if self.node.right.balance > 0:
self.node.right.rrotate()
# rotation이 됐으므로 BF 업데이트
self.update_heights()
self.update_balances()
# U의 오른쪽 자식노드의 왼쪽 서브트리보다
# 오른쪽 서브트리보다 높이가 클 경우 시나리오4에 해당
# single left rotation (시나리오2도 이 작업 수행)
self.lrotate()
# rotation이 됐으므로 BF 업데이트
self.update_heights()
self.update_balances()
삽입/삭제 연산
AVL 트리의 삽입 연산은 기본적으로 이진탐색트리와 동일합니다. 다만 마지막에 우리가 이미 정의해놓은 rebalance 함수를 호출하는 과정 하나가 다를 뿐입니다.
def insert(self, key):
tree = self.node
newnode = Node(key)
# empty tree일 경우
if tree == None:
# 새 값(key)을 empty tree의 루트(node)에 넣음
self.node = newnode
# 이 루트의 left/right에 새 empty tree 선언
self.node.left = AVLTree()
self.node.right = AVLTree()
debug("Inserted key [" + str(key) + "]")
# 현재 보고 있는 node가 비어있지 않고
# 새 값이 현재 node의 값보다 작으면
# 왼쪽 서브트리에 삽입 (재귀함수 호출)
elif key < tree.key:
self.node.left.insert(key)
# 새 값이 현재 node의 값보다 크면
# 오른쪽 서브트리에 삽입 (재귀함수 호출)
elif key > tree.key:
self.node.right.insert(key)
else:
debug("Key [" + str(key) + "] already in tree.")
# 현재 노드(루트)에 대해 rebalancing
# 재귀함수 형태로 호출되므로 트리 전체의 루트~새 잎새노드
# 경로의 모든 노드에 대해 계산을 수행하게 됨
self.rebalance()
삭제 연산도 이진탐색트리와 동일합니다. 다만 삭제 후에 Balance Factor가 깨진 노드가 있을 수 있으니 이를 위해 rebalance를 해 줍니다.
insert example
다음 숫자들을 순서대로 넣어 AVL 트리를 구축해 보겠습니다.
3, 2, 1, 4, 5, 6, 7, 16, 15, 14
1까지는 잎새노드에 붙이는 방식으로 삽입하면 됩니다.
그런데 1을 삽입하고 보니, 루트노드인 3의 왼쪽 서브트리 높이는 2, 오른쪽은 0이어서 BF는 2가 됐습니다. 루트노드를 기준으로 rotation을 수행해야 합니다. 그런데 2 노드는 루트노드의 왼쪽 자식노드이고, 새 노드(1)는 2 노드의 왼쪽 서브트리에 추가됐으므로 single rotation(right)을 수행해 줍니다. 다음과 같습니다.
4, 5를 순서대로 붙여 줍니다. 다음과 같습니다.
그런데 5을 삽입하고 보니, 루트노드의 BF는 -2입니다. 3 노드의 BF도 -2입니다. AVL 트리에서는 둘 중에 3 노드(BF가 2 이상이고 잎새노드로부터 가장 가까운 노드)를 기준으로 rotation을 수행합니다. 그런데 4는 3의 오른쪽 자식노드이고, 5는 3의 오른쪽 서브트리에 삽입됐으므로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.
6을 삽입합니다.
6을 삽입하고 보니 루트노드의 BF가 -2입니다. 4 노드는 루트노드의 오른쪽 자식노드이고, 새 노드(6)는 4 노드의 오른쪽 서브트리에 삽입됐으므로 루트노드를 기준으로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.
7을 삽입합니다.
7을 삽입하고 보니 5 노드의 BF가 -2입니다. 6은 5 노드의 오른쪽 자식노드이고, 새 노드(7)는 5 노드의 오른쪽 서브트리에 삽입됐습니다. 따라서 5 노드를 기준으로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.
16과 15를 삽입합니다.
15를 삽입하고 보니 7 노드의 BF가 -3입니다. 16은 7 노드의 오른쪽 자식노드이고, 새 노드(15)는 16 노드의 오른쪽 서브트리에 삽입됐습니다. 따라서 7 노드를 기준으로 double rotation을 수행해 줍니다. 다음과 같습니다.
14를 삽입합니다.
14를 삽입하고 보니 6 노드의 BF가 -2입니다. 15는 6 노드의 오른쪽 자식노드이고, 새 노드(14)는 15 노드의 왼쪽 서브트리에 삽입됐습니다. 따라서 6 노드를 기준으로 double rotation을 수행해 줍니다. 다음과 같습니다.
계산복잡성
AVL 트리의 계산복잡성을 분석해 보겠습니다. 우선 삽입 연산부터 살펴보겠습니다.
AVL 트리는 이진탐색트리의 일종입니다. 이진탐색트리 삽입 연산의 계산복잡성은 트리의 높이가 $h$일 때 $O(h)$입니다. 그런데 AVL 트리는 여기에 추가로, 삽입 후에 Balance Factor를 계산하고, BF의 절대값이 2 이상이면서 새 잎새노드와 가장 가까운 조상노드에 대해 rotation을 수행해 줍니다.
BF 계산 대상은 새 잎새노드~루트노드에 이르는 경로의 모든 노드들이므로 $O(h)$만큼의 계산량이 필요합니다. AVL 트리(이진탐색트리)가 기본적으로 연결리스트로 구현되고, rotation 연산은 부모-자식 간의 관계만 변경해 주면 되기 때문에, single이든 double이든 계산복잡성은 $O(1)$입니다. 따라서 AVL 트리 삽입 연산의 계산복잡성은 BF 계산과 rotation 연산을 고려하더라도 $O(h)$가 됩니다.
AVL 트리 삭제 연산 역시 이진탐색트리와 동일한 $O(h)$입니다. AVL 트리는 여기에 더해 삭제 후에 BF를 계산하고, BF가 높아 균형이 깨진 노드에 대해 rotaion을 수행합니다. 각각 $O(h)$, $O(1)$이 추가됩니다. 따라서 AVL 트리 삭제 연산 역시 BF 계산과 rotation 연산을 고려하더라도 $O(h)$가 됩니다.
요컨대 AVL 트리 삽입/삭제 연산은 트리의 높이 $h$에 의존적이라는 이야기입니다. AVL 트리 노드 수가 $n$개일 때 높이 $h$의 하한은 $2\log_2{n}$이라고 합니다. 따라서 AVL 트리의 계산복잡성은 $O(h)=O(\log{n})$이 됩니다. 이는 $O(n)$인 이진탐색트리보다 낮은 것입니다. rotation 같은 복잡한 과정을 거쳐 트리의 높이를 줄여 계산량을 감소시키는 데 성공한 셈이죠.
전체 코드
파이썬 전체 코드는 이곳에 있습니다. 저도 저장 용도로 남깁니다.
이번 글에서는 AVL 트리에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고하였습니다. 그럼 시작하겠습니다.
concepts
AVL 트리란 서브트리의 높이를 적절하게 제어해 전체 트리가 어느 한쪽으로 늘어지지 않도록 한 이진탐색트리(Binary Search Tree)의 일종입니다. 트리의 높이가 $h$일 때 이진탐색트리의 계산복잡성은 $O(h)$이기 때문에 균형된 트리를 만들어 $h$를 줄이고자 하는 발상에서 비롯됐습니다.
AVL 트리의 핵심 개념 가운데 하나가 Balance Factor(BF)입니다. 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 것입니다. 두 서브트리의 높이가 같거나 잎새노드라면 BF는 0입니다(empty tree의 BF는 -1로 정의). 다음 그림을 보겠습니다.
위 이진탐색트리의 루트노드의 BF는 -1입니다. 왼쪽 서브트리의 높이는 1, 오른쪽은 2이기 때문입니다. 9의 BF는 1입니다. 9의 왼쪽 서브트리의 높이는 1, 오른쪽 서브트리는 존재하지 않아 0이기 때문입니다. 잎새노드인 3, 5, 7은 서브트리가 전혀 없기 때문에 BF는 0이 됩니다. BF가 클 수록 불균형 트리라고 할 수 있겠습니다.
AVL 트리는 요소를 삽입(insert)하거나 삭제(delete)하는 과정에서 서브트리를 재구성해 트리 전체의 균형을 맞춥니다. 삽입/삭제 연산시 BF가 일정 값 이상(보통 2) 혹은 이하(-2)로 바뀐 노드를 기준으로 그 서브트리들의 위치를 rotation하는 방식을 취합니다. rotation에는 두 가지 방식이 있는데 삽입 연산을 중심으로 살펴 보겠습니다.
single rotation
삽입 연산시 single rotation은 다음과 같은 방식으로 수행합니다. $U$는 주어진 이진탐색트리의 루트노드, $V$는 $U$의 왼쪽 자식노드, $Z$는 $U$의 오른쪽 서브트리입니다. $X$와 $Y$는 각각 $V$의 왼쪽, 오른쪽 서브트리를 가리킵니다. $X$, $Y$, $Z$의 높이가 모두 $h$라고 가정해 보겠습니다. 여기에서 $X$에 새로운 요소를 하나 추가해 보겠습니다. 이 경우 $V$와 $U$의 BF는 각각 1, 2가 됩니다.
$U$는 ‘BF가 2 이상, 2 이하일 때 rotation을 실시한다’는 조건에 부합합니다. $U$의 왼쪽 자식노드인 $V$를 기준으로 single rotation을 아래와 같이 실시해 줍니다. 기존 트리 구조에서 $Z$를 잡아 당겨 내려서 $V$를 새로운 루트노드로 만드는 겁니다. 요소 하나가 추가된 $X$의 높이만 $h+1$이고 나머지는 모두 $h$인 점을 감안하면 rotation 실시 후의 $U$, $V$의 BF는 각각 0, 0이 되어 균형 트리를 이룹니다.
single rotation을 일반화한 그림은 다음과 같습니다.
요소 하나 추가하는 데 이렇게까지 복잡하게 할 필요가 있을까 싶기도 합니다. 하지만 AVL 트리는 기본적으로 이진탐색트리라는 점에 유의해야 합니다. 삽입 연산을 수행하더라도, 부모노드는 왼쪽 자식노드보다 크거나 같고, 오른쪽 자식노드보다는 작거나 같다는 성질이 깨지지 않도록 해야 한다는 이야기입니다.
구체적인 예를 들어 볼까요. 아래 트리에서 0.8을 삽입해 보겠습니다. 0.8은 5보다 작으므로 3과 비교하고, 3보다 작으므로 1과 비교하고, 1보다 작고 1의 자식노드가 없습니다. 따라서 0.8이 들어갈 위치는 1의 왼쪽 자식노드가 됩니다. 기존의 이진탐색트리라면 여기에서 삽입 연산을 마칩니다.
하지만 서브트리 $X$에 0.8이 추가되면서 $V$와 $U$의 BF는 각각 1, 2이 됐습니다. $V$를 기준으로 rotation을 해줍니다. 이를 수행한 결과는 상단 우측 그림과 같습니다. 우선 모든 노드의 BF가 1 이하여서 균형을 이루고 있는 점을 확인할 수 있습니다.
이번엔 rotation 수행 결과로 이진탐색트리 속성이 깨졌는지 여부를 살펴볼까요? ‘중위탐색(inorder traverse) 결과가 정렬된 리스트를 이룬다’는 이진탐색트리의 기본 속성을 활용해 보겠습니다. 중위탐색은 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식입니다. 상단 우측 그림을 중위탐색으로 읽은 결과 요소 하나를 추가했는데도 이진탐색트리의 속성을 만족하고 있음을 살펴볼 수 있습니다.
0.8, 1, 3, 4, 5, 8
single rotation은 rotation을 한 차례 수행해 위와 같이 원하는 결과를 얻을 수 있는 경우를 가리킵니다. 삽입 연산의 single rotation은 다음 두 가지 경우에 $V$($U$의 자식노드, BF 절대값이 1이하)를 중심으로 실시합니다. ($U$는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드)
- $V$가 $U$의 왼쪽 자식노드, $V$의 왼쪽 서브트리에 새 노드 삽입 : $V$를 기준으로 right rotation
- $V$가 $U$의 오른쪽 자식노드, $V$의 오른쪽 서브트리에 새 노드 삽입 : $V$를 기준으로 left rotation
left/right rotation를 직관적으로 나타낸 그림은 각각 다음과 같습니다.
single rotation의 파이썬 구현
left rotation의 파이썬 코드는 다음과 같습니다.
def lrotate(self):
# 현재 트리의 기존 root를 A라고 두자
A = self.node
# 기존 root의 right child를 B라고 두자
B = self.node.right.node
# B의 left child(위 그림에서 베타)를 T라고 두자
T = B.left.node
# B를 새로운 root로 지정
self.node = B
# A를 root(B)의 새로운 left child로 지정
B.left.node = A
# T(위 그림에서 베타)를 A의 새로운 right child로 지정
A.right.node = T
right rotation은 위의 반대로 수행하면 됩니다.
def rrotate(self):
A = self.node
B = self.node.left.node
T = B.right.node
self.node = B
B.right.node = A
A.left.node = T
double rotation
rotation 한 차례만으로 원하는 삽입 결과를 내지 못하는 케이스가 존재합니다. 다음 두 가지 경우 double rotation을 수행해 줍니다. ($U$는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드, $V$는 $U$의 자식노드이면서 BF 절대값이 1이하)
- $V$가 $U$의 왼쪽 자식노드, $V$의 오른쪽 서브트리에 새 노드 삽입
- $V$가 $U$의 오른쪽 자식노드, $V$의 왼쪽 서브트리에 새 노드 삽입
아래 그림과 같은 트리 구조에서 $B$에 새로운 요소를 추가한다고 가정해 보겠습니다 (동그라미는 노드, 세모는 서브트리를 가리킵니다) 이렇게 되면 요소 하나를 삽입한 후의 $U$, $V$, $W$의 BF는 각각 2, -1, 1이 됩니다. 따라서 $U$를 루트노드로 하는 서브트리가 재구성 대상이 되겠습니다.
그런데 $V$는 $U$의 왼쪽 자식노드이고, 새 노드는 $V$의 오른쪽 서브트리에 추가됐으므로 double rotation을 수행해 줍니다. 여기에서 $W$는 $V$의 오른쪽 자식노드입니다. 다음과 같습니다.
- 첫번째 : $W$를 중심으로 left rotation 수행 ($A$를 잡아 당겨 내리는 과정)
- 두번째 : $W$를 중심으로 right rotation 수행 ($D$를 잡아 당겨 내리는 과정)
요소 삽입 후 서브트리들 가운데 $C$의 높이만 $h-1$이고 나머지는 모두 $h$인 점을 감안하면 double rotation 수행 후 $U$, $V$, $W$의 BF는 각각 -1, 0, 0이 되어서 균형을 이룹니다. 다음 그림과 같습니다.
구체적인 예를 들어보겠습니다. 하단 좌측그림과 같은 트리에 3.5를 추가한다고 가정해 봅시다. 3.5는 5보다 작으므로 3과 비교하고, 3보다 크므로 4와 비교하고, 4보다는 작고 4의 자식노드가 없습니다. 따라서 3.5가 들어갈 위치는 4의 왼쪽 자식노드가 됩니다. 기존의 이진탐색트리라면 여기에서 삽입 연산을 마칩니다.
하지만 3.5가 추가되면서 $V$와 $U$의 BF는 각각 -1, 2가 됐습니다. $U$를 루트노드로 하는 서브트리가 재구성 대상입니다. 그런데 $V$는 $U$의 왼쪽 자식노드이고, 새 노드(0.8)는 $V$의 오른쪽 서브트리에 추가됐므로 double rotation을 수행해 줍니다. $W$를 중심으로 left rotation을 수행한 뒤 다시 $W$를 중심으로 right rotation을 합니다. 이렇게 트리를 재구성하면 $W$가 루트노드가 됩니다.
이를 수행한 결과는 상단 우측 그림과 같습니다. 삽입이 우리가 원하는 대로 됐는지 볼까요? 우선 모든 노드의 BF가 1 이하여서 균형을 이루고 있는 점을 확인할 수 있습니다. 상단 우측 그림의 트리를 중위탐색으로 읽은 결과는 다음과 같습니다. 정렬된 순서대로 출력돼 이진탐색트리의 속성을 만족하고 있음을 살펴볼 수 있습니다.
1, 3, 3.5, 4, 5, 8
시나리오별 rotation
지금까지 설명한 내용을 네 개 시나리오별로 정리하면 다음과 같습니다. ($U$는 BF의 절대값이 2 이상인 노드)
- 시나리오1 : $U$의 왼쪽 자식노드의 왼쪽 서브트리 $A$에 새 노드 삽입 : single right rotation
- 시나리오2 : $U$의 왼쪽 자식노드의 오른쪽 서브트리 $B$에 새 노드 삽입 : double rotation(left-right)
- 시나리오3 : $U$의 오른쪽 자식노드의 왼쪽 서브트리 $C$에 새 노드 삽입 : double rotation(right-left)
- 시나리오4 : $U$의 오른쪽 자식노드의 오른쪽 서브트리 $D$에 새 노드 삽입 : single left rotation
이를 구현한 파이썬 코드는 다음과 같습니다.
def rebalance(self):
# 현재 노드(루트)~잎새노드에 이르는 경로의
# 모든 노드에 대해 Balance Factor 업데이트
self.update_heights(False)
self.update_balances(False)
# 현재 노드(루트, 위 그림에서 U)의 BF 절대값이 2 이상이면
# 불균형트리이므로 rotation 수행
while self.balance < -1 or self.balance > 1:
# U의 Balance Factor가 2 이상이면
# U의 왼쪽 서브트리 높이가 오른쪽보다 크므로
# 시나리오1 혹은 시나리오2에 해당
if self.balance > 1:
# U의 왼쪽 자식노드의 왼쪽 서브트리보다
# 오른쪽 서브트리의 높이가 클 경우 시나리오2에 해당
# 우선 single left rotation
if self.node.left.balance < 0:
self.node.left.lrotate()
# rotation이 됐으므로 BF 업데이트
self.update_heights()
self.update_balances()
# U의 왼쪽 자식노드의 왼쪽 서브트리가
# 오른쪽 서브트리보다 높이가 클 경우 시나리오1에 해당
# single right rotation (시나리오2도 이 작업 수행)
self.rrotate()
# rotation이 됐으므로 BF 업데이트
self.update_heights()
self.update_balances()
# U의 Balance Factor가 -1 이하이면
# U의 오른쪽 서브트리 높이가 왼쪽보다 크므로
# 시나리오3 혹은 시나리오4에 해당
if self.balance < -1:
# U의 오른쪽 자식노드의 오른쪽 서브트리보다
# 왼쪽 서브트리의 높이가 클 경우 시나리오3에 해당
# 우선 single right rotation
if self.node.right.balance > 0:
self.node.right.rrotate()
# rotation이 됐으므로 BF 업데이트
self.update_heights()
self.update_balances()
# U의 오른쪽 자식노드의 왼쪽 서브트리보다
# 오른쪽 서브트리보다 높이가 클 경우 시나리오4에 해당
# single left rotation (시나리오2도 이 작업 수행)
self.lrotate()
# rotation이 됐으므로 BF 업데이트
self.update_heights()
self.update_balances()
삽입/삭제 연산
AVL 트리의 삽입 연산은 기본적으로 이진탐색트리와 동일합니다. 다만 마지막에 우리가 이미 정의해놓은 rebalance 함수를 호출하는 과정 하나가 다를 뿐입니다.
def insert(self, key):
tree = self.node
newnode = Node(key)
# empty tree일 경우
if tree == None:
# 새 값(key)을 empty tree의 루트(node)에 넣음
self.node = newnode
# 이 루트의 left/right에 새 empty tree 선언
self.node.left = AVLTree()
self.node.right = AVLTree()
debug("Inserted key [" + str(key) + "]")
# 현재 보고 있는 node가 비어있지 않고
# 새 값이 현재 node의 값보다 작으면
# 왼쪽 서브트리에 삽입 (재귀함수 호출)
elif key < tree.key:
self.node.left.insert(key)
# 새 값이 현재 node의 값보다 크면
# 오른쪽 서브트리에 삽입 (재귀함수 호출)
elif key > tree.key:
self.node.right.insert(key)
else:
debug("Key [" + str(key) + "] already in tree.")
# 현재 노드(루트)에 대해 rebalancing
# 재귀함수 형태로 호출되므로 트리 전체의 루트~새 잎새노드
# 경로의 모든 노드에 대해 계산을 수행하게 됨
self.rebalance()
삭제 연산도 이진탐색트리와 동일합니다. 다만 삭제 후에 Balance Factor가 깨진 노드가 있을 수 있으니 이를 위해 rebalance를 해 줍니다.
insert example
다음 숫자들을 순서대로 넣어 AVL 트리를 구축해 보겠습니다.
3, 2, 1, 4, 5, 6, 7, 16, 15, 14
1까지는 잎새노드에 붙이는 방식으로 삽입하면 됩니다.
그런데 1을 삽입하고 보니, 루트노드인 3의 왼쪽 서브트리 높이는 2, 오른쪽은 0이어서 BF는 2가 됐습니다. 루트노드를 기준으로 rotation을 수행해야 합니다. 그런데 2 노드는 루트노드의 왼쪽 자식노드이고, 새 노드(1)는 2 노드의 왼쪽 서브트리에 추가됐으므로 single rotation(right)을 수행해 줍니다. 다음과 같습니다.
4, 5를 순서대로 붙여 줍니다. 다음과 같습니다.
그런데 5을 삽입하고 보니, 루트노드의 BF는 -2입니다. 3 노드의 BF도 -2입니다. AVL 트리에서는 둘 중에 3 노드(BF가 2 이상이고 잎새노드로부터 가장 가까운 노드)를 기준으로 rotation을 수행합니다. 그런데 4는 3의 오른쪽 자식노드이고, 5는 3의 오른쪽 서브트리에 삽입됐으므로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.
6을 삽입합니다.
6을 삽입하고 보니 루트노드의 BF가 -2입니다. 4 노드는 루트노드의 오른쪽 자식노드이고, 새 노드(6)는 4 노드의 오른쪽 서브트리에 삽입됐으므로 루트노드를 기준으로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.
7을 삽입합니다.
7을 삽입하고 보니 5 노드의 BF가 -2입니다. 6은 5 노드의 오른쪽 자식노드이고, 새 노드(7)는 5 노드의 오른쪽 서브트리에 삽입됐습니다. 따라서 5 노드를 기준으로 single rotation(left)를 수행해 줍니다. 다음과 같습니다.
16과 15를 삽입합니다.
15를 삽입하고 보니 7 노드의 BF가 -3입니다. 16은 7 노드의 오른쪽 자식노드이고, 새 노드(15)는 16 노드의 오른쪽 서브트리에 삽입됐습니다. 따라서 7 노드를 기준으로 double rotation을 수행해 줍니다. 다음과 같습니다.
14를 삽입합니다.
14를 삽입하고 보니 6 노드의 BF가 -2입니다. 15는 6 노드의 오른쪽 자식노드이고, 새 노드(14)는 15 노드의 왼쪽 서브트리에 삽입됐습니다. 따라서 6 노드를 기준으로 double rotation을 수행해 줍니다. 다음과 같습니다.
계산복잡성
AVL 트리의 계산복잡성을 분석해 보겠습니다. 우선 삽입 연산부터 살펴보겠습니다.
AVL 트리는 이진탐색트리의 일종입니다. 이진탐색트리 삽입 연산의 계산복잡성은 트리의 높이가 $h$일 때 $O(h)$입니다. 그런데 AVL 트리는 여기에 추가로, 삽입 후에 Balance Factor를 계산하고, BF의 절대값이 2 이상이면서 새 잎새노드와 가장 가까운 조상노드에 대해 rotation을 수행해 줍니다.
BF 계산 대상은 새 잎새노드~루트노드에 이르는 경로의 모든 노드들이므로 $O(h)$만큼의 계산량이 필요합니다. AVL 트리(이진탐색트리)가 기본적으로 연결리스트로 구현되고, rotation 연산은 부모-자식 간의 관계만 변경해 주면 되기 때문에, single이든 double이든 계산복잡성은 $O(1)$입니다. 따라서 AVL 트리 삽입 연산의 계산복잡성은 BF 계산과 rotation 연산을 고려하더라도 $O(h)$가 됩니다.
AVL 트리 삭제 연산 역시 이진탐색트리와 동일한 $O(h)$입니다. AVL 트리는 여기에 더해 삭제 후에 BF를 계산하고, BF가 높아 균형이 깨진 노드에 대해 rotaion을 수행합니다. 각각 $O(h)$, $O(1)$이 추가됩니다. 따라서 AVL 트리 삭제 연산 역시 BF 계산과 rotation 연산을 고려하더라도 $O(h)$가 됩니다.
요컨대 AVL 트리 삽입/삭제 연산은 트리의 높이 $h$에 의존적이라는 이야기입니다. AVL 트리 노드 수가 $n$개일 때 높이 $h$의 하한은 $2\log_2{n}$이라고 합니다. 따라서 AVL 트리의 계산복잡성은 $O(h)=O(\log{n})$이 됩니다. 이는 $O(n)$인 이진탐색트리보다 낮은 것입니다. rotation 같은 복잡한 과정을 거쳐 트리의 높이를 줄여 계산량을 감소시키는 데 성공한 셈이죠.
전체 코드
파이썬 전체 코드는 이곳에 있습니다. 저도 저장 용도로 남깁니다.
Comments