C++ or Java Pruning BSTs : write a method/function that prunes a BST by “deletin

Question

C++ or 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

program :

#include <iostream>
#include<cstdio>
using namespace std;
struct Node{
int data;
struct Node *left;
struct Node *right;
};

Node* FindMin(Node* root){
while(root->left != NULL) root = root->left;
return root;
}

struct Node* Delete(struct Node *root, int data){
if(root == NULL) return root;
else if(data < root->data) root->left = Delete(root->left,data);
else if(data > root->data) root->right = Delete(root->right, data);
else {
if(root->left == NULL && root->right == NULL){
delete root;
root = NULL;
  } else if(root->left == NULL){
struct Node *temp = root;
root = root->right;
delete temp;
} else if(root->right == NULL){
struct Node *temp = root;
root = root->left;
delete temp;
} else{
struct Node *temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}
return root;
}

void Inorder(Node *root){
if(root == NULL) return;
Inorder(root->left);
printf("%d ",root->data);
Inorder(root->right);
}

Node* Insert(Node *root, char data){
if(root == NULL){
root = new Node();
root->data = data;
root->left = root->right = NULL;
} else if(data <= root->data){
root->left = Insert(root->left, data);
} else {
root->right = Insert(root->right, data);
}
return root;
}

int main ()
{
Node* root = NULL;
root = Insert(root, 5);
root = Insert(root, 10);
root = Insert(root, 3);
root = Insert(root, 4);
root = Insert(root, 1);
root = Insert(root, 11);
  root = Delete(root, 5);
  z cout<<"Inorder: ";
Inorder(root);
cout<<" ";
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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