Question
Hello, I need help with my data structure in c++. In this assignment youre going to implement splay trees. BST Implementation For splay trees, you
Hello, I need help with my data structure in c++.
In this assignment youre 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 wont 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 its 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 theres 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)!
Here is the link to the test function that tests the functions we need to implement.
https://staffwww.fullcoll.edu/aclifton/cs133/files/assign4_test.cpp
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started