9-1. AVL 트리

Yeonghyeon·2022년 9월 23일

자료구조 및 알고리즘

목록 보기

10/12

본 포스팅은 아래의 출처를 참고하여 정리한 것입니다.
https://www.youtube.com/watch?v=PIidtIBCjEg&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=1

AVL 트리 (Adelson-Velsky, Landis)

가장 오래된 균형이진탐색트리 중 하나 (1964)
모든 노드에 대해서 노드의 왼쪽 부트리와 오른쪽 부트리의 높이 차가 1 이하인 이진탐색트리
노드 10 기준에서 왼쪽 부트리와 오른쪽 부트리의 높이 차가 2가 됨 ➡️ 10 노드가 AVL 트리 만족 X
노드 3과 노드 1, 노드 5 입장에서는 왼족, 오른쪽 부트리 높이 차가 1
AVL 트리의 조건을 만족하면 항상 $O(logn)$ 이 되느냐 ➡️ 증명해보자

O(logn) 증명

h=0, 1, 2일 때 노드의 개수가 최소인 경우는 각각 1, 2, 4개

일반화: 높이가 h인 AVL 트리 중에서 최소 노드 개수를 $N_h$
- $N_0=1$ , $N_1=2$ , $N_2=4$ , $N_3=7$ , ...
- $N_h=N_{h-1}+N_{h-2}+1$

$N_h=N_{h-1}+N_{h-2}+1$
즉, $N_h \ge 2^\frac{h}{2}$
- 높이가 h이고 노드 개수가 n인 AVL 트리일 때 $h \le c\cdot log_2^n$ 을 증명해야 됨
- $n \ge N_h \ge 2^\frac{h}{2}$
  - $n$ : 노드 개수
  - $N_h$ : AVL 트리의 최소 노드 개수
  $\frac{h}{2} \le log_2^n$
  
  $h \le 2\cdot log_2^n$
- 따라서 $h=O(logn)$

AVL 트리 삽입 연산

class Node: BST와 동일 ➡️ 원래의 key, left, right, parent와 더불어 height(높이) 변수가 추가됨
class BST: 동일하게 사용 ➡️ insert, delete by Merging/Copying, search
- AVL 트리도 BST의 일종이니까
- height 정보 update에 대한 코드 추가 필요
class AVL(BST): 상위 클래스로써 부모인 BST를 물려받아서 사용
- def __init__ 함수 선언하지 않아도 상관없음 ➡️ class BST의 __init__ 함수가 자동으로 불림
- def insert(self, key): BST에도 똑같이 insert 함수가 있지만 AVL class에 정의된 insert가 우선적으로 호출됨 (AVL class에 없는 함수였다면 BST의 함수가 호출됨)
  - AVL의 insert 또한 BST의 insert 규칙과 동일하게 삽입되고(즉 BST의 insert를 그대로 호출해서 사용한 후), 높이 차에 대한 조건을 AVL의 insert에서 조정이 필요한 것
    ➡️ 1. v = super(AVL, self).insert(key)
    (super(현재 class, 전달할 object)).조상 클래스의 함수(key)
    ➡️ 2. rebalance(x, y, z) (회전을 통해 height 차 조정)
    - x는 y의 자식, y는 z의 자식 (z-y-x 순)

insert(self, key):
1. v = super(AVL, self).insert(key) $(O(h)=O(logn))$
1. find x, y, z (z는 처음으로 AVL 조건이 깨진 노드) $(O(h)=O(logn))$
2. w = rebalance(x, y, z) $(O(1))$
3. if w.parent == None: self.root = w $(O(1))$

총 수행 시간은 $O(logn)$ ➡️ 엄청난 발전!

AVL 트리 삭제 연산

p의 자식 노드에서의 삭제 연산
이후 p의 부모 노드 z에서 AVL 트리의 균형 깨짐
z의 자식 노드 왼/오 중 height가 높은 쪽을 y, y의 자식 노드 왼/오 중에서도 height가 더 높은 쪽을 x라고 함 ➡️ 무거운 쪽이 모두 left에 있으므로 z 기준으로 rotateRight()
다시 w에서의 AVL 트리의 균형이 맞지 않음 (부모노드로 타고 올라가면서 계속 균형이 깨질 수 있다는 것, 따라서 삭제 연산은 한두번의 조정으로 균형이 맞춰지지 않기때문에 연산이 조금 더 복잡하다)
- 삽입 연산은 최대 2번의 rotation으로 끝나지만, 삭제 연산은 최악의 경우 $O(logn)$ 번 rotation될 수 있다는 것

def delete(self, u):
	v = super(AVL, slef).deleteByCopying(u): u를 삭제해서 균형이 깨질 수 있는 가장 깊은 곳에 있는 노드 리턴
    while v!=None: # 루트 노드까지 계속 부모노드를 타고 올라가면서 균형 확인
    	if v is not balanced:
        	z = v
            if z.left.height >= z.right.height:
            	y = z.left
            else:
            	y = z.right
            
            if y.left.height >= y.right.height:
            	x = y.left
            else:
            	x = y.right
                
           	v = rebalance(x, y, z) # insert처럼 z-y-x가 한쪽방향으로 나열된 경우와 삼각형 모양으로 나열된 경우로 나뉘어서
            
            w = v # 예전 v를 w에 저장
            v = v.parent # 그림이랑은 안 맞음
   
    # while 빠져나와서 v가 None인 경우
    # v == None, w == root (예전 v)
    self.root = w # 균형 맞춰주면서 root까지 가게되어 root가 바뀌었을 수도 있으니까

AVL 트리 정리

높이 $\le 2logn=O(logn)$
insert: $O(logn)$
- 노드 삽입 $O(logn)$
- rebalance: 1회/2회 회전 $O(1)$
delete: $O(logn)$
- 노드 제거 $O(logn)$
- rebalnce: 매 level에서 1-2회 균형 ➡️ 최악의 경우 $O(logn)$ 회전