Since a binary search tree with N nodes has N + 1 null references, half the spac
ID: 3551930 • Letter: S
Question
Since a binary search tree with N nodes has N + 1 null references, half the space allocated in a binary search tree for link information is wasted. Suppose that if a node has a null left child, we make its left child link to its inorder predecessor, and if a node has a null right child, we make its right child link to its inorder successor. This is known as a threaded tree, and the extra links are called threads.
a. How can we distinguish threads from real children links?
b. Design the routines to perform insertion and deletion into a tree threaded in the manner described above.
c. What is the advantage of using threaded trees?
Explanation / Answer
1. One can distinguish threads from real child links by storing bits to the node. Or one can also detect cycle during tree traversal.
2.
Insertion routine:
int thread_insert(NodeTree* tree, int data){
if( tree->root == NULL)
tree->root = make_node(data);
else{
struct Node* it = tree->root, *q;
int dir;
while(1){
dir = it->data < data;
if(it->data == data)
return 0;
else if (dir==1 && it->thread==1)
break;
else if(it->link[dir] == NULL)
break;
it = it->link[dir];
}
q = make_node(data);
if(dir == 1){
q->link[1] = it->link[1];
it->thread = 0;
}
else
q->link[1] = it;
it->link[dir] = q;
}
return 1;
}
Deletion routine:
int thread_remove(struct NodeTree* tree, int data)
{
if(tree->root != NULL){
struct Node head = {0};
struct Node* it = &head;
struct Node* q, *p, *f=NULL;
int dir = 1;
it->link[1] = tree->root;
while( it->link[dir] != NULL){
if(dir==1 && it->thread==1)
break;
p = it;
it = it->link[dir];
dir = it->data <= data;
if(it->data == data)
f= it;
}
if(f!=NULL){
q = it->link[it->link[0] == NULL];
dir = p->link[1] == it;
f->data = it->data;
if(p==q)
p->link[0] = NULL;
else if(it->link[0] ==NULL && it->thread){
p->thread = 1;
p->link[1] = it->link[1];
}
else if(it->link[0] == NULL)
p->link[dir] = q;
else {
q->thread = it->thread;
q->link[1] = it->link[1];
p->link[dir] = q;
}
}
tree->root = head.link[1];
}
return 1;
}
3. Advantages:
a). By doing threading we avoid the recursive method of traversing a Tree , which makes use of stack and consumes a lot of memory and time .
b) . The node can keep record of its root .
c) We can efficiently determine predecessor and successor nodes starting from any node.