Performance of Binary Search Tree (BST) is proportional to its height O(h). To achieve best performance, it is important to balance the tree. AVL tree, Red-Black tree and Splash tree are popular self-balacing BSTs. Like AVL tree, Splay tree and Red-Black tree are self-balancing trees which provide O(Log n) search performance.
Red-Black tree
Red-Black tree is preferred over AVL trees when there is high frequency of insert/delete operations compared to search as AVL tree balancing (rotation) is expensive. Red-black tree balances itself on insert and delete operations satisfying the following conditions.
- Each node is either red or black. Usually color information is stored in a bit in the node.
- Root and leaf nodes are black.
- No two red nodes to be adjacent, meaning, a red node cannot have a parent or children which are red.
- Every path from root to leaf nodes have same number of black nodes.
Splay tree
Splay tree provides performance better than O(log n) by optimizing the placement of nodes. It makes the recently accessed nodes in the top of the tree and hence providing better performance. It’s suitable for cases where there are large number of nodes but only few of them are accessed frequently.