5) Recall the in class discussions on implementing relations as various data str
ID: 3585455 • Letter: 5
Question
5) Recall the in class discussions on implementing relations as various data structures, such as linked lists, hash tables, and vectors. Define an implementation of a relation using a binary search tree as the datastructure containing the pairs (a,b). Your BST does NOT have to be balanced, but it must maintain the search property. Assume you weigh the tree based off of the domain (a) value, and that ties will always go to the left child (i.e. if (a,b) is a node in our tree, and (a,c) is inserted, it will be placed somewhere in the left subtree of (a.b). Define insert, delete, and lookup functions for your BST relation.
Explanation / Answer
Ans
Insert
Node * insert(node * r , int k)
{
if(! r)
return newNode(k);
if(k<= r->k)
{
r->left = insert (r->left , k);
if( r->left->val > r->val)
r = rightrotate (r);
}
else
r -> right = insert( r -> right , key);
if(r->right->val > r->val)
r = leftrotate(r);
}
return r;
}
Delete
Node * delNode(Node * r, int k)
{
if (r == NULL)
return r;
if (k < r->k)
r->left = delNode(r->left, k);
else if (k > r->k)
r->right = delNode(r->right, k);
else if (r->left == NULL)
{
Node * temp = r->right;
del(r);
r = temp;
}
else if (r->right == NULL)
{
Node *temp = r->left;
del(r);
r = temp;
}
else if (r->left->val < r->right->val)
{
r = leftRotate(r);
r->left = delNode(r->left, k);
}
else
{
r = rightRotate(r);
r->right = delNode(r->right, k);
}
return r;
}
Lookup
public boolean look(k) {
return look(r, key);
}
private boolean look(node<K> n,k) {
if (n == null) {
return false;
}
if (n.getk().equals(k)) {
return true;
}
if (key.compareTo(n.getk()) < 0) {
return look(n.getLeft(), k);
}
else {
return look(n.getRight(), k);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.