explore Splay Trees

Splay trees are derived from the binary search tree unlike AVL Tree and Red Black Tree with the properties of self adjusting and self balancing but what makes them different from them is the property of splaying.

However the splay tree is not always balanced instead it is optimized so that the elements that have been recently accessed are quick to access again. The splay tree contains the same operations as the binary search tree i.e. insertion, deletion and searching. After every operation on the element, there’s rearrangement the entire tree so that the element which is placed at the root position of the tree.

As mentioned earlier what make it different from the binary search tree’s other variants like AVL tree and Red Black Tree is its property of Splaying.

Splaying an element is the process of bringing it to the root position by performing suitable rotation operations.

Every operation is followed by splaying.

For example, if we insert an element in the splay tree then we will follow the binary search tree insertion operation to insert the element and then splay it to bring that element on the root position. And similarly, if we search for some element then simply search the element using binary search tree search operation and then splay the tree to bring that element on the root position. Hence every time when we search an item x or insert x, it moves x to the root of the tree so that the next access of x is quick.

This property is somewhat similar in nature with stack. The stack also has the last in first out (LIFO) property in which the most recent item that is added is quickest one to access. The splay tree performs the splaying operation with the following six rotations:

1. Zig rotation

2. Zag Rotation

3. ZigZig rotation

4. ZigZag rotation

5. ZagZag rotation

6. ZagZig rotation

Splaying is the property that keeps the splay tree roughly balanced not completely balanced so to splay a node displaying steps are performed continuously and repeatedly on it until that node becomes the root position of the tree.

Now the question arises that how to decide what kind of playing step to perform so here is how it works:

· If the n is the child of the root then rotate the root in the correct direction so that n is the new root. More elaborately, if n is the left child of the root then perform the right rotation on the root or if the n is the right child of the root then perform the left rotation on the root. This operations are often referred to as Zig rotation and Zag rotation (single rotation).

· If the N node is the left child of a right child of a root then we need to perform two rotations. Let P is its parent and G is its grandparent, then it first rotates N and P right then rotates N and G left. If the node is the right child of the left child it does the opposite. It first rotates in N and P left and then N and G right. This is sometimes also referred as a ZigZag case rotation or ZagZig rotations.

· If the node is the left child of a left child of the root then also we have to perform to rotations. First G and P are rotated right and then N and P are rotated right. If the node is right child of a right child G and P are first rotated left followed by N and P being rotated left. This is known as ZigZig or ZagZag rotations.

Now that we know all the rotations we are all set to explore various other operations on splay tree.

Insert: If initially the tree is empty, then add node x as root and exit. Else insertion is done based on the binary search tree logic and then Splaying is done that moves the node to the root.

Split: This operation splits the Tree into two parts T and S at node x, such that T contains all the elements smaller than or equal to x and S contains all the elements greater than x. This is a two step process:

1. First of all, it splays x, i.e. move x to the root position.

2. Split right sub-tree from the rest of the tree.

Join: This operation joins two trees T and S such that T contains all the elements smaller than all the items in S. This is also two step process:

1. Splay the largest node in T, which will bring the largest node to the root.

2. Set the right child of the new root of T to S.

Delete: deletion of a node involves join and split operation. To delete a node,

1. Split the tree at x (node to be deleted), that breaks it into S and T.

2. Remove x from the root

3. Join the remaining part of tree.

Search: This operation in the splay tree is most interesting. Whenever any element is looked up in the tree, the splay tree rearranges the entire tree to move that element to the root of the tree, without violating the rules of binary search tree. Hence if the next access request is for the same element it is returned immediately.

This simple algorithm can provide extremely good performance in practice as the small amount of elements which are used more frequently are more likely to be found near the top of tree and are thus found quickly.

The search operation is performed in two steps:

1. Perform ordinary binary search tree operation. Let’s suppose the key is found in node x.

2. Splay the tree at node x.

All of these operations require amortized time O(log n).

Pros and Cons of a Splay Tree :

1. The main advantage of a splay tree is that they provide the best performance by keeping the most frequently accessed nodes at the top of the tree so that the elements can be accessed quickly. It is majorly used in systems like garbage collection for programming languages and cache implementation so we don’t have to go to the memory for accessing the data and the data can be accessed quickly.
2. They need less space as they don’t need to store the extra information unlike AVL trees and red black tree and this is what makes them attractive for memory sensitive programs.
3. Access (look-up) and update algorithms are conceptually easy, simple and fastest for the practical applications.
4. The biggest disadvantage of splay trees is that they can be linear, i.e. within a sequence, which will take O(n) time complexity and can be very expensive and maybe a drawback in real time applications; though it is also extremely rare case for this to occur.
5. They require more local adjustments especially during access operations. Rotating the node x to the root significantly “helps” x but “hurts” the rest of the treeAnd also the splay trees are are not completely balanced but are roughly balanced.

Applications:

A good example of this is a network router. A network router receives packets from incoming connections at a very high rate and it should have to decide very fast on which outgoing connection to send packet based on the IP address in the packet. The router needs a big mapping table that can be used to look up an IP address and find out which outgoing connection to use. If an IP address has been used once it is more expected to be used again and perhaps many times. Hence the splay trees can provide good performance in this situation.

A kind of trivial usage of splay trees is ‘recommended searches’ or a ‘text field suggestion’. It’s easy to store strings in a binary tree and splay a value when it is searched or entered.

This can be well understood by the designing of the playlist feature of the music app which enhance the access time of the recent played item. Consider 10 songs to justify your design and out of those, 3 most frequent accessed songs from it.

For this we consider 10 songs as 10 numbers. Say 18, 8, 19, 5, 9, 2, 17, 26, 4, 6.

a Binary Search Tree

1. Construct a binary search tree of this elements, first, as shown in figure.

2. Now for the 4 most frequently accessed songs we need to splay one song (node) at a time. Look-up for 8.

Node 8 is at the root position after splaying.

3. Next, search for 17.

Node 17 is at the root position after splaying.

4. Look-up 9 in the tree.

Node 9 is at the root position after splaying.

Conclusively the most frequently played songs are near to the top of the tree and can be accessed more quickly in the course of time. Henceforth, splay trees gives more efficiency if the usage pattern is uneven, since they adapt according to the usage.

Citations:

[1]: Splay trees. https://www.cs.cornell.edu/courses/cs3110/2013sp/recitations/rec08-splay/rec08.html

[2]: Data Structure Tutorials— Splay Tree with an example. http://www.btechsmartclass.com/data_structures/splay-trees.html

[3]: Splay Tree. Brilliant org. (Dec 10, 2021) — Alex Chumbley and Karleigh Moore. https://brilliant.org/wiki/splay-tree/#concept-question

[4]: Splay Trees (with implementations in C++, Java, and Python). https://algorithmtutor.com/Data-Structures/Tree/Splay-Trees/

[5]: Splay Tree — Javatpoint https://www.javatpoint.com/splay-tree

[6]: Splay Trees https://inst.eecs.berkeley.edu/~cs61bl/r//cur/balanced-search-trees/splay-trees?topic=lab27.topic&step=5&course=

[7]: Splay Trees : Splaying, Insertion and Deletion https://www.codesdope.com/course/data-structures-splay-trees/