Week 10
Deletion from BSTs
Ex1: Deletion from Search Trees
New Binary Search Tree ADT
TreeLab
Ex2: Generating Values in Prefix Order
Balanced Trees
Balanced Binary Search Trees
Operations for Rebalancing
Ex3: Tree Rotations
Insertion at Root
Ex4: Insertion at Root
Randomized BST Insertion
Ex5: Randomized Insertion
Warning: Notation Change
Tree Size
Joining Two Trees
Ex6: Tree Join
Splay Trees
Real Balanced Trees
Better Balanced Binary Search Trees
AVL Trees
AVL Trees
Ex7: AVL insertion
2-3-4 Trees
2-3-4 Trees
Ex8: Insertion into 2-3-4 Tree
Produced: 4 Oct 2017