[Algorithm] AVL 트리

한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에

이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용한다.

AVL 트리 = 자가 균형 이진 탐색 트리

 

특징

• 이진 트리의 속성을 가진다
• 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다
• 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 차이를 줄인다
• AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간복잡도는 O(logN)이다

균형(밸런스) 잡는 방법

Balance Factor를 사용한다. 이는 왼쪽과 오른쪽의 자식(노드)의 높이 차이를 뜻하는 말이다. 균형인수라고도 한다.

균형 인수의 절대 값이 클수록 트리의 균형이 무너진 것이다.

 

트리를 균형있게 만들어야 하는 이유

트리의 높이가 h라면 이진 탐색 트리의 시간 복잡도는 O(h)가 된다

즉, 한쪽으로만 치우친 트리는 트리로써의 역할을 제대로 하지 못한다.

 

회전(rotation)

• LL 회전

• RR 회전

• LR 문제

RR 회전 후 LL 회전

 

코드 구현

from bstree import Node, BSTree

class AVLnode(Node):
	def __init__(self, data):
    	super().__init__(data)
        self.height = 0
        
class AVLTree(BSTree):
	def get_height(self, node):
    	if node is None:
        	return -1
            
        left_height = node.left.height if node.left else -1
        right_height = node.right.height if node.right else -1
        
        return 1 + max(left_height, right_height)
        
    def get_balance(self, node):
    	return self.get_height(node.left) - self.get_height(node.right)
        
    def _insert(self, node, data):
    	if node is None:
        	return AVLnode(data)
        if node.data > data:
        	node.left = self._insert(node.left, data)
        else:
        	node.right = self._insert(node.right, data)
            
        # 삽입 이후에는 재귀적으로 호출된 각 노드에 대해 높이를 갱신해야 하므로,
        # 현재 노드의 높이를 새로 계산해 할당한다
        node.height = self.get_height(node)
        return node
        
# 트리를 받아서 레벨 순서 순휘하며 값을 출력하는 함수
def level_order(tree):
	q = [tree.root]
    res = []
    
    while q:
    	node = q.pop(0)
        res.append((node.data, node.height, tree.get_balance(node)))
        if node.left:
        	q.append(node.left)
        if node.right:
        	q.append(node.right)
            
    return res
    
tree = AVLTree()
for x in (8, 3, 10, 1, 6, 9, 12, 4, 5, 11):
	tree.insert(x)
    print(level_order(tree))

실행 결과

[(8, 0, 0)]
[(8, 1, 1), (3, 0, 0)]
[(8, 1, 0), (3, 0, 0), (10, 0, 0)]
[(8, 2, 1), (3, 1, 1), (10, 0, 0), (1, 0, 0)]
[(8, 2, 1), (3, 1, 0), (10, 0, 0), (1, 0, 0), (6, 0, 0)]
[(8, 2, 0), (3, 1, 0), (10, 1, 1), (1, 0, 0), (6, 0, 0), (9, 0, 0)]
[(8, 2, 0), (3, 1, 0), (10, 1, 0), (1, 0, 0), (6, 0, 0), (9, 0, 0), (12, 0, 0)]
[(8, 3, 1), (3, 2, -1), (10, 1, 0), (1, 0, 0), (6, 1, 1), (9, 0, 0), (12, 0, 0), (4, 0, 0)]
[(8, 4, 2), (3, 3, -2), (10, 1, 0), (1, 0, 0), (6, 2, 2), (9, 0, 0), (12, 0, 0), (4, 1, -1), (5, 0, 0)]
[(8, 4, 1), (3, 3, -2), (10, 2, -1), (1, 0, 0), (6, 2, 2), (9, 0, 0), (12, 1, 1), (4, 1, -1), (11, 0, 0), (5, 0, 0)]

 노드의 height와 balance factor가 삽입될 때마다 즉시 반영되는 것을 확인할 수 있다. 이 값들을 기준으로 이후에는 불균형이 발생했을 때 어떤 회전을 적용할지 판단할 수 있다. (회전 코드)