Top Down Splaying

Hello everyone,

This week we will be talking about Splay Trees, a varient of binary search trees that uses some algorithms associated usually with AVL trees. In this lab, we used the BST class we coded last week to make our Splay_BST lab this week. As always, feel free to leave a comment and lets get into this.

What are AVL and Splay Trees?

Before we begin, we need to know what an AVL tree is. AVL trees are self-balancing binary search trees. AVL trees are seen as unbalanced when the height of each node in the left and right subtrees differ more than 1. AVL trees are designed to keep the worst case of operations done on the tree (such as searching) closer to O(log N), since most operations of binary search trees are dependent on the height of the tree. AVL trees balance themselves automatically when operations such as insert() and remove() are called, using a technique called "rotation". I suggest doing your own personal study on rotation as it is a tricky topic to understand, but it is used in our Splay Trees.

Now, Splay Trees are a form of binary search trees that have the most recently accessed or inserted element as the root of the tree. The idea behind Splay Trees is to have faster access times for recently used items, since they will be either at or close to the top of the tree. Downside of Splay Trees is that operations like insert and remove will be a bit slower, as the tree needs to be restructured every time it is splayed.

The Implementation

Our Splay_BST class will be inherited from our BST class, since Splay Trees IS-A binary search tree. There are many different kinds of implementations of a Splay Tree out there. What was different about this lab is that we were given the pseudo code of the splay() algorithm and we had to write the code for it.

The algorithm we had to code up utilizes Top-Down Splaying, which essentially is splaying from the top of the tree to the bottom. There is another method called Bottom-Up Splaying, but it is more difficult to code than Top-Down Splaying. 

The splay() algorithm utilizes the same kind of rotation as AVL trees, except we are not worry about the height of the nodes in our Splay_BST class. splay() also utilizes three kinds of trees: the main tree, and a left and right tree. The left and right trees are used in the restructuring of the tree, which is assembled at the end of the splaying. 

Now, splay() will be a private method that is used in operations such as insert(), remove(), and find(). The reason for it is that the user does not need to know or use splay(), and the functions I just listed need to call splay() to insure that our Splay Tree stays as a Splay Tree.

Lab Questions

Q: How can you tell if splaying has resulted in any benefits? What kind of experiments can you do to test for it?

A: You can probably tell if splaying has resulted in any benefits by comparing the runtimes of insert(), remove(), find() in binary search trees, AVL trees, and the Splay trees. If you were to do tests on these three trees, AVL trees and Splay trees will be somewhat close to each other since the balancing in both of them will result in worst cases being close to O(log N). However, Splay trees will be a little bit faster in tests that result in multiple accesses of the same item, since recently accessed items are at the top of the tree.

Q: Does splaying preserve tree balance according to the AVL criterion? Or any other criterion?

A: I forgot to mention this above, but Splay Trees are essentially AVL trees with another condition. AVL trees have three conditions: a structure condition (from binary search trees), an ordering condition (also from binary search trees), and the AVL balancing condition (which states that the height of each node in the left and right subtrees differ by at most 1). Splay Trees just add one more condition to AVL trees, which is the Splay condition (the most recently inserted or accessed node is at the root of the tree). Since Splay Trees just add one more condition to AVL trees, and the fact that Splay Trees IS-A AVL tree, then splaying should preserve tree balance according to the AVL criterion.

Q: Since find() and contains() will trigger splaying, they cannot be const methods anymore.

A: This is essentially true because since splaying modifies the tree object itself and const methods do not allow the modification of the object calling the method, it will always result in compiler errors.

Conclusion

The lab was focused discovering how Splay Trees operate, using inheritance on generics, and getting a feel of implementing an algorithm for clients (something that is done in the world of software). In short, Splay Trees are great for fast access of recently used items. The downside of Splay trees is that there will be a little more overhead in some operations due to splaying. Hope you guys enjoyed reading about Splay Trees and such. Leave a comment if you like and thank you for reading!