The problem considers algorithms based on binary search trees. 12.3-5 Introducti
ID: 647436 • Letter: T
Question
The problem considers algorithms based on binary search trees.
12.3-5 Introduction to Algorithms, Third Edition
Suppose that instead of each node x keeping the attribute x.p, pointing to x's parent, it keeps x.succ, pointing to x's successor. Give pseudocode for SEARCH, INSERT, and DELETE on a binary search tree T using this representation. These procedures should operate in time O(h), where h is the height of the tree T. (Hint: You may wish to implement a subroutine that returns the parent of a node.)
Explanation / Answer
BST(T[root], value) {
current =root
if(value==current)
value found at root
else if(value<current)
if current->left=null
value not in tree
else
BST(T[current->left,value)
else if(value>current)
if current->right=null
value not in tree
else
BST(T[current->right,value)
}
INSERT
BSTInsert(T[root],Value)
{if (root==null)
T[root]=value
else
current=root
if(value<current)
if(current->left=null)
current->left=value
else
BSTInsert(current->left,value)
if(value>current)
if(current->right=null)
current->right=value
else
BSTInsert(current->right,value)
}
DELETE
BSTDelete(T,value)
{current=root
if(current=null)
tree is empty
else Node= BSTSearch(current, value)
if(node->left=null and node->right=null)
if(value<node->parent)
node->parent->left=null
else node->parent->right=null
end if
if(node->left=null or node->right=null)
if(value<node->parent)
node->parent->left=node->child
else
node->parent->right->node->child
end if
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.