BST Implementation For splay trees

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

In this assignment you’re going to implement splay trees.

BST Implementation For splay trees, you should begin by implementing a basic (unbalanced) binary search tree, with integer keys and no values (i.e., a Set data structure). Use the following node type: struct node { int key; node* left; node* right; node* parent; };

Maintaining parent pointers complicates some of the algorithms! I would suggest implementing the basic, unbalanced BST operations first, and then adding the parent pointers and making sure everything still works, and finally adding the balancing code. Of course, your code won’t pass the tests until the balancing code is correct. Implementation You must implement the following tree operations: void rotate(node* child, node* parent); // Rotation bool find(node*& root, int value); // Search node* insert(node* root, int value); // Insertion node* splay(node* t); // Splay t to root These functions should work in exactly the same way as described in class.

Note that find and insert should all do a splay step after their main operation, to rebalance the tree! (The splay function will be tested independently of them, to make sure that it works correctly on its own.) You do not need to implement removal, because it’s really hard to get right. find is a bit different than the implementation shown in class: It takes the root of the tree by reference, finds the target node, and then splays it to the root of the tree.

Thus, after a find, root->key == value and there’s no need to return the found node. Instead, it returns a bool, true if the node was found, and false otherwise. Note that if find returns false then the tree must be unchanged! rotate does not return the new parent node: because we have parent pointers, we can rewrite the tree in-place. insert does return the new root of the tree, and thus must be used like this: node* tree = ...; tree = insert(tree, 5); // Insert 5 into tree Be sure to correctly handle the case where root == nullptr (i.e., the empty tree)! When you compile, link with assign4_test.cpp (or /usr/local/class/src/assign4_test.cpp on the server).

The test runner will first test your rotate function (because if that doesn’t work correctly, nothing else will, either) and then proceed to construct a BST by inserting and finding nodes. After each operation, it will verify the tree structure, to make sure that parent pointers are lined up and such, and after every insert and find, it will check to make sure the target node has been splayed to the root. Extra credit option If you implement remove, this assignment will count for two assignments. (The current version of the test code doesn’t test for the correctness of remove; I’ll add a version to the server that does test it when I get a chance.)

Submission

Save your work in a directory on the server named cs133/assign4/.

Expert's Answer

618 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of