implement splay trees in c++ ONLY. Please ensure code passes test case file which i included below the instructionals. Note: other chegg exparts have gotten this wrong so please do not copy their answer over. Any other details in comments or advices is highly appreciated.

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 and no others:

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

/* test runner code on the below link*/

http://staffwww.fullcoll.edu/aclifton/cs133/files/assign4_test.cpp