9. AVL 트리

AVL 트리는 모든 내부노드 $v$에 대해, $v$의 좌우 자식들의 높이 차이가 1을 넘지 않는 이진 탐색 트리이다.
AVL 트리의 부트리 역시 AVL 트리이며, 높이 정보는 각 내부 노드에 저장된다.

AVL 트리의 높이균형 속성 덕분에, $n$개의 원소를 저장하는 AVL 트리의 높이는 $O(\log n)$이 보장된다. (이진 탐색 트리는 최악의 경우 $O(n)$)

AVL 트리에서의 삽입/삭제

AVL 트리에서 원소의 삭제와 삽입은 이진 탐색 트리와 유사하나, 삽입 혹은 삭제로 인해 AVL 트리의 높이균형 속성이 파괴될 수 있으므로 이를 복원해주는 작업이 추가된다.

삽입

def insertItem(k, e):
    w = treeSearch(root(), k)
    if isInternal(w):
        raise Exception("Key Already Exists!")
    w.elem = e
    w.key = k
    expandExternal(w)
    searchAndFixAfterInsertion(w) # 이 부분이 추가된다.
    return 

def searchAndFixAfterInsertion(w):
    z = w
    while !isRoot(z):
        z = w.parent() # 루트까지 거슬러 올라가다가
        if !rightBalance(z): # 처음 만난 밸런스 깨진 노드가 z가 된다.
            break
    if isRoot(z) and rightBalance(z): # 만약 루트까지 전부 정상이면 리턴
        return
    y = higherChild(z) # y는 z의 높은 자식
    x = higherChild(y) # x는 y의 높은 자식
    restructure(x, y, z) # 균형을 복구한다. 하위 트리의 균형이 복구되면 루트까지 모든 균형이 복구된다.
    return

def reconstructure(x,y,z):
    a,b,c,t0,t1,t2,t3 = inorder(x,y,z) # x,y,z의 중위순회 순서와, x,y,z를 제외한 나머지 4개의 부트리
    swap(z, b) # 루트를 b로 바꾸고
    a.left = t0
    a.right = t1
    c.left = t2
    c.right =t3
    b.left = a
    b.right = c
    return b

삭제

def removeElement(k):
    w = treeSearch(root(), k)
    if isExternal(w):
        raise Exception("No Such Key!")
    e = w.elem
    z = leftChild(w)
    if !isExternal(z):
        z = rightChild(w)
    if isExternal(z): # 자식 중 외부노드 존재
        zs = reduceExternal(z) # 그냥 지우기
    else:
        y = inOrderSucc(w) # 중위순회 후계자 탐색
        z = leftChild(y)
        w.key = y.key
        w.elem = y.elem
        zs = reduceExternal(z)
    searchAndFixAfterRemoval(zs) # 균형 복구
    return e

def searchAndFixAfterRemoval(w):
    z = w
    while !isRoot(z):
        z = w.parent() # 루트까지 거슬러 올라가다가
        if !rightBalance(z): # 처음 만난 밸런스 깨진 노드가 z가 된다.
            break
    if isRoot(z) and rightBalance(z): # 만약 루트까지 전부 정상이면 리턴
        return
    y = higherChild(z)
    if (y.left.height == y.right.height): # y 의 두 자식의 높이가 같으면
        if isLeft(y): # y랑 같은 쪽을 자식으로
            x = y.left
        else:
            x = y.right
    else:
        x = higherChild(y)
    b = reconstructure(x,y,z)
    if isRoot(w):
        return
    else:
        searchAndFixAfterRemoval(w.parent()) #루트까지 재귀 반복

AVL 트리의 성능

AVL 트리를 이용하여 구현된 원소 $n$개의 사전은 $O(n)$ 공간과 $O(\log n)$ 높이를 가진다.

• 3 노드를 개조하는 reconstructure 작업은 $O(1)$ 시간
• findElement는 $O(\log n)$ 시간
• insertItem, removeElement는 $O(\log n)$ 시간이 소요된다.
  • 초기의 treeSearch에 $O(\log n)$
  • 균형 복구에 $O(\log n)$