Chapter 7. AVL 트리(AVL Tree)¶

0절. 개요

1절. AVL 트리

2절. 수선

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

4절. 코드 구현

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