Question

When would you use a splay tree over a red black tree? A binary heap over a leftist heap?

Answer 1

There are certain advantages of the splay tree over the red-black tree as listed below:

The basic idea behind the slay tree is to bring the latest accessed node to the root node.
1. Splay tree exploits the good use of the locality of reference that is it can access the recently accessed item by O(1) complexity.

2. A splay tree is also the self-balancing tree as the red-black tree but in the splay tree, it changes the node positions even at the time of reading operations. Which can be used as an advantage in the application where the search is the most frequent operation.

3. The splay tree provides better performance then O(logn) using its node position changing strategy which is a clear advantage over the red-black tree.

Leftist heap is the version of the binary heap with a priority queue implementation. Binary heap operations are simpler for normal operations with fewer data.

As compared to a leftist heap, binary heap provides faster insertion and deletion operation.

Leftist heap provides better complexity for merge operation compared to the binary heap. So we can choose binary heap over leftist heap when Insertion and deletion is the frequent operation compared to Merger.