bst 刪除節點

Problem statement:

問題陳述：

Given a BST and a value x, write a function to delete the nodes having values greater than or equal to x. The function will return the modified root.

給定一個BST和一個值x ，編寫一個函數刪除值大于或等于x的節點 。 該函數將返回修改后的根。

Example:

例：

Input BST
8
/  \
4    10
/ \   / \
3   5  9  11
Input X:  10
After deletion:
8
/  \
4    9
/ \   
3   5  

Solution:

解：

Basic properties of BST:

BST的基本屬性：

1. All node values are distinct.

   所有節點值都是不同的。

2. The left child node is always smaller than the root & right child node is always greater than the root.

   左子節點始終小于根節點，右子節點始終大于根節點。

Thus it's clear whenever a root has a value greater than or equal to the input value X, the entire right subtree and root need to be deleted, but not the left one.

因此，很明顯，只要根的值大于或等于輸入值X ，就需要刪除整個右子樹和根，而不必刪除左子樹和根。

Algorithm:

算法：

FUNCTION buildTree (root,X)
IF (root==NULL)
Return NULL;
END IF
IF (root->data is equal to X)
return root->left; //returning the left subtree basically
ELSE IF(root->data>key)
//recur for the left subtree since left subtree may also have nodes 
//that need to be deleted due to greater or equal values
return buildTree(root->left, X); 
ELSE
//root is not at all to be deleted, same for left subtree, 
//recursively process right subtree
root->right=buildTree(root->right, X);
return root;
END FUNCTION

The above function actually builds the tree deleting the nodes having greater and equal value than X.

上面的函數實際上是在構建樹，刪除值大于和等于X的節點。

Example with Explanation:

解釋示例：

Nodes are represented by respected values for better understanding
8
/  \
4    10
/ \   / \
3   5  9  11
Input X:  10
At main we callbuildTree (8, 10)
------------------------------------------------
buildTree (8, 10)
root not NULL
8<10
Thus root->left= 8->left
root->right=buildTree (8->right, 10) //buildTree (10, 10)
------------------------------------------------
buildTree (10, 10)
root not NULL
10==10
Thus return root->left= 10->left=9
------------------------------------------------
Hence At buildTree (8, 10)
Thus root->left= 8->left
root->right=9 (9 is the root to the remaining subtree which is NULL here luckily)
So the tree actually becomes
8
/ \
4     9
/ \ 
3   5 

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
class Node{
public:             
int data;           //value
Node *left;    //pointer to left child
Node *right;   //pointer to right child
};
// creating new node
Node* newnode(int data)  
{ 
Node* node = (Node*)malloc(sizeof(Node)); 
node->data = data; 
node->left = NULL; 
node->right = NULL; 
return(node); 
}
Node* buildTree(Node* root,int key){
if(!root)
return NULL;
if(root->data==key){
return root->left; //only left subtree not deleted
}
else if(root->data>key)
return buildTree(root->left,key); //recur for left subtree
else{
//root not deleted
//left subtree not deleted
//buld right subtree
root->right=buildTree(root->right,key); 
return root;
}
}
Node* deleteNode(Node* root, int key)
{
root=buildTree(root,key);
return root; 
}
void levelwisedisplay(Node *root)
{
//to display the tree level wise
queue<Node*> q;
Node* temp;
int count=0;
q.push(root);
q.push(NULL);
while(!q.empty()){
temp=q.front();
q.pop();
if(temp==NULL){
if(!q.empty())
q.push(NULL);
cout<<"\nend of level "<<count++<<endl;
}
else{
cout<<temp->data<<" ";
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
return ;
}
int main(){
cout<<"tree is built as per example\n";
Node *root=newnode(8); 
root->left= newnode(4); 
root->right= newnode(10); 
root->right->right=newnode(11);
root->right->left=newnode(9);
root->left->left=newnode(3); 
root->left->right=newnode(5);
printf("Displaying level wise\n");
levelwisedisplay(root);
root=deleteNode(root,10);//as per example
printf("after deleting nodes greater or equal to 10\n");
levelwisedisplay(root);
return 0;
}

Output

輸出量

tree is built as per example
Displaying level wise
8      
end of level 0
4 10   
end of level 1
3 5 9 11      
end of level 2
after deleting nodes greater or equal to 10
8      
end of level 0
4 9    
end of level 1
3 5    
end of level 2 

翻譯自: https://www.includehelp.com/icp/delete-nodes-greater-than-or-equal-to-k-in-a-bst.aspx

bst 刪除節點