AVL Tree
ratsgo's blog의 AVL Tree 를 참고하여 작성하였습니다.
- 이진탐색트리(Binary Search Tree)의 일종
- 이진탐색트리의 탐색 시간복잡도 : 𝑂(ℎ), h : 트리의 높이
- 서브트리의 높이를 조절해서 전체 트리가 한쪽으로 늘어지지 않도록 하는 것이 핵심
- 균형된 트리를 만들어 ℎ를 줄입니다.
- 기본적으로 삽입(insert) / 삭제(delete) 연산은 일반적인 BST과 동일합니다.
- 다만, 연산 이후 Balance Factor(BF) 값에 따라 서브트리를 재구성해 트리 전체의 균형을 맞춥니다 (Rebalance).
- Balance Factor(BF) : 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값
- 두 서브트리의 높이가 같거나 잎새노드라면 BF = 0 (empty tree의 BF는 -1로 정의)
- BF가 클 수록 불균형 트리
- 삽입/삭제 연산시 BF가 일정 값 이상(보통 2) 혹은 이하(-2)로 바뀐 노드를 기준으로 서브트리를 rotation 합니다.
- rotation 은 두가지 방식이 있습니다.
- single rotation
- 𝑈 는 주어진 이진탐색트리의 루트노드, 𝑉 는 𝑈 의 왼쪽 자식노드, 𝑍 는 𝑈 의 오른쪽 서브트리, 𝑋 와 𝑌 는 각각 𝑉 의 왼쪽, 오른쪽 서브트리, 𝑋 , 𝑌 , 𝑍 의 높이가 모두 ℎ 라고 가정하겠습니다.
- 아래 그림처럼 𝑋 에 새로운 노드를 하나 추가하는 경우, 𝑉 와 𝑈 의 BF는 각각 1, 2가 됩니다.
- 𝑈 는 BF가 2 이상, -2 이하일 때 rotation을 실시한다 는 조건에 부합
- 𝑈 의 BF가 2 이상(양수)이므로 왼쪽 자식노드인 𝑉 를 기준으로 single rotation 을 합니다.이 때 V의 오른쪽 자식노드 Y가 존재한다면, 이진탐색트리의 성질에 따라 V < Y < U 입니다.요소 하나가 추가된 𝑋 의 높이만 ℎ+1 이고 나머지는 모두 ℎ 인 점을 감안하면 rotation 실시 후의 𝑈, 𝑉 의 BF는 각각 0, 0이 되어 균형 트리를 이룹니다.
- 따라서 rotation 후에 U의 왼쪽 자식노드로 넣어주게 되면 이진탐색트리의 성질이 깨지지 않습니다.
- 기존 트리 구조에서 𝑍 를 잡아 당겨 내려서 𝑉 를 새로운 루트노드로 만듭니다.
- _single rotation_을 일반화한 그림
- 이진탐색트리의 성징을 깨뜨리지 않기 위한 방법입니다.
- (부모노드는 왼쪽 자식노드보다 크거나 같고, 오른쪽 자식노드보다는 작거나 같다는 성질)
- [예시] 삽입연산 (0.8)
- 0.8이 들어갈 위치는 1의 왼쪽 자식노드로 삽입.
- 서브트리 𝑋 에 0.8이 추가되면서 𝑉와 𝑈의 BF는 각각 1, 2
- 𝑉를 기준으로 single rotation
- rotation 수행 결과 이진탐색트리 속성이 깨졌는지 여부를
중위순회(inorder traverse)으로 확인할 수 있습니다.0.8, 1, 3, 4, 5, 8 로 이진탐색트리 속성이 깨지지 않았음을 확인할 수 있습니다. - 중위순회의 결과가 정렬된 리스트이면 됩니다.
- 중위순회과 관련된 내용은 Binary Search Tree 참고하세요.
- 0.8은 5보다 작으므로 3과 비교하고, 3보다 작으므로 1과 비교하고, 1보다 작고 1의 자식노드가 없습니다.
- 삽입 연산의 _single rotation_은 두 가지 경우에 𝑉(𝑈의 자식노드, BF 절대값이 1이하)를 중심으로 실시합니다.
- 𝑉가 𝑈의 왼쪽 자식노드, 𝑉의 왼쪽 서브트리에 새 노드 삽입 : 𝑉를 기준으로 right rotation
- 𝑉가 𝑈의 오른쪽 자식노드, 𝑉의 오른쪽 서브트리에 새 노드 삽입 : 𝑉를 기준으로 left rotation
- (𝑈는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드)
- _left/right rotation_를 직관적으로 나타낸 그림
]
- double rotation다음 두 가지 경우 _double rotation_을 수행한다.
- 𝑉가 𝑈의 왼쪽 자식노드, 𝑉의 오른쪽 서브트리에 새 노드 삽입
- 𝑉가 𝑈의 오른쪽 자식노드, 𝑉의 왼쪽 서브트리에 새 노드 삽입
아래 그림과 같은 트리 구조에서 𝐵에 새로운 요소를 추가한다고 가정.이렇게 되면 요소 하나를 삽입한 후의 𝑈, 𝑉, 𝑊W의 BF는 각각 2, -1, 1이 된다.
)
- 𝑊를 중심으로 left rotation 수행 (𝐴를 잡아 당겨 내리는 과정)
- 𝑊를 중심으로 right rotation 수행 (𝐷를 잡아 당겨 내리는 과정)
)
- 삽입 예시 (3.5)
- 3.5는 5보다 작으므로 3과 비교하고, 3보다 크므로 4와 비교하고, 4보다는 작고 4의 자식노드가 없다.
- 따라서 3.5가 들어갈 위치는 4의 왼쪽 자식노드가 된다.
- 3.5가 추가되면서 𝑉와 𝑈의 BF는 각각 -1, 2가 된다.
- 𝑈를 루트노드로 하는 서브트리가 재구성 대상.
- 𝑉는 𝑈의 왼쪽 자식노드이고, 새 노드(0.8)는 𝑉의 오른쪽 서브트리에 추가됐므로 _double rotation_을 수행.
- 𝑊를 중심으로 left rotation 수행.
- 다시 𝑊를 중심으로 right rotation 수행.이렇게 트리를 재구성하면 𝑊가 루트노드가 된다.
- 모든 노드의 BF가 1 이하여서 균형을 이루고 있는 점을 확인할 수 있다.
- 중위순회로 결과 : 1, 3, 3.5, 4, 5, 8
- 3.5는 5보다 작으므로 3과 비교하고, 3보다 크므로 4와 비교하고, 4보다는 작고 4의 자식노드가 없다.
- 다음 그림과 같습니다.
- 요소 삽입 후 서브트리들 가운데 𝐶의 높이만 ℎ−1이고 나머지는 모두 ℎ이므로 double rotation 수행 후 𝑈, 𝑉, 𝑊의 BF는 각각 -1, 0, 0이 되어서 균형을 이룬다.
- 여기에서 𝑊는 𝑉의 오른쪽 자식노드.
- 이런 경우(𝑉는 𝑈의 왼쪽 자식노드이고, 새 노드는 𝑉의 오른쪽 서브트리에 추가), _double rotation_을 수행한다.
- 아래와 같이 문제(BF가 2이상 혹은 -2 이하)가 해결되지 않습니다.
- 그런데 _single rotation_을 수행하게 되면,
- 따라서 𝑈를 루트노드로 하는 서브트리가 재구성 대상이다.
- (동그라미는 노드, 세모는 서브트리)
- (𝑈는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드, 𝑉는 𝑈의 자식노드이면서 BF 절대값이 1이하)
- rotation 한 차례만으로 원하는 삽입 결과를 내지 못하는 케이스가 존재한다.
- 시나리오별 rotation
- 𝑈의 왼쪽 자식노드의 왼쪽 서브트리 𝐴에 새 노드 삽입 : single right rotation
- 𝑈의 왼쪽 자식노드의 오른쪽 서브트리 𝐵에 새 노드 삽입 : double rotation(left-right)
- 𝑈의 오른쪽 자식노드의 왼쪽 서브트리 𝐶에 새 노드 삽입 : double rotation(right-left)
- 𝑈의 오른쪽 자식노드의 오른쪽 서브트리 𝐷D에 새 노드 삽입 : single left rotation
- (𝑈는 BF의 절대값이 2 이상인 노드)
- single rotation
- 계산복잡성
- 삽입
- 이진탐색트리 삽입 연산의 계산복잡성은 트리의 높이가 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 트리의 계산복잡성은 O(h)=O(logn)이 됩니다.rotation 같은 복잡한 과정을 거쳐 트리의 높이를 줄여 계산량을 감소시키는 데 성공한 셈입니다.
- 삽입
- 이는 O(n)인 이진탐색트리보다 낮은 것입니다.
- AVL 트리 노드 수가 n개일 때 높이 h의 하한은 2log2n이라고 합니다.
- 기본적으로 AVL 트리는 이진탐색트리의 일종입니다.
예시
예시는 ratsgo's blog의 AVL Tree 의 3, 2, 1, 4, 5, 6, 7, 16, 15, 14 삽입 연산과정을 천천히 따라가보면 도움이 될 것 같습니다.
Python Code
전체 소스는 이곳 에 정리해두었습니다.
class Node():
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class AVLTree():
def __init__(self, *args):
self.node = None
self.height = -1
self.balance = 0;
if len(args) == 1:
for i in args[0]:
self.Insert(i)
def IsLeaf(self):
return (self.height == 0)
def Insert(self, key):
'''
Insert Node
'''
new_node = Node(key)
now = self.node
if now == None:
self.node = new_node
self.node.left = AVLTree()
self.node.right = AVLTree()
print("Inserted key [" + str(key) + "]")
elif key < now.key:
now.left.Insert(key)
elif key > now.key:
now.right.Insert(key)
else:
print("Key [" + str(key) + "] already in tree.")
self.Rebalance()
def Delete(self, key):
'''
Delete Node
'''
now = self.node
if now != None:
if now.key == key:
print("Deleting ... " + str(key))
if now.left.node == None and now.right.node == None:
now = None
elif now.left.node == None:
now = now.right.node
elif now.right.node == None:
now = now.left.node
else:
replacement = self.LogicalSuccessor(now)
if replacement != None:
print("Found replacement for " + str(key) + " -> " + str(replacement.key))
now.key = replacement.key
now.right.Delete(replacement.key)
elif key < now.key:
now.left.Delete(key)
elif key > now.key:
now.right.Delete(key)
self.Rebalance()
else:
return
def LogicalPredecessor(self, node):
'''
Find the biggest valued node in LEFT child
'''
node = node.left.node
if node != None:
while node.right != None:
if node.right.node == None:
return node
else:
node = node.right.node
return node
def LogicalSuccessor(self, node):
'''
Find the smallese valued node in RIGHT child
'''
node = node.right.node
if node != None: # just a sanity check
while node.left != None:
print("LS: traversing: " + str(node.key))
if node.left.node == None:
return node
else:
node = node.left.node
return node
def Rebalance(self):
'''
Rebalance a particular (sub)tree
'''
# key inserted. Let's check if we're balanced
self.UpdateHeights(False)
self.UpdateBalances(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.UpdateHeights()
self.UpdateBalances()
# U의 왼쪽 자식노드의 왼쪽 서브트리가
# 오른쪽 서브트리보다 높이가 클 경우 시나리오1에 해당
# single right rotation (시나리오2도 이 작업 수행)
self.RRotate()
# rotation이 됐으므로 BF 업데이트
self.UpdateHeights()
self.UpdateBalances()
# 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.UpdateHeights()
self.UpdateBalances()
# U의 오른쪽 자식노드의 왼쪽 서브트리보다
# 오른쪽 서브트리보다 높이가 클 경우 시나리오4에 해당
# single left rotation (시나리오2도 이 작업 수행)
self.LRotate()
# rotation이 됐으므로 BF 업데이트
self.UpdateHeights()
self.UpdateBalances()
def RRotate(self):
# Rotate left pivoting on self
print ('Rotating ' + str(self.node.key) + ' right')
A = self.node
B = self.node.left.node
T = B.right.node
self.node = B
B.right.node = A
A.left.node = T
def LRotate(self):
# Rotate left pivoting on self
print ('Rotating ' + str(self.node.key) + ' left')
A = self.node
B = self.node.right.node
T = B.left.node
self.node = B
B.left.node = A
A.right.node = T
def UpdateHeights(self, recurse=True):
if self.node == None:
self.height = -1
else:
if recurse:
if self.node.left != None:
self.node.left.UpdateHeights()
if self.node.right != None:
self.node.right.UpdateHeights()
self.height = max(self.node.left.height, self.node.right.height) + 1
def UpdateBalances(self, recurse=True):
if self.node == None:
self.balance = 0
else:
if recurse:
if self.node.left != None:
self.node.left.UpdateBalances()
if self.node.right != None:
self.node.right.UpdateBalances()
self.balance = self.node.left.height - self.node.right.height
def CheckBalanced(self):
if self == None or self.node == None:
return True
# We always need to make sure we are balanced
self.UpdateHeights()
self.UpdateBalances()
return ((abs(self.balance) < 2) and self.node.left.CheckBalanced() and self.node.right.CheckBalanced())
def InorderTraverse(self):
if self.node == None:
return []
inlist = []
l = self.node.left.InorderTraverse()
for i in l:
inlist.append(i)
inlist.append(self.node.key)
l = self.node.right.InorderTraverse()
for i in l:
inlist.append(i)
return inlist'SW > Algorithm & Data Structure' 카테고리의 다른 글
| Binary Search Tree (0) | 2021.06.13 |
|---|---|
| Sorting Algorithm (0) | 2021.05.29 |
| Tree (0) | 2021.05.10 |
Comment