Programming 기초/Python
[Python 자료구조 #탐색트리3] AVL트리, AVL트리를 이용한 맵
코딩상륙작전
2023. 5. 26. 19:36
* 심화 학습 : 균형이진탐색트리 - AVL 트리
- AVL 트리는 Adelson-Velskii와 Landis에 의해 제안된 트리이다. AVL트리는 항상 균형 트리를 보장하기 때문에 탐색과 삽입, 삭제 연산에서 항상 O(log_2 n)의 처리시간을 보장한다.
- AVL 트리를 정의하기 위해서는 균형인수를 정의해야 한다.
- 어떤 노드의 균형 인수(balance factor)는 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차로 정의된다.
- AVL 트리는 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다.
AVL 트리 정의
AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1을 넘지 않는 이진탐색 트리이다. 즉 모든 노드의 균형 인수는 0이나 ±1이 되어야 한다.
* AVL 트리의 삽입 연산
- 노드가 삽입되면 삽입되는 위치에서 루트까지의 경로에 있는 모든 조상 노드들의 균형 인수가 영향을 받는다.
- 균형이 깨진 트리의 서브 트리를 회전시켜 다시 균형을 잡을 수 있다.
삽입 연산에서 균형이 깨지는 경우는 다음과 같이 4가지가 있다.
(새로 삽입된 노드 N으로부터 가장 가까우면서 균형 인수가 ±2가 된 조상 노드를 A라고 하자)
- LL 타입 : N이 A의 왼쪽 자식의 왼쪽 서브 트리에 삽입된다.
- LR 타입 : N이 A의 왼쪽 자식의 오른쪽 서브 트리에 삽입된다.
- RR 타입 : N이 A의 오른쪽 자식의 오른쪽 서브 트리에 삽입된다.
- RL 타입 : N이 A의 오른족 자식의 왼쪽 서브 트리에 삽입된다.
LL과 RR 회전은 한번만 회전하는 단순 회전(single rotation) 방법이다.
LR과 RL은 두 번의 회전이 필요한 이중 회전(double rotation)이다.
1. LL 회전
# LL 회전
# 회전에 의해 루트가 변경되므로 반드시 새로운 루트를 반환해야 하는 것에 유의할 것
def rotateLL(A) : # 시계방향 회전
B = A.left # A의 왼쪽서브트리를 담을 B 변수 선언
A.left = B.right
B.right = A
return B # 새로운 루트 B를 반환
2. RR회전
# RR회전
def rotateRR(A) : # 반시계방향 회전
B = A.right # A의 오른쪽 서브트리를 담을 새로운 변수 B 선언
A.right = B.left
B.left = A
return B # 새로운 루트 B를 반환
3. RL회전
# RL 회전
def rotateRL(A) :
B = A.right
A.right = rotateLL(B) # LL 회전
return rotateRR(A) # RR 회전
4. LR회전
# LR회전
def rotateLR(A) :
B = A.left
A.left = rotateRR(B) # RR회전
return rotateLL(A) # LL회전
▶재균형 함수
노드의 균형을 검사하여 균형이 깨져 있으면 재균형하는 전체 함수는 다음과 같다.
↓calc_height() 함수 참고(이전 포스팅에서 다룸)
더보기
def calc_height(n) :
if n is None : # 공백 트리 -> 0을 반환
return 0
hLeft = calc_height(n.left) # 왼쪽 트리의 높이 -> hLeft
hRight = calc_height(n.right) # 오른쪽 트리의 높이 -> hRight
if (hLeft > hRight) : # 더 높은 높이에 1을 더해 반환.
return hLeft + 1
else:
return hRight + 1
# 재균형 함수
def calc_height_diff(n) : # 균형인수 계산기
if n==None :
return 0
return calc_height(n.left) - calc_height(n.right)
def reBalance (parent) :
hDiff = calc_height_diff(parent) # parent의 왼쪽과 오른쪽 서브트리 높이 차를
# 반환하는 함수. parent가 None이면 0을 반환
if hDiff > 1 :
if calc_height_diff( parent.left ) > 0 :
parent = rotateLL( parent )
else :
parent = rotateLR( parent )
elif hDiff < -1 :
if calc_height_diff( parent.right ) < 0 :
parent = rotateRR( parent )
else :
parent = rotateRL( parent )
return parent
▶삽입 함수 구현
이진탐색트리의 삽입함수와 유사하지만 두 가지 차이가 있다.
- 삽입이 끝나면 반드시 재균형 함수를 호출해서 균형을 확인해야 한다.
- 이진탐색트리에서와 달리 삽입 후 서브트리의 루트노드가 변경되는 경우가 많다. 따라서 루트를 반환해야 한다.
# AVL트리의 삽입 연산
# 이진탐색트리ADT에서 삽입할 node의 parent를 찾는 함수를 통해 parent를 찾아서 인수로 넣는다.
def insert_avl(parent, node) :
if node.key < parent.key : # 노드의 키가 부모 노드의 키보다 작을 경우
if parent.left != None : # 부모 노드의 왼족 서브트리가 비어있지 않으면
parent.left = insert_avl(parent.left, node) # AVL 트리 삽입 연산 순환 호출
else : # 부모 노드의 왼쪽 서브트리가 비어있으면 바로 삽입
parent.left = node
return reBalance(parent) # 재균형 함수를 거치고 반환된 새로운 루트를 반환한다.
elif node.key > parent.key : # 노드의 키가 부모 노드의 키보다 클 경우
if parent.right != None :
parent.right = insert_avl(parent.right, node)
else :
parent.right = node
return reBalance(parent)
else : # 노드의 키가 부모 노드의 키와 같을 경우 에러 메시지 반환
print("중복된 키 에러")
* AVL 트리 구축의 예
다음과 같은 데이터가 순서대로 주어졌을 때 AVL 트리가 만들어지는 과정
[7, 8, 9 , 2, 1, 5, 3, 6, 4]
* AVL 트리를 이용한 맵
이전 포스팅에서 구현한 BSTMap에 새로운 삽입기능만 추가한다.(클래스 상속기능 사용)
↓levelorder(), count_leaf(), calc_height(), calc_height_diff() 코드 참고(CircularQueue()는 원형큐 포스팅 참고)
더보기
def levelorder(root): # 레벨 순회 함수
queue = CircularQueue()
queue.enqueue(root)
while not queue.isEmpty():
n = queue.dequeue()
if n is not None:
print(n.key, end=" ")
queue.enqueue(n.left)
queue.enqueue(n.right)
def count_leaf(n): # 단말노드 개수 세는 함수
if n is None:
return 0
elif n.left is None and n.right is None:
return 1
else:
return count_leaf(n.left) + count_leaf(n.right)
def calc_height(n): # 이진트리 높이 계산
if n is None: # 공백 트리 -> 0을 반환
return 0
hLeft = calc_height(n.left) # 왼쪽 트리의 높이 -> hLeft
hRight = calc_height(n.right) # 오른쪽 트리의 높이 -> hRight
if hLeft > hRight: # 더 높은 높이에 1을 더해 반환.
return hLeft + 1
else:
return hRight + 1
def calc_height_diff(n): # 균형인수 계산
if n == None:
return 0
return calc_height(n.left) - calc_height(n.right)
from BSTMap import* # BSTMap.py에서 정의한 모든 것을 사용함
class AVLMap(BSTMap): # BSTMap클래스를 상속한 AVLMap 클래스 선언
def __init__ (self): # AVLMap 클래스의 생성자 함수
super().__init__() # 부모(BSTMap) 클래스의 생성자 호출
def insert(self, key, value=None): # AVL 트리의 삽입 연산을 다시 구현(재정의.overriding)
n = BSTNode(key, value)
if self.isEmpty() :
self.root = n
else :
self.root = insert_avl(self.root, n)
# display연산도 overriding
# 결과를 앞에서 살펴본 AVL 트리 구축 예와 비교하기 위해 중위순회가 아니라 레벨 순회를 사용.
def display(self, msg = 'AVLMap :'):
print(msg, end='')
levelorder(self.root)
print()node = [7,8,9,2,1,5,3,6,4]
map = AVLMap()
for i in node :
map.insert(i)
map.display("AVL(%d): "%i)
print(" 노드의 개수 = %d" % count_node( map.root ))
print(" 단말의 개수 = %d" % count_leaf( map.root ))
print(" 트리의 높이 = %d" % calc_height( map.root ))
---------------------------------------------------------
AVL(7): 7
AVL(8): 7 8
AVL(9): 8 7 9
AVL(2): 8 7 9 2
AVL(1): 8 2 9 1 7
AVL(5): 7 2 8 1 5 9
AVL(3): 7 2 8 1 5 9 3
AVL(6): 7 2 8 1 5 9 3 6
AVL(4): 7 3 8 2 5 9 1 4 6
노드의 개수 = 9
단말의 개수 = 4
트리의 높이 = 4