Chapter 7. AVL 트리(AVL Tree)

0절. 개요

AVL 트리

• 러시아 수학자 Adelson, Velskii, Landis에 의해 제안(1962년)
• 모든 노드의 왼쪽 서브 트리 높이(깊이)와 오른쪽 서브 트리 높이 차가 1 이하

1절. AVL 트리

깊이(Depth), 높이(Height)

• 이진 트리 한 노드 N에 대한 깊이(Depth)와 높이(Height) 정의

종류	설명
깊이(Depth)	루트 노드에서 노드 N까지의 간선 수
높이(Height)	노드 N에서 가장 깊은 리프 노드까지의 간선 수

균형 인수(Balance Factor)

• 이진 트리 한 노드 N에 대한 균형 인수(Balance Factor) 정의

| | | | —————————————————————————————————————————— | —————————————————————————————————————————— |

Balance Factor(N)
= Height(RightSubtree(N))- Height(LeftSubtree(N))
= Height(LeftSubtree(N))- Height(RightSubtree(N))

노드 1의 경우
Height(3) = 1
Height(6) = 3
Balance Factor(1) = Height(6) - Height(3) = 3 - 1 = 2

개념도

What is AVL Tree?

| | | | ——————————————————————————————————————————- | ——————————————————————————————————————————- |

2절. 수선

수선 ?

• 삽입, 삭제 연산 후 트리의 균형이 깨질 때 트리의 균형을 다시 맞추는 과정
• 회전(rotation) 연산 이용

수선 예시

• 균형이 깨진 서브 트리 중 가장 낮은 곳부터 수선

좌회전 수선 : 불균형 1개

좌회전 수선 : 불균형 2개

3절. 표준화 : 4가지 수선

표준화

• t = root
  • t의 4가지 서브 트리 유형에 따른 수선

유형	설명
LL	t.left.left가 가장 깊은 경우
LR	t.left.right가 가장 깊은 경우
RR	t.right.right가 가장 깊은 경우
RL	t.right.left가 가장 깊은 경우

LL

• 우회전(Right Rotation)

LR

• 좌회전 후 우회전(Left Rotation and Right Rotation)
• 타입 LL로의 변환

RR

• 좌회전(Left Rotation)

RL

• 우회전 후 좌회전(Right Rotation and Left Rotation)

4가지 유형 수선 요약

매우 긴 수선 예시

4절. 코드 구현

AVL 트리 코드 구현(파이썬)

• NIL 노드를 활용한 구현

# t = 회전 중심 노드

# AVL 노드 구현
class AVLNode:
  def __init__(self, newItem, left, right, h):
    self.item = newItem
    self.left = left
    self.right = right
    self.height = h

# AVL 트리 구현
class AVLTree:
  def __init__(self):
    self.NIL = AVLNode(None, None, None, 0)
    self.__root = self.NIL
    self.LL = 1; self.LR = 2; self.RR = 3; self.RL = 4
    self.NO_NEED = 0
    self.ILLEGAL = -1

  # 높이 반환 함수
  def height(self, node):
    return node.height

  # 좌회전
  def LeftRotation(self, t):
    childR = t.right
    childRL = childR.left
    childR.left = t
    t.right = childRL

    childR.height = max(self.height(childR.right), self.height(childR.left)) + 1
    t.height = max(self.height(t.right), self.height(t.left)) + 1
    return childR

  # 우회전
  def RightRotation(self, t):
    childL = t.left
    childLR = childL.right
    childL.right = t
    t.left = childLR

    childL.height = max(self.height(childL.right), self.height(childL.left)) + 1
    t.height = max(self.height(t.right), self.height(t.left)) + 1
    return childL

  # 수선
  def BalancingAVL(self, t, type):
    if type == self.LL:
      t = self.RightRotation(t)
    elif type == self.LR:
      t.left = self.LeftRotation(t.left)
      t = self.RightRotation(t)
    elif type == self.RR :
      t = self.LeftRotation(t)
    elif type == self.RL :
      t.right = self.RightRotation(t.right)
      t = self.LeftRotation(t)
    return t