Splay tree

Coding Assignment 3

CSC 330: Advanced Data Structures, Spring 2019 Released Monday, April 15, 2019

Due on Canvas on Wednesday, May 1, at 11:59pm

Overview

In this assignment, you’ll implement another variant of a height-balancing tree known as a splay tree. The assignment will also give you an opportunity to work with Java inheritance; in particular, the base code that you’ll amend is structured so that your SplayTree class extends from an abstract class called HeightBalancingTree, which gives a general template for how a height-balancing tree should be defined.

As always, please carefully read the entire write-up before you begin coding your submission.

Splay Trees

As mentioned above, a splay tree is another example of a height-balancing tree — a binary search tree that, upon either an insertion or deletion, modifies the tree through a sequence of rotations in order to reduce the overall height of the tree.

However, splay trees differ from the other height-balancing trees we’ve seen (AVL trees, red-black trees) in terms of the type of guarantees that they provide. In particular, recall that both AVL trees and red-black trees maintain the property that after any insertion or deletion, the height of the tree is O(log n), where n is the number of elements in the tree. Splay trees unfortunately do not provide this (fairly strong) guarantee; namely, it is possible for the height of a splay tree to become greater than O(log n) over a sequence of insertions and deletions.

Instead, splay trees provide a slightly weaker (though still meaningful) guarantee known as an amortized bound, which is essentially just a bound on the average time of a single opera- tion over the course of several operations. In the context of splay trees, one can show that over the course of, say, n insertions to build a tree with n elements, the average time of each of these operations is O(log n) (but again, keeping in mind it is possible for any single one of these operations to take much longer than this).

Showing this guarantee is beyond the scope of this course (although the details of the analy- sis can be found in your textbook). Instead, in this assignment, we will just be in interested

1

r splay:

N

root root

2

1 1

2

l splay:

N

1

2

rr splay:

N

N

N

ll splay:

rl splay:

1

2

N

lr splay:

Figure 1: Illustration of the six possible cases for on a given step of a splay operation.

in writing an implementation of a splay tree in Java that is structured using inheritance.

Splay Tree Insertions and Deletions

To insert or delete an element from the tree, splay trees use the same approach as the other height-balancing trees we’ve discussed in class — first we insert/deletion an element using standard BST procedures, and then perform a “height-fixing” procedure that rebalances the tree. Thus, what distinguishes each of these height-balancing trees from one another is how they define their height-fixing procedures.

To fix the tree after both insertions and deletions, splay trees use (as the name suggests) a key subroutine known as a splay. A splay procedure begins at some node N, and then performs a series of rotations until N is the new root of the tree. In particular, the splay subroutine repeatedly applies one of the following six operations on N while it is not yet the root of the tree (each case is also illustrated in Figure 1):

• Case 1 (r splay): If N is currently the left child the root, then perform a right rotation on the root of the tree.

• Case 2 (l splay): If N is currently the right child the root, then perform a left rotation on the root of the tree.

2

• Case 3 (rr splay): If N is currently the left child of its parent, and N’s parent is the left child of N’s grandparent, then first perform a right rotation on N’s grandparent, and then perform and right rotation on N’s parent.

• Case 4 (ll splay): If N is currently the right child of its parent, and N’s parent is the right child of N’s grandparent, then first perform a left rotation on N’s grandparent, and then perform and left rotation on N’s parent.

• Case 5 (rl splay): If N is currently the left child of its parent, and N’s parent is the right child of N’s grandparent, then first perform a right rotation on N’s parent, and then perform and left rotation on N’s grandparent.

• Case 6 (lr splay): If N is currently the right child of its parent, and N’s parent is the left child of N’s grandparent, then first perform a left rotation on N’s parent, and then perform and right rotation on N’s grandparent.

A couple things to note: a) since either an r or l splay will be performed if N is a child of the root, it’s safe for us to assume that N has a grandparent in the other cases, and b) note that the order in which the parent and grandparent are rotated is switched between rr/ll splays versus rl/lr splays, i.e., rr/ll splays rotate the grandparent first, whereas rl/lr splays rotate the parent first.

Now that we’ve defined this splay operation, defining the fixing procedure for both insertions and deletions is straightforward. For insertions, we simply run the splay procedure on the newly inserted node. For deletions, we splay the parent of the node that was deleted from the tree (noting in the case where the node we removed was the node originally the node containing the successor of the element that was deleted, the node we splay is the parent of the successor).

API Details

The Java project you will amend contains five files, which form a small inheritance hierarchy (illustrated in Figure 2). In particular, the files included in the project are as follows:

• Collection.java: An interface that defines a (very general) template for a data struc- ture containing a collection of elements (i.e., it must support insertions, deletions, and searches). There are no changes you need to make to this file.

