Data Structures AVL and Binary Search Trees

continue from last week

AVL Tree

BST in which every node is balanced, right heavy or left heavy.

Balance = height(left subtree) - height(right subtree)

Balance of every node should be between

-1, 0 or 1

AVL is o(___)

log n

height of an empty tree is equal to

0

operations on AVL Trees

Search, Insert and Delete

Insert

Do a TreeInsert as in BST, then verify if its still an AVL. If it’s unbalanced, we need to rebalance.

Types of rotation

Left and right rotation


Left rotation: Height of left subtree inc, height of right dec, BST order maintained

Good insert case

Balanced Preserved (insert middle then small then tall)

Bad Insert Case

Left left right or right right imbalance

how to fix left left inbalance

using right right insertion

Bad Insert case #2

Left right or Right Left

To fix RL or LR we fix it using

Double Rotation

AVL Insert Alg

1. Find spot for value

2. Hang new node
   • Search back up looking for imbalance
   • If there is an imbalance:
   case #1: Perform single rotation
   case #2: Perform double rotation
   • Done!
   (There can only be one imbalance!)