CITS2200 - Lecture 16

← Back to Home

CITS2200 - Lecture 15
AVL Trees - Slides

AVL Trees

• An AVL tree is a binary search tree (BST)
• Every internal nodes’ children can only differ in height by at most 1
  • If this condition is not met, the tree is unbalanced
• Height of an AVL tree is $O(\log n)$

⚡ Named after inventors Adelson-Velsky & Landis (1962)

---

Insertion & Imbalance

• Always done by expanding an external node
• When a node is added, it may lead to the tree being unbalanced
• The tree then needs to be restructured

• The tree on the right is unbalanced:
  • Node 78: $h=4$, but Node 17: $h=2$
  • $h$ difference $\ge 1$ between siblings
  • $\therefore$ tree is unbalanced

Restructuring process:

• Identify problem nodes:
  • $z$ $-$ highest unbalanced node → node 78
  • $y$ $-$ child of $z$ with the larger height → node 50
  • $x$ $-$ child of $y$ with the larger height → node 62

Trinode Restructuring

• To restore balance, we perform rotations
• Let $(a,b,c)$ be an inorder listing of $x,y,z$
  • Inorder listing $-$ $a<b<c$ → Left-Root-Right
  • $b$ node will become parent node for $a$ and $c$
• Two main scenarios:
  • Single rotation $-$ $x,y,z$ form a straight line
    Left rotation about $a$:
    
  • Double rotation $-$ $x,y,z$ form a zig-zag
• Only one rebalancing step is required for insertion

---

Removal

Initial step $-$ do regular BST deletion:

• Case A: Node is a leaf → delete node
• Case B: Node has one child → replace node with child
• Case C: Node has two children
  • Replace node with in-order successor
    • In-order successor is smallest node in right subtree for BST
  • Then, delete that successor

Retracing and Rebalancing

• After node is gone, retrace path from deleted node’s parent up to root
• Check each nodes balance factor BF:
  $\text{BF}=\text{height(left)}-\text{height(right)}$
• If $|\text{BF}|>1$, the node is unbalanced
• Four rotations we can perform to fix this, as seen in the table below ↓

AVL Tree Performance

• Single restructure $-$ $O(1)$
• Searching $-$ $O(\log n)$
• Insertion $-$ $O(\log n)$
• Removal $-$ $O(\log n)$

---

CITS2200 - Lecture 17