Binary search tree (BinarySearchTree/BSTree), also called binary sorting tree or binary search tree

Refer to the search binary tree in the figure below:

2. Operation of binary search tree

1.Find:

Start searching from the root, and go to the left subtree if it is smaller than the root, and go to the right subtree if it is larger than the root, and so on until you find the node corresponding to the key value. When you reach the empty node and you cannot find it, then this value does not exist;

2. Traversal:

The result of mid-order traversal is in ascending order. Taking the binary tree in the picture above as an example, the result of mid-order traversal is
10 25 34 48 61 73 81;

3. Insert

a. If the tree is empty, add a node directly and assign it to the root pointer;
b. The tree is not empty. The search operation is performed according to the properties of the binary search tree. If it is smaller than the root, go left. If it is larger than the root, go right. If it is empty, then this position is the insertion position of the new node. Insert the node;

4. Delete

First, find the node to be deleted. If the node does not exist, return false. If it exists, delete it according to the situation:

a. The node to be deleted has no child nodes;
b. The node to be deleted only has left child nodes;
c. The node to be deleted only has the right child node;
d. The node to be deleted has both left and right child nodes;
//The situation of a can be classified into the same category as b or c;

a, b: When the deleted node only has a left child, its left child needs to be entrusted to the parent node of the deleted node. Then the problem is that we do not know that the currently deleted node is its parent. The left child of the node is still the right child, so a judgment condition needs to be added. If it is the left child of the parent node, point the left pointer of the parent node to the left child of the deleted node.
In the same way, if it is the right child of a parent node, point the right pointer of the parent node to the left child of the deleted node, so that the node can be deleted and its left child can be managed; let’s take the following binary tree as an example ;

When we want to delete 14 or 7, 14 only has a left child and the right child is empty, so to delete 14, we need to entrust 14’s left child 13 to his parent node 10; delete 7 because he does not have left or right children. , that is, both the left and right pointers are empty, so you only need to determine whether it is the left or right child of its parent’s node. 7 is the right child of 6, so to delete 7, directly point the right pointer of 6 to the left pointer of 7 or Just use the right pointer;

c: Just refer to b. Deleting 10 is the same as the above operation;

d: When we want to delete 3 or 8, they have left and right child nodes and require special processing, so I use the replacement method;
Find the largest node in the left subtree of the deleted node, or the smallest node in the right subtree, replace it with the deleted node, and then delete the replaced node; taking deletion 3 as an example, we find the right subtree Replace the minimum node 4 of the tree with it, and then delete the node at the position of 3 after replacement;
ps: The largest node of the left subtree is on its rightmost side, and the smallest node of the right subtree is on its far left side;

3. Search efficiency (time complexity) of binary search tree

a. When the binary search tree is a full binary tree or a complete binary tree, its average search time complexity is O(logN);

b. When the binary search tree degenerates into a single tree (basically only the left subtree or only the right subtree),
Its average time complexity is O(N);

4. Code implementation of binary search tree

#include<iostream>
#include<string>
using namespace std;
namespace key {
template<class T>
struct BSTreeNode //Binary tree node
{
typedef BSTreeNode<T> Node;
BSTreeNode(const T & amp; key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}

Node *_left;
Node *_right;
T_key;

};
template<class T>
classBSTree
{
typedef BSTreeNode<T> Node;
public:
bool Insert(const T & amp; key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return false;
}
Node* Find(const T & amp; key)
{
Node *cur = _root;
while (cur) {
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const T & amp; key)
{
Node* cur = _root;
Node* parent = cur;
while (cur)
{

if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else //Find the key node and prepare to delete it
{
Node *temp = cur;
if (cur->_left == nullptr) //The left subtree of the key node is empty, or both the left and right subtrees are empty.
//The child nodes of the key node need to be hosted on the parent node of the key;
{
if (_root == cur)//When the root node happens to be the node to be deleted, additional processing is required
{
_root = cur->_right;
}
else
{
if (cur->_key > parent->_key)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}

delete temp;

}
}
else if (cur->_right == nullptr)//key node right subtree is empty
{
if (cur == _root)
{
_root = cur->_left;
}
else {
if (cur->_key > parent->_key)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete temp;

}
else //Neither left nor right subtree of key node is empty
//Find the maximum node of the left subtree or the minimum node of the right subtree and replace it with the key node before deleting;
{

Node* minkey = cur->_right;

while (minkey->_left)
{
parent = minkey;
minkey = minkey->_left;
}
std::swap(minkey->_key, cur->_key);
if (parent->_left == minkey)
{
parent->_left = minkey->_right;
}
else
{
parent->_right = minkey->_right;
}
delete minkey;
}
return true;
}

}
return false;
}
voidInOrder()
{
_InOrder(_root);
cout << endl;
}
//Recursively implement the above method
bool FindR(const T & amp; key)
{
return _FindR(_root, key);
}

bool InsertR(const T & amp; key)
{
return _InsertR(_root, key);
}

bool EraseR(const T & amp; key)
{
return _EraseR(_root, key);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
bool _FindR(Node *root, const T & amp; key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
_FindR(root->_right, key);
}
else if (root->_key > key)
{
_FindR(root->_left, key);
}
else
{
return true;
}
}
bool _InsertR(Node* & amp; root, const T & amp; key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
else
{
if (key > root->_key)
{
_InsertR(root->_right, key);
}
else if (key < root->_key)
{
_InsertR(root->_left, key);
}
else
{
return false;
}

}
}
bool _EraseR(Node* & amp; root, const T & amp; key)
{
if (root == nullptr)return false;
if (key > root->_key)
{
return _EraseR(root->_right, key);
}
else if (key < root->_key)
{
return _EraseR(root->_left, key);
}
else
{
if (root->_left == nullptr)
{
Node* temp = root;
root = root->_right;
delete temp;
return true;
}
if (root->_right == nullptr)
{
Node* temp = root;
root = root->_left;
delete temp;
return true;
}
else
{
Node *minnode = root->_right;
while (minnode->_left)
{
minnode = minnode->_left;
}
std::swap(minnode->_key, root->_key);
return _EraseR(root->_right, key);
}

}
}


Node* _root = nullptr;
};

void TestBSTree()
{
BSTree<int>b1;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto num : a)
{
b1.Insert(num);
}
b1.InOrder();

b1.Erase(1);
b1.InOrder();

b1.Erase(10);
b1.InOrder();

b1.Erase(14);
b1.InOrder();

b1.Erase(8);
b1.InOrder();
}
void TestBSTree1()
{
BSTree<int>b1;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto num : a)
{
b1.InsertR(num);
}
b1.InOrder();
for (auto num : a)
{
b1.EraseR(num);
b1.InOrder();
}

}
void TestBSTree2()
{
BSTree<int>b1;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto num : a)
{
b1.InsertR(num);
}
b1.InOrder();
for (auto num : a)
{
if (b1.Find(num))cout << num << endl;
}

}
}
int main()
{
   key::TestBSTree();
   key::TestBSTree1();
key::TestBSTree2();
   return 0;
}

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57342 people are learning the system