JAVA Pruning BSTs : write a method/function that prunes a BST by “deleting” node

Question

JAVA

Pruning BSTs: write a method/function that prunes a BST by “deleting” nodes with key values out of a given range [min, max]. Since actual deletions of nodes from BST is expensive (O(h) time for BSTs of height h) and also some applications might require fast recovery of deleted nodes, we will just put “deletion marks” on those nodes instead of actually deleting them. There are two types of marks we can use to mark nodes: (1) type-I marks indicating that the marked nodes are unavailable (“deleted”); and (2) type-II marks indicating that all nodes in the subtree rooted at the marked nodes are unavailable (“deleted”). There is an O(h)-time algorithm that places no more than O(h) marks (type-I and type-II combined) in a BST of height h in order to indicate that all nodes with key values outside a given range [min, max] are unavailable. One possible application of such an algorithm is that in implementing a shopping website, we might need to use BSTs to store results of a search and facilitate fast refinement of the search results, i.e., tablets within a price range.

Explanation / Answer

//The following functionremoves all nodes having value outside the given range and returns the root of the tree:

// of modified tree

node* removeOutsideRange(node *root, int min, int max)

{

   // Base Case

   if (root == NULL)

      return NULL;

   // First fix the left and right subtrees of root

   root->left = removeOutsideRange(root->left, min, max);

   root->right = removeOutsideRange(root->right, min, max);

   // Now fix the root. There are 2 possible cases for toot

   // 1.a) Root's key is smaller than min value (root is not in range)

   if (root->key < min)

   {

       node *rChild = root->right;

       delete root;

       return rChild;

   }

   // 1.b) Root's key is greater than max value (root is not in range)

   if (root->key > max)

   {

       node *lChild = root->left;

       delete root;

       return lChild;

   }

   // 2. Root is in range

   return root;

}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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