In this unit, the following four advanced data structures have been practically emphasized. These may be considered as alternative to a height balanced tree, i.e., AVL tree.

• Splay tree
• Red_Black tree
• AA_tree
• Treap

The key factors that have been discussed in this unit about the above mentioned data structures include complexity of code in terms of Big oh notation, cost involved in searching a node, the process of deletion of a node and the cost involved in inserting a node.

After going through this unit, you should be able to:

• know about Splay trees;
• know about Red-Black tree;
• know about AA-trees, and
• know about Treaps.