A splay tree does not keep track of heights and does not use any balance factors like an avl tree". explain. [5]
Answers
AVL tree
It is a balanced binary search tree. It is not perfectly balanced. Pairs of sub-trees differ in height by 1, they maintain an O(log n) search time.
Splay tree
1. It is a self-adjusting binary search tree. Every time a node of the tree is accessed for insertion, retrieval or deletion, a radical surgery is performed on the tree. The newly accessed node becomes the root of the modified tree. This ensures that the nodes which are frequently accessed do not drift away from the root and the inactive nodes get pushed further away from the root.
2. Amoritzed complexity - A splay tree can become highly unbalanced. A single access to a node of the tree may be quite expensive. But this is overcome in long sequences of accesses when there are many inexpensive cases also.
3. There is no need for heights or balance factors like AVL trees. Colours are not required like in Red-Black trees.
4. Rotations or splaying steps are used to work on the tree. There are six splaying steps.
5. It has an additional property that the recently accessed elements can be accessed again quickly.