AVL Trees

What we have learned so far:

• BSTs store ordered data linearly
• BST best case: $\Theta(\ln(n))$
• BST worst case: $\Theta(n)$

Given an unlanaced BST, we can apply a set of rotations to balance the tree.

Left heavy tree Right heavy tree

Find the height of a node

Height of a tree is the height of the root node.

Definition: AVL tree

A BST is called to be AVL if

• the difference of left and right subtrees $|h_R - h_L| \le 1$
• the

• Upper bound of perfect binary tree
• Lower bound

The behaviour of the lowest bound is actually a Fibonacci sequenc4 of numbers:

• Worst case AVL tree
• $$F(h) = F(h-1) + F(h-2) + 1$$

Approximate value: $F(h) \approx 1.8944 \phi ^h - 1$ where $\phi\approx 1.6180$

Maintaining the balance

• left-left or right-right imblanaced --> requires single rotation: promote the middle node, right-right rotate

• left-right or right-left (zig-zag) imbalanced --> requires double rotation:

  Notes:

• Balancing the tree for insertion (both cases) are $\Theta(1)$.

• Insertions is $\Theta(\ln(n))$

• For erasing an element, balencing can be $\Theta(h)$ in the worst case.

• for eraing, you need to balance using the same left-left/right-right or zig-zag imbalance, but you need to chech the parants to see if they are imblanaced or not.

Implementation

Maintaining balance

Case 1:

AVL_node<Type> *b = left(),
               *BR = b->right;
b->right_tree() =

Case 2:

AVL_node<Type> *b = left(),
               *d = b->right(),
               *DL = d->left(),
               *DR = d->right();

d->left_tree = b;
d->right_tree = this;