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

$$\max(h_L,h_R) + 1$$

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

template<typename Type>
int AVL_node<Type>::height() const {
    return empty() ? -1 : ;
}

template<typename Type>
int AVL_node<Type>::insert( .. ){

}

Maintaining balance

Case 1:

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

Important: This fix does not violate BST requirement:

$F_R$ contains values such that $x > f$
$B_R$ contains values such that $b < x < f$
$B_L$ contains values such that $x < b$

Case 2:

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

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

Erase

Similart to insertion, after erasing an element, we should check for imbalances.
While insertion can only cause one imbalance, for erase we may have $O(h)$ to check for imbalances



In [ ]: