How to add, delete, check and modify binary search tree
What this article shares with you is about how to add, delete, check and modify the binary search tree. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article. Let's take a look at it with the editor.
The properties of binary search tree:
1. Each node has a key (key) that is used as a search basis, and all nodes have different keys.
two。 The key of the left subtree is smaller than that of the root node.
3. The key of the right subtree is greater than that of the root node.
4. Both left and right subtrees are binary search trees.
# include
Using namespace std
Template
Struct BSTreeNode
{
BSTreeNode* _ left
BSTreeNode* _ right
K _ key
V _ value
BSTreeNode (const K & key, const V & value)
: _ left (NULL)
, _ right (NULL)
, _ key (key)
, _ value (value)
{}
}
Template
< class K, class V>Class BSTree
{
Typedef BSTreeNode Node
Public:
BSTree ()
: _ root (NULL)
{}
/ * bool Insert (const K & key, const V & value)
{
If (_ root = = NULL)
{
_ root = new Node (key, value)
Return true
}
Node* parent = NULL
Node* cur = _ root
While (cur)
{
If (cur- > _ key > key)
{
Parent = cur
Cur = cur- > _ left
}
Else if (cur- > _ key
< key) { parent = cur; cur = cur->_ right
}
Else
{
Return false
}
}
If (parent- > _ key > key)
{
Parent- > _ left = new Node (key, value)
}
Else
{
Parent- > _ right = new Node (key, value)
}
Return true
}
Node* Find (const K & key)
{
Node* cur = _ root
While (cur)
{
If (cur- > _ key > key)
{
Cur = cur- > _ left
}
Else if (cur- > _ key
< key) { cur = cur->_ right
}
Else
{
Return cur
}
}
Return NULL
}
Bool Remove (const K & key)
{
If (_ root = = NULL)
{
Return false
}
Node* parent = NULL
Node* cur = _ root
While (cur)
{
If (cur- > _ key
< key) { parent = cur; cur = cur->_ right
}
Else if (cur- > _ key > key)
{
Parent = cur
Cur = cur- > _ left
}
Else
{
If (cur- > _ left = = NULL) / / left is empty
{
If (cur = = _ root)
{
_ root = cur- > _ right
}
Else
{
If (parent- > _ left = = cur)
{
Parent- > _ left = cur- > _ right
}
Else
{
Parent- > _ right = cur- > _ right
}
}
Delete cur
}
Else if (cur- > _ right = = NULL) / / right is empty
{
If (parent = = NULL)
{
_ root = cur
}
Else
{
If (parent- > _ left = = cur)
{
Parent- > _ left = cur- > _ left
}
Else
{
Parent- > _ right = cur- > _ left
}
}
Delete cur
}
Both sides of else// are not empty.
{
Node* parent = cur
Node* left = cur- > _ right
While (left- > _ left)
{
Parent = left
Left = left- > _ left
}
Cur- > _ key = left- > _ key
Cur- > _ value = left- > _ value
If (parent- > _ left = = left)
{
Parent- > _ left = left- > _ right
}
Else
{
Parent- > _ right = left- > _ right
}
Delete left
}
Return true
}
}
Return false
} * /
Void Inorder ()
{
Node* root = _ root
_ Inorder (root)
Cout _ left)
Cout _ key _ right)
}
Bool InsertR (const K & key, const V & value)
{
Return _ InsertR (_ root, key, value)
}
Node* FindR (const K & key)
{
Return _ FindR (_ root, key)
}
Bool RemoveR (const K & key)
{
Return _ RemoveR (_ root, key)
}
Protected:
Bool _ InsertR (Node*& root, const K & key, const V & value)
{
If (root = = NULL)
{
Root = new Node (key, value)
Return true
}
If (root- > _ key > key)
{
Return _ InsertR (root- > _ left, key, value)
}
Else if (root- > _ key
< key) { return _InsertR(root->_ right, key, value)
}
Else
{
Return false
}
}
Node* _ FindR (Node* root, const K& key)
{
If (root = = NULL)
{
Return NULL
}
If (root- > _ key = = key)
{
Return root
}
If (root- > _ key > key)
{
Return _ FindR (root- > _ left, key)
}
Else if (root- > _ key
< key) { return _FindR(root->_ right, key)
}
}
Bool _ RemoveR (Node*& root, const K& key)
{
If (root = = NULL)
{
Return false
}
If (root- > _ key > key)
{
Return _ RemoveR (root- > _ left, key)
}
Else if (root- > _ key
< key) { return _RemoveR(root->_ right, key)
}
Else
{
Node* del = root
If (root- > _ left = = NULL) / / left is empty
{
Root = root- > _ right;// there is no need to consider the parent node of the deleted node, because the reference used recursively, the passed parameter is actually the left or right child of the father node.
}
Else if (root- > _ right = = NULL) / / right is empty
{
Root = root- > _ left
}
Both sides of else// are not empty.
{
Node* parent = root
Node* left = root- > _ right
While (left- > _ left)
{
Parent = left
Left = left- > _ left
}
Del = left
Root- > _ key = left- > _ key
Root- > _ value = left- > _ value
If (parent- > _ left = = left)
{
Parent- > _ left = left- > _ right
}
Else
{
Parent- > _ right = left- > _ right
}
}
Delete del
}
Return true
}
Protected:
Node* _ root
}
The above is how to add, delete, check and modify the binary search tree. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.
