- Self balancing BST
-
For every node difference between left and right height does not exceed 1; balance factor <= 1
- balance factor = abs(left height - right height)
Insert
- Perform normal BST Insert
- Traverse all ancestors form the inserted node
- If unbalanced check for below case
| Case | Rotation |
|---|
| left left | single rotation |
| right right | single rotation |
| left right | double rotation |
| right right | double rotation |
- While inserting you will just have to fix one ancestor
- Time complexity:
O(log n)
Delete
- While deleting you have to go up and keep checking for unbalanced