AVL Tree

• Adelson-Velsky and Landis Tree
• Height balanced Binary Search Tree
• Self balancing
• Invariants
  • Maintains BST Invariants
  • For every node: Balance Factor = -1, 0, 1
• Height with $n$ nodes $=1.44{\log }_2(n+2)\in O(\log n)$

Rotations

• Tools to rearrange tree without affecting its semantics (the meaning of the tree eg. being sorted)
• $O(1)$ time
  • Just manipulating a few pointers
• Types Rotations
  • Left Rotation
    • For the Right Right case (both children are the right children)
    • Moves the root to the left child of the middle node, middle becomes the new root
    • Image:
      • 
  • Right Rotation
    • Left left case
    • Moves the right node to the left child of the middle node, middle becomes the new root
  • Right Left Rotation
    • Right left case
    • Apply right rotation to right subtree and then left rotation to root
  • Left Right Rotation
    • Left right case
    • Apply left rotation to left subtree and then right rotation to root
• There rotations can’t fix complex trees so we need to automatically apply them when adding nodes
  • AVL Tree

Node* rotateLeft(Node* node) {
	grandchild = node->right->left;
	newParent = node->right;
	newParent->left = node;
	node->right = grandchild;
	return newParent;
}

Balance Factor

• Height(left) - Height(right)
• Rotation dependent on balance factor:

Case	Parent	Child	Rotation
Left Left	+2	+1	Right
Right Right	-2	-1	Left
Left Right	+2	-1	Left Right
Right Left	-2	+2	Right Left

Operations

Operation	Best Case	Worst Case
Searching	$O(\log n)$	$O(\log n)$
Insertion	$O(\log n)$	$O(\log n)$
Deletion	$O(\log n)$	$O(\log n)$

Operation	Max Rotations
Insertion	$O(1)$
Deletion	$O(\log n)$

• Insertion/Deletion
  • Same as BST
  • Identify the deepest node that breaks the balance factor rule, rotate, and then move up and rotate the next (through recursion)
    • Insertion has at most 1 rotation
    • Deletion can have at most h rotations
  • After, height of all nodes in search path may change (should store height values in nodes so height count is O(1) instead of O(n))
• Search

TreeNode* insert(TreeNode* root, int key) {
	// Insert
	if (root == nullptr)  
		return new TreeNode(key);
	else if (key < root->val)  
		root->left = insert(root->left, key);
	else
		root->right = insert(root->right, key);
 
	// Update height
 
	// Rebalance
	// (pseudo below)
 
	return root;
}

IF tree is right heavy
	IF tree's right subtree is left heavy
		Perform Right Left rotation 
	ELSE
		Perform Left rotation
ELSE IF tree is left heavy 
	IF tree's left subtree is right heavy
		Perform Left Right rotation 
	ELSE
		Perform Right rotation