AVL Trees

What is an AVL tree? §

• An AVL tree is a self-balancing data structure that adheres to the same guidelines as a Binary Search Tree. However, the AVL tree has additional properties:
  • Height of left and right subtree can differ no greater than 1
• BalanceFactor(X) = Height(RightSubtree(x) - Height(LeftSubtree(X))

Rotations: §

Let x be our offending node.

If the tree is left-heavy If the left child of x is right-heavy perform a LR @ x’s left child. perform a RR @ x else perform a RR @ x

If the tree is right-heavy If the right child of x is left-heavy perform a RR @ x’s right child perform a LR @ x else perform a LR @ x

Code Implementation: §

node *rotateLeft(node *x)
{
	node *newRoot, *orphan;

	// x's right child becomes the new root. 
	newRoot = x->right 

	// x's right child is about to take x as its left child.
	// as such we must store x's left child as it is orphaned
	orphan = newRoot->left;

	// x moves down and to the left to become the left child of the new root. 
	newRoot->left = x; 

	// Now x, having lost its right child, adopts any orphan that might exist. Notice that if an oprhan is NULL, we end up setting x's right child to NULL. 
	x->right = orphan; 

	return newRoot; 
}

Insertion: §

1. Insert BST Style.
2. Fix bad balance-factors as we go.

Deletion: §

1. Delete node BST Style.
2. Perform rotations to fix bad balance-factors.

Searching: §

1. Search for the value BST Style.

Runtime considerations §

Insertion: O(log n)

#evergreen