Balanced BS Tree: AVL Tree

Agenda

  1. Motives
  2. "Balanced" binary trees
  3. Essential mechanic: rotation
  4. Out-of-balance scenarios & rotation recipes
  5. Generalized AVL rebalancing (insertion)
  6. Rebalancing on removal

1. Motives

2. "Balanced" binary trees

3. Essential mechanic: rotation

4. "Out-of-balance" scenarios & rotation recipes

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

5. Generalized AVL rebalancing (insertion)

5. Rebalancing on removal