Trees

BST

• Normal BSTs can be unbalanced. So, their find/insert/deletion complexity can go upto O(n) in worst case. So, there are variants which balance the tree after every insertion.
  • AVL Tree - Use rotations after insertion/deletion.
  • Red-Black Tree - Colors + rotations. If the tree will be seeing many insertions/deletions compared to searching, then Red-Black tree is preferred as compared to AVL Tree because Red-Black tree avoids rotations in some cases.
  • Splay Tree - The rationale behind splay trees is that the nodes which are searched more should be at the top of the tree. When a node is accessed, it is promoted to the root of the tree. So, in practical situations Splay trees perform better than AVL and Red-Black trees. The difference here is that splay trees change their structure after a Search operation too.