AVL Tree 01. AVL Tree 설명 및 의사코드

AVL Tree

기본적인 구조는 BST와 유사

• 러시아 수학자 G. M. Adelson-Velskii와 E. M. Landis 의 이름을 따서 만든 트리

AVL 트리를 사용하는 이유

• BST를 사용하는 경우, 최악의 경우 탐색의 시간복잡도가 O(N)까지 갈 수 있음

• AVL의 Balancing을 사용하여 탐색의 시간복잡도를 O(lg N)으로 줄임

• AVL 트리는 각각의 노드들에서 +1, 0, -1의 balance factor를 가짐

AVL 트리의 삽입 과정

Left of Left

root의 balance factor가 +2 이므로 right rotation을 시행

• Simple right rotation

• Complex right rotation

Right of Right

root의 balance factor가 -2 이므로 left rotation을 시행

• Simple left rotation

• Complex left rotation

Right of Left

• Simple double rotation right

• Complex double rotation right

Left of Right

• Simple double rotation right

• Complex double rotation right

AVL ADT

삽입 (insert)

function AVLInsert (root, newData):
  if subtree is empty:
    insert newData as root
    return root
  if newData < root:
    AVLInsert (left subtree, newData)
    if left subtree is taller:
      leftBalance (root)
  else:
    AVLInsert (right subtree, newData)
    if right subtree is taller:
      rightBalance (root)
  return root

삭제 (Delete)

function AVLDelete (root, dltKey, success):
  if subtree is empty:
    set success to false
    return null
  if dltKey < root:
    set left subtree to AVLDelete (left subtree, dltKey, success)
    if tree is shorter:
      set root to deleteRightBalance (root)
  else if dltKey > root:
    set right subtree to AVLDelete (right subtree, dltKey, success)
    if tree is shorter:
      set root to deleteLeftBalance (root)
  else:
    save root
    if no right subtree:
      set success to true
      return left subtree
    else if no left subtree:
      set success to true
      return right subtree
    else:
      find largest node on left subtree
      save largest key
      copy data in largest to root
      set left subtree to AVLDelete (left subtree, largest key, success)
      if tree is shorter:
        set root to deleteRightBalance (root)
  return root

삽입 중 균형 (Balance)

function leftBalance (root):
  if left tree is higher:
    rotateRight (root)
  else:
    rotateLeft (left subtree)
    rotateRight (root)

functino rightBalance (root):
  if right tree is higher:
    rotateLeft (root)
  else:
    rotateRight (right subtree)
    rotateLeft (root)

회전 (Rotate)

function rotateRight (root):
  exchange left subtree with right subtree of left subtree
  make left subtree a new root

function rotateLeft (root):
  exchange right subtree with left subtree of right subtree
  make right subtree a new root

삭제 중 균형 (Delete Balance)

function deleteRightBalance (root):
  if tree is not balanced:
    set rightOfRight to right subtree
    if left of rightOfRight is higher:
      set leftOfRight to left subtree of rightOfRight
      set right subtree to rotateRight (rightOfRight)
      set root to rotateLeft (root)
    else:
      set root to rotateLeft (root)
  return root