Data Structure in C++

AVL tree and its Register machine

I tried this homework and there are errors.

Please check my code and fix errors.

:

#include #include #include #include

struct node { int key; node* left; node* right; node* parent; int height; node(int k) {key = k; left = right = 0; height = 1;} };

int height(node* root){ return root == nullptr ? 0 : root->height; }

int bfactor(node* p){ // the balance factor of the given node. It operates with nonzero pointers only return height(p->right) - height(p->left); }

void fix_height(node* p){ int hl = height(p->left); int hr = height(p->right); p->height = (hl > hr ? hl : hr) + 1; }

node* rotateR(node* p){ node* q = p->left; p->left = q->right; q->right = p; fix_height(p); fix_height(q); return q; }

node* rotateL(node* q){ node* p = q->right; q->right = p->left; p->left = q; fix_height(q); fix_height(p); return p; }

node* balance(node* p){ fix_height(p); if(bfactor(p) == 2){ if(bfactor(p->right) right = rotateR(p->right); return rotateL(p); } if(bfactor(p) == -2){ if(bfactor(p->left) > 0) p->left = rotateL(p->left); return rotateR(p); } return p; }

node*& find(node*& root, int value){ // Search if(!root || root->key == value) return root; else if(value key) return find(root->left, value); else return find(root->right, value); }

void node::insert(node*& root, int key){ // Insertion node*& n = find(root, key); if(node==nullptr) n = new node{key, nullptr, nullptr}; }

node*& largest(node*& root) { if(!root) return root; else if(!root->right) return root; else return largest(root->right); }

node*& pred(node*& value) { if(value->left) return largest(value->left); }

void remove(node*& root, int value){ // Deletion if(!value) return; // Not found

if(!value->left && !value->right) { // No children, just remove delete value; target = nullptr; } else if(value->left) { // One left child, remove and replace with left node*& vl = value->left; delete value; value = vl; } else if(value->right) { // One child right, remove and replace with right node*& vr = value->right; delete value; value = vr; } else { // Both children, swap with predecessor node*& p = pred(root, key); std::swap(value->key, p->key); remove(p); } }

void print(std::ostream& out, node* root); // Print

node* merge(node* t1, node* t2); // Tree-merge

bool check(node* root){ // Check tree for correctness int height = bfactor(root); if(height == 0 || height == 1) return true; else return false; }

int main() { /ode* root = NULL; // Creating an empty tree

return 0; }

Part 1: AVL Trees Implement AVL trees (with parent pointers). Implement it as a binany search tr with integer keys (i.e..an ordered set). Your nodes should have type struct node int key node* left: node right; node parent int height, Other members as needed by your tree implementation Note that 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. You must implement the following tree operations node 8 find(node & root, int value Search void insert nod g root, int value); Insertion Deletion void renov node & root, int value void print(std::ostrean& out, node root Print Tree-merge node merge (node t node* t2); Check tree for correctness bool check(node root Be sure to correctly handle the case where root nullptr (ie. e empty tree. Depending on how you feel about references vs. pointers, you might prefer to change the *8 (reference to a pointer) parameters to double-pointer. A single pointer will not suffice. however. The print function is mostly for your convenience in testing your code: you can print your trees in any format you'd like, though I'd suggest using an inorder traversal, as that will print the elements of the tree in numerical order (hopefully). Likewise. the check function should return true if the tree has the correct tree structure (ordering, pointers connected correctly. etc.) To "merge two trees, you can simply insert all the nodes of one into the other, although there are more efficient ways of doing it. Part 2: Tree Register Machine Built an interpreter for a tree register machine supporting the following commands: Command Description Reset rto contain the empty tree clear r insert vr nsert the value vinto the tree in register r renove vr Remove the value vfrom register r. if it exists merge r1 r2 r Merge trees in r1 and r2 into register r Print TRUE if vis in ris tree. FALSE otherwise test vr print r Print the tree in register r As with assignment 1. your machine has 4 registers: a, b, c, d Use this to test you tree implementation