Balanced BST

are height-balanced trees that ensures nearly half of the data is located in each subtree

BST Rotations

• BST rotations restore the balance property to a tree after an insert causes a BST to be out of balance.
• Four possible rotations: L, R, LR, RL
  • Rotations are local operations
  • Rotations do not impact the broader tree
  • Rotations run in O(1) time
• Theses trees are called AVL Trees (Adelson-Velsky and Landis)

AVL Tree

• is an implementation of a balanced Binary Search Tree (BST)
• An implementation of an AVL tree starts with a BST implementation and adds two key ideas
  • Maintains the height at each node
  • Maintains the balance factor after insert and remove

AVL Insert

1. Insert at proper place
2. Check for imbalance
3. Rotate, if necessary
4. Update height

AVL Remove

B-Tree

B-Tree Insert