AVL 트리
트리 내의 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않은 상태로 유지되는 이진 검색 트리
AVL 트리의 회전
1. 좌회전
def rotateLeft(self, t):
tR = t.right; tRL = tR.left
tR.left = t; t.right = tRL
t.height = max(t.left.height, t.right.height) + 1
tR.height = max(tR.left.height, tR.right.height) + 1
# 밑에서 부터 올라가면서 높이를 수정해 주어야 한다!
return tR
2. 우회전
def rotateRight(self, t):
tL = t.left; tLR = tL.right
tL.right = t; t.left = tLR
t.height = max(t.left.height, t.right.height) + 1
tL.height = max(tL.left.height, tL.right.height) + 1
return tLAVL 트리의 수선 (균형 맞추기)
t를 루트로 하는 트리의 수선 작업은 t의 네 손자 서브 트리 중 가장 깊은 것에 따라 다음 네 가지 유형으로 나뉜다.
LL : t.left.left가 가장 깊음
LR : t.left.right 가 자장 깊음
RR : t.right.right가 가장 깊음
RL : t.right.left가 가장 깊음
LL유형의 해결 : t를 기준으로 우회전한다.
LR유형의 해결 : t.left를 기준으로 좌회전해서 LL유형으로 만든 다음, t를 기준으로 우회전한다.
RR유형의 해결 : t를 기준으로 좌회전한다.
RL유형의 해결 : t.left를 기준으로 우회전해서 RR유형으로 만든 다음 t를 기준으로 좌회전한다.
# 균형 맞추기
def bf(self, t):
return t.left.height - t.right.height
# 양수이면 L비대, 음수이면 R비대
def rotateLeft(self, t):
tR = t.right; tRL = tR.left
tR.left = t; t.right = tRL
t.height = max(t.left.height, t.right.height) + 1
tR.height = max(tR.left.height, tR.right.height) + 1
# 밑에서 부터 올라가면서 높이를 수정해 주어야 한다!
return tR
def rotateRight(self, t):
tL = t.left; tLR = tL.right
tL.right = t; t.left = tLR
t.height = max(t.left.height, t.right.height) + 1
tL.height = max(tL.left.height, tL.right.height) + 1
return tL
def getBalance(self, t):
if self.bf(t) > 1: # L 유형
if self.bf(t.left) < 0: # LR
t.left = self.rotateLeft(t.left)
return self.rotateRight(t) # LL
elif self.bf(t) < -1: # R 유형
if self.bf(t.right) > 0: # RL
t.right = self.rotateRight(t.right)
return self.rotateLeft(t) # RR
else: # 수선 불필요
return t
bf > 1 : L 유형
bf < -1 : R 유형
None 대신 경계 노드 NIL로 처리하면 일반성이 높아진다.
노드 x가 None이라 해도 NIL.height (-1)가 존재하며, 서브트리의 높이 계산을 위한 필드 height를 쉽게 처리할 수 있다.
삽입과 삭제 과정에서 높이에 변화가 생길 가능성이 있는 모든 곳에서 AVL 균형을 체크하고, 만일 균형이 깨지면 균형 맞추기 작업을 수행한다.
검색 과정에서는 AVL 균형이 깨지지 않는다.
AVL 트리의 구현
class AVLNode:
def __init__(self, item, left, right, height):
self.item = item
self.left = left
self.right = right
self.height = height
class AVLTree:
def __init__(self):
self.NIL = AVLNode(None, None, None, -1) # NIL의 height는 -1로, 리프노드의 height는 0으로 한다.
self.__root = self.NIL
# 균형 맞추기
def bf(self, t):
return t.left.height - t.right.height
# 양수이면 L비대, 음수이면 R비대
def rotateLeft(self, t):
tR = t.right; tRL = tR.left
tR.left = t; t.right = tRL
t.height = max(t.left.height, t.right.height) + 1
tR.height = max(tR.left.height, tR.right.height) + 1
# 밑에서 부터 올라가면서 높이를 수정해 주어야 한다!
return tR
def rotateRight(self, t):
tL = t.left; tLR = tL.right
tL.right = t; t.left = tLR
t.height = max(t.left.height, t.right.height) + 1
tL.height = max(tL.left.height, tL.right.height) + 1
return tL
def getBalance(self, t):
if self.bf(t) > 1: # L 유형
if self.bf(t.left) < 0: # LR
t.left = self.rotateLeft(t.left)
return self.rotateRight(t) # LL
elif self.bf(t) < -1: # R 유형
if self.bf(t.right) > 0: # RL
t.right = self.rotateRight(t.right)
return self.rotateLeft(t) # RR
else: # 수선 불필요
return t
# 원소 검색 : 검색 과정에서는 AVL 균형이 깨지지 않는다.
def search(self, x):
return self.__searchItem(self.__root, x)
def __searchItem(self, tNode, x):
if tNode == self.NIL or x == tNode.item:
return tNode
elif x < tNode.item:
return self.__searchItem(tNode.left, x)
else:
return self.__searchItem(tNode.right, x)
# 원소 삽입 : 높이에 변화가 생길 가능성이 있는 모든 곳에서 균형을 체크하고 만일 균형이 깨지면 균형 맞추기 작업을 수행한다
def insert(self, x):
self.__root = self.__insertItem(self.__root, x)
def __insertItem(self, tNode, x):
if tNode == self.NIL: # self.NIL의 item값이 None이므로 int인 x값과 직접 비교가 불가능 하므로 여기서 걸러져야 함!!!
tNode = AVLTree(x, self.NIL, self.NIL, 0)
elif x < tNode.item:
tNode.left = self.__insertItem(tNode.left, x)
tNode.height = max(tNode.left.height, tNode.right.height) + 1
tNode = self.getBalance(tNode)
else:
tNode.right = self.__insertItem(tNode.right, x)
tNode.height = max(tNode.left.height, tNode.right.height) + 1
tNode = self.getBalance(tNode)
return tNode
# 원소 삭제 : 높이에 변화가 생길 가능성이 있는 모든 곳에서 균형을 체크하고 만일 균형이 깨지면 균형 맞추기 작업을 수행한다
def delete(self, x):
self.__root = self.__deleteItem(self.__root, x)
def __deleteItem(self, tNode, x):
if tNode == self.NIL:
return self.NIL
elif x == tNode.item:
tNode = self.__deleteNode(tNode)
# 이미 height를 수정한 tNode가 tNode자리에 들어오는 것이기 때문에 따로 height를 조정할 필요는 없다.
elif x < tNode.item:
tNode.left = self.__deleteItem(tNode.left, x)
tNode.height = max(tNode.left.height, tNode.right.height) + 1
tNode = self.getBalance(tNode)
else:
tNode.right = self.__deleteItem(tNode.right, x)
tNode.height = max(tNode.left.height, tNode.right.height) + 1
tNode = self.getBalance(tNode)
return tNode
def __deleteNode(self, tNode):
if tNode.left == self.NIL and tNode.right == self.NIL:
return self.NIL
elif tNode.left == self.NIL:
return tNode.right
elif tNode.right == self.NIL:
return tNode.left
else:
(rtnItem, rtnNode) = self.__deleteMinItem(tNode.right)
tNode.item = rtnItem
tNode.right = rtnNode
tNode.height = max(tNode.left.height, tNode.right.height) + 1
tNode = self.getBalance(tNode)
return tNode
def __deleteMinItem(self, tNode):
if tNode.left == None:
return (tNode.item, tNode.right)
else:
(rtnItem, rtnNode) = self.__deleteMinItem(tNode.left)
tNode.left = rtnNode
tNode.height = max(tNode.left.height, tNode.right.height) + 1
tNode = self.getBalance(tNode)
return (rtnItem, tNode)
# 기타 작업 : isEmpty, clear
def isEmpty(self):
return self.__root == self.NIL
def clear(self):
self.__root = self.NIL