Data Structure in C++ In this assignment, you\'re going to implement splay trees

Question

Data Structure in C++

In this assignment, you're going to implement splay trees, and then re-use some of your code from assignment 1 to create a tree register machine, a machine with four registers whose values are search trees. Implement AVL trees (with parent pointers) Implement it as a binary search tree 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; 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*& find(node*& root, int value);//Search void insert(node*& root, int value);//Insertion void remove(node*& root, int value);//Deletion void print(std::ostream & out, node* root);//Print node* merge(node* t1, node* t2);//Tree-merge bool check(node* root); Check tree for correctness Be sure to correctly handle the case where root == nullptr (i.e.. the empty tree)! Depending on how you feel about references vs. pointers, you might prefer to change the (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 in order 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... Built an interpreter for a tree register machine supporting the following commands: clear r Reset r to contain the empty tree insert v r Insert the value v into the tree in register r remove v r Remove the value v from register r. if it exists merge r1 r2 r Merge trees in r1 and r2 into register r test v r Print TRUE if visa in is tree. FALSE otherwise 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 your tree implementation.

Explanation / Answer

This code can be used for AVL Tree implementation. You can use this code to implement the Tree Register machine.

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

unsigned char height(node* p)
{
return p?p->height:0;
}

int bfactor(node* p)
{
return height(p->right)-height(p->left);
}

void display(node *ptr, int level)
{
int i;
if (ptr!=NULL)
{
display(ptr->right, level + 1);
printf(" ");
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->left, level + 1);
}
}

bool check(node *root)
{
   int height = bfactor(root);
   if(height==0 || height==1)
       return true;
   else
       return false;
}
void fixheight(node* p)
{
unsigned char hl = height(p->left);
unsigned char hr = height(p->right);
p->height = (hl>hr?hl:hr)+1;
}

node* rotateright(node* p)
{
node* q = p->left;
p->left = q->right;
q->right = p;
fixheight(p);
fixheight(q);
return q;
}

node* rotateleft(node* q)
{
node* p = q->right;
q->right = p->left;
p->left = q;
fixheight(q);
fixheight(p);
return p;
}

node* balance(node* p) // balancing the p node
{
fixheight(p);
if( bfactor(p)==2 )
{
if( bfactor(p->right) < 0 )
p->right = rotateright(p->right);
return rotateleft(p);
}
if( bfactor(p)==-2 )
{
if( bfactor(p->left) > 0 )
p->left = rotateleft(p->left);
return rotateright(p);
}
return p; // balancing is not required
}

node* insert(node* p, int k) // insert k key in a tree with p root
{
if( !p ) return new node(k);
if( k<p->key )
p->left = insert(p->left,k);
else
p->right = insert(p->right,k);
return balance(p);
}

node* findmin(node* p) // find a node with minimal key in a p tree
{
return p->left?findmin(p->left):p;
}

node* removemin(node* p) // deleting a node with minimal key from a p tree
{
if( p->left==0 )
return p->right;
p->left = removemin(p->left);
return balance(p);
}

node* remove(node* p, int k) // deleting k key from p tree
{
if( !p ) return 0;
if( k < p->key )
p->left = remove(p->left,k);
else if( k > p->key )
p->right = remove(p->right,k);  
else // k == p->key
{
node* q = p->left;
node* r = p->right;
delete p;
if( !r ) return q;
node* min = findmin®;
min->right = removemin®;
min->left = q;
return balance(min);
}
return balance(p);
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.