5. Variations of BST #

Created Wednesday 12 February 2020

For the best insertion, deletion and other ops for a BST is O(H) i.e if we can minimize h, then we can minimize the height.

• |H~left ~- H~right~| <= 1 for all nodes.
• h = O(log(n))
• Search, insertion and deletion is O(h).

Types of balanced BSTs:

1. AVL tree - Read and implement.
2. Red-Black Tree
3. 2-4 tree