AVL 트리
코드
리뷰

AVL 트리

일반 이진 트리에서 발생 할 수 있는 문제인 편향적인 트리를 방지할 수 있는 알고리즘이다.
일반 이진 트리에서 값이 순서대로([1, 2, 3, 4, 5, 6, 7]) 이런식의 값이 들어온다면
루트 노드를 기준으로 오른쪽 레벨만 깊어지게 된다.
이 상태에서 값을 탐색하면 일반 배열에서 N만큼의 시간동안 순회하며 값을 찾는 것과 같은 시간복잡도가 주어지고 이진 탐색 트리의 장점이 희석된다.
이 문제를 해결 하기 위해 값을 트리에 추가 할 때 마다 재귀를 기준으로 값의 배치가 끝나면 다시 돌아오면서 높이와 자식노드 들의 레벨차를 이용하여 불균형이 생기면 노드 간의 배치를 다시 해준다.

---

노드의 레벨

자식노드 들의 레벨 차를 이용하여 노드간 재배치를 하기 전에 먼저 노드의 높이를 알고 있어야 한다.
여기서 말하는 특정 노드의 레벨은 특정 노드의 왼쪽 노드와 오른쪽 노드들 중 더 깊은 노드의 레벨 + 1을 한 값이다.
A노드의 높이 = max(A노드의 왼쪽 노드, A노드의 오른쪽 노드) + 1
즉 해당 노드의 자식들 중 가장 깊은 레벨을 가진 자식 보다 한 레벨 높은 값이다.
코드에서는 값을 삽입 할 때마다 삽입하기 위해 지나간 노드들의 레벨을 갱신 시켜야 한다.

---

자식 노드들 간의 레벨 차이

왼쪽 노드와 오른쪽 노드의 레벨을 알고 있기 때문에 두 자식의 레벨 차가 -1보다 작으면 안되고 1보다 크면 안된다.
A노드기준 자식노드들의 레벨차 = A노드 왼쪽 노드 레벨 - A노드 오른쪽 노드 레벨
즉 왼쪽 노드의 깊이와 오른쪽 노드의 깊이의 차가 1보다 커서는 안된다.

---

노드의 재 배치

두 자식의 레벨차가 1보다 큰걸 확인하면 균형을 맞추기 위해 노드의 재배치가 필요하다.
왼쪽 자식의 레벨이 오른쪽 자식의 레벨보다 크다면 1보다 큰 차이가 난다는 뜻이다.
그럴 경우 레벨이 작은쪽 즉 오른쪽의 깊이를 늘려야 한다. (전체적으로 봤을때는 전체레벨이 줄어듦)
반대의 경우에는 왼쪽깊이를 늘리는 느낌이여야 한다.

코드

class node:
    def __init__(self, val, height = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
        self.height = height


class AVL:
    def __init__(self):
        self.root = None
        
    def height(self, base):
        if base is None:	#부모가 말단 노드인 경우
            return 0
        return base.height	#아닐경우 본인의 높이 리턴
        
    def check_balance(self, base):
        if self.get_level_dif(base) < -1:	#오른쪽 자식이 깊은 경우
            if self.get_level_dif(base.right) > 0:
            # 오른쪽 자식이 깊으면서 그 오른쪽 자식의 왼쪽이 깊을 경우 
            # 그냥 놥두면 정렬을 시켜도 다시 균형이 깨지기 때문에 한번 더 체크
                base = self.relocate_right(base.right)
            base = self.relocate_left(base)
        elif self.get_level_dif(base) > 1:	#위와 완전히 반대
            if self.get_level_dif(base.left) < 0:
                base = self.relocate_left(base.left)
            base = self.relocate_right(base)
        return base
        
    def put(self, val):
        if self.root is None:		#루트가 비어있는경우 예외처리
            self.root = node(val)
            return
        self.root = self.recursion_put(self.root, val) #재귀적으로 처리
        
    def recursion_put(self, base, val):
        if base is None:			#말단 노드에 도착한 경우 해당자리에 노드생성
            return node(val, 1)
        if base.val < val:
            base.right = self.recursion_put(base.right, val)
        elif base.val > val:
            base.left = self.recursion_put(base.left, val)
            
        ##노드의 배치가 끝나고 재귀의 특성으로 돌아오면서 해당 노드의 정보를 갱신
        
        base.height = max(self.height(base.left), self.height(base.right)) + 1
        return self.check_balance(base)
        
    def get_level_dif(self, base):	#해당 노드의 자식들 레벨 차 구하기
        return self.height(base.left) - self.height(base.right)
        
    def relocate_right(self, base):	#왼쪽 자식이 깊은 경우 오른쪽 재배치
        next = base.left
        base.left = next.right
        next.right = base
        base.height = max(self.height(base.left), self.height(base.left)) + 1
        next.height = max(self.height(next.left), self.height(next.left)) + 1
        return next
        
    def relocate_left(self, base):	#오른쪽 자식이 깊은 경우 왼쪽 재배치
        next = base.right
        base.right = next.left
        next.left = base
        base.height = max(self.height(base.left), self.height(base.left)) + 1
        next.height = max(self.height(next.left), self.height(next.left)) + 1
        return next


bt = AVL()
bt.put(1)
bt.put(2)
bt.put(3)
bt.put(4)
bt.put(5)

print(bt.root.right.left.val)

리뷰

노드간의 레벨과 그 레벨 차에 대한 개념을 헷갈려서 초반에 좀 난해했다.
다른문서에서는 회전이라는 개념을 많이 다루는데 개인적으로는 재배치라는 느낌이 더 와닿았다.
재귀로 구현시 돌아오면서 바로바로 갱신을 하고 배치를 해서 상당히 효율적인 느낌이 들었다.