AVL Tree

Unbalanced trees an be transformed to a balanced one using structural rotation: an operation on a binary tree that change the tree's structure without affecting teh order of the elements (as read in by an in-order traversal).

• Is often employed to balance two branches of different epths.
• One node i shifted up, another is shifted down, and some of the remaining nodes may be shifted to ensure the tree is a binary tree.
• Structural rotations change the heightof the tree by moving up larger subtrees.

Right Rotation

    7
   /
  5
 /
3

The grandparent (root) is not balanced so we must push 7 to the right of 5 to restore balnace.

  5
 / \
3   7

• Noice that the violation of the balancep ropertywas caused by the left child's left subtree. The solution is a single right rotation ot bring the parent node (median value) above the grandparent (high value).
• It gets more tricky if the parent node has a right child. Then you would have to move the right child to another place.

Node<T> rightRotation(Node<T> root) {
	Node<T> child = root.left; 
	root.left = child.right;
	child.right = root;
	return child; // new root
}

There is a constant number of assignments, so time complexity is O(1).

Left rotation

From the perspective of the grandparent node, the problem was caused in the right child's right subtree. The solution is a (single) left rotation to bring hte parent node above the grandparent.

Node<T> leftRotation(Node<T> root) {
	Node<T> child = root.right;
	root.right = child.left;
	child.left = root;
	return child; 
}
## Double rotation

3
 \
  7
 /
5 

We must perform a right rotation for 5 and 7, and then a left rotation. This is called a (double) right-left rotation.

• From the perspective of the grandparent node, the problem was caused in the right child's left subtree. The solution is a (single) left rotation to bring hte parent node above the grandparent.

A (double) left-right rotation is done when:

• the problem is cused by the left child's right subtree.

When to rotate

The balance factor indiciates which directino to rotate. If the grandparent and the child have a positive bf, there must be a right rotation. If the grandparent and the child have a negative bf, there must be a left rotation.

The the grandparent has a negative bf but the child has a positive bf, then there must be a right-left rotation. The the grandparent has a positive bf but the child has a negative bf, then there must be a right-left rotation.

AVL Tree Explained

AVL is named after its inventors. It is a self-balancing binary search tree that maitains the height property (and BST order property) usings tructural rotations.

• Insertion and deletion are similar to reguar binary search trees. Then, it performs post-processing structural rotations to restore the balance fo any portions of the tree that have been adversely affected.

Insertion

• Insert the item
• Start with the newest node, go up to udpate heights
• If you find a node that has become unbalanced, do a rotation.
• Rebalnacing reduces the height of a subtree by 1, so there is no need to propagate up. Only one adjustmet is needed at most becaues the tree was previously balanced before the insert.
• It takes O(lgN) to insert and O(1) to rebalance.

Removal

• Remove the item
• Start with the parent of the deleted node, go up to update heights.
• As you go up from the deleted node to update heights, rebalance them as needed.
• Reotations may reduce the height of a subtree, causing further imbalances, so you may have to do more than one rebalancing operations
• Since you need to travel from the deleted node upwards, you will perform O(lgn) rotations.
• O(lgn) to remove and O(lgn) to rebalance.

Implement these operations recursively. You must store the height of each node. As you insert/remove you must travel upwards towards the root to update ancestor's height.