• HeightBalancingTree.java: An abstract class that implements the Collection in- terface by giving a template for how a height-balancing tree class should be imple- mented (as well as explicitly defining methods that are common subroutines for all height-balancing trees, e.g., finding a node or performing a rotation).

• RedBlackTree.java: A class that implements a red-black tree data structure by ex- tending from the abstract class HeightBalancingTree. There are no changes you need to make to this file.

3

Collection (interface)

HeightBalancedTree (abstract class)

RedBlackTree SplayTree

Figure 2: Inheritance hierarchy implemented in the assignment.

• SplayTree.java: A class that implements a splay tree data structure by extending from the abstract class HeightBalancingTree.

• TestHeightBalTree.java: A test file that will tests the correctness of the overall implementation of the RedBlackTree class (which is designed to test your implemen- tations of the rotation methods you write in HeightBalancingTree), as well the cor- rectness of your splay tree implementation. There are no changes you need to make to this file.

As in the previous assignment, many methods are already written for you, so please famil- iarize yourself with all the code in the project. In terms of the methods you must write for the assignment, in HeightBalancingTree.java you will implement:

• protected void leftRotate(Node rotRoot): Performs a left rotation on the subtree rooted at rotRoot.

• protected void rightRotate(Node rotRoot): Performs a right rotation on the sub- tree rooted at rotRoot.

In SplayTree.java, you will implement:

• public void insert(T element): Insert element into the the splay tree (implements the corresponding method declaration in Colletion.java).

• public boolean delete(T element): Remove an occurrence of element in the tree. Returns true if element was removed; returns false otherwise (also implements the corresponding method declaration in Colletion.java).

4

• protected void insertionFix(Node<T> n): Rebalance the tree after inserting node n into the tree.

• protected void deletionFix(Node<T> del, Node<T> replace, Node<T> parent): Rebalances the tree after deleting node del from tree, which was then replaced by node replace (one its children nodes); node parent points to the parent of the deleted node. Note that in the case that the node that was actually deleted from the tree was the successor of the element to be deleted (i.e., when the element to be deleted is stored at a node with two children), del will be the node containing the successor (and therefore replace will be the child node that replaced the successor, and parent is the parent of the successor.)

• private void splay(Node<T> n): Perform a splay procedure starting at node n (see the previous section for the details of the algorithm).

Comments and Tips

• The TestHeightBalTree.java file tests the correctness your trees by making sure both the in-order and pre-order traversals of your tree matches those produced by the solution code. Keep in mind that as long as your implementation satisfies the BST property, your in-order traversals should match that of the target solution (in partic- ular, the in-order traversal should be all the elements in tree given in sorted order). A matching pre-order traversal means you’ve properly implemented the methods that modify the structure of the tree (rotations, splay, etc.).

• Observe that HeightBalancedTree is written so that all missing child links, as well the parent of the root, should point to nullNode. By default, nullNode is set to be null, but a deriving class can change this (as is the case for RedBlackTree when it defines its special “sentinel” null node that is black). Thus, all checks for null links should be for nullNode (and not for just null).

• When implementing both leftRotate() and rightRotate(), be sure to properly up- date all child and parent pointers. Note that you should not try to change any pointers of nullNode (as it may be null), and also be sure to update the root when necessary.

• Your implementations of insert() and delete() in SplayTree should be similar the overriden implementations of the same methods in RedBlackTree(), so be sure to use the latter as guiding examples. On a related note, the most involved methods you’ll write should be leftRotate(), rightRotate(), and splay(). If your code for the other methods begins to look intricate, you should rethink your approach.

• Just something to observe: Although you aren’t required to understand the exact structure of the TestHeightBalTree.java, this is a good file to look at to see some of the benefits of structuring these classes to use inheritance. For example, using inheritance allows us to write one method that is capable of testing both types of trees.

5

Code Retrieval and Submission

As with Coding Assignment 3, the entire netbeans project is given as a .zip file on Canvas. To complete your assignment, please modify the given files (i.e., fill-in implementations for each method that currently says “write this method”). To submit, please submit the modi- fied project as a .zip file on Canvas.

Evaluation

Your submission will again be scored a 50 point scale. The point breakdown by category is as follows.

• Overall Approach and Code Readability [10 points]: This category will be scored based on the overall structure and approach of your implementation. For exam- ple, how readable is your code? Did you include useful comments? Can I understand (with not too much effort) the approach you took for each method?

• Method Implementation [20 points]: For this category, I will pick two of methods that you were asked to write for the assignment (for this particular assignment, I will grade one of the two rotation methods, as well as the splay() method) and do a more detailed evaluation of their implementations based on correctness, efficiency, and code readability.

• Empirical Testing [20 point; 10 points public; 10 points private]: For this category, you will receive a grade based on tests I’ll run on your code. Half of the points will come from public tests, which are included TestHeightBalTree.java. The other ten points will come from private tests.

6