Rebalancing Algo

[surbhitt]

Trees with self balancing properties

• fib-tree
• splay tree
• red-black tree
• avl tree

[surbhitt]

AVL tree has the best time complexity for rebalancing. It works on 4 types of imbalances *

• left left : left subtree fo the left child of a node is imbalanced
• right right : right subtree of the right child of a node is imbalanced
• left right : right subtree of the left child
• right left : left subtree of the right child

Balancing

All of them require different techniques for rebalancing *