-
binary search tree
- basic concept
- Common conclusions
- use
- Performance analysis of binary search trees
-
Operations on binary search trees
- find
- stick
- removing
-
code implementation
binary search tree
basic concept
Binary Search Tree (BST, Binary Search Tree)
A binary search tree, also known as a binary sort tree, is either an empty tree or a binary tree with the following properties.
- If its left subtree is not empty, then the values of all nodes in the left subtree are less than the value of the root node
- If its right subtree is not empty, then the values of all nodes in the right subtree are greater than the value of the root node
- Its left and right subtrees are also binary search trees respectively
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
A binary search tree/binary lookup tree is also known as a binary sort tree, because the result of a middle-order traversal of a binary sort tree is ascending.
Common conclusions
The left subtree of a binary search tree must be smaller than the root, and the right subtree must be larger than the root.Combining definitions of recursive subtreesavailable
-
The rightmost node of the left subtree is the largest node of the left subtree, and the rightmost node of the right subtree is the largest node of the right subtree.
-
The leftmost node of the left subtree is the smallest node of the left subtree, and the leftmost node of the right subtree is the smallest node of the right subtree.
-
The smallest node of a binary search tree is the leftmost node of the left subtree, and the largest node is the rightmost node of the right subtree.
use
The actual situation is seldom directly use the search binary tree, mostly based on the search binary tree's efficient search characteristics, derived from more practical higher-order data structures, such as balanced binary search tree (AVL tree, red-black tree), etc. ...
- K model: K model that only key as the key code, the structure only need to store Key can be, the key code that is the need to search to the value. (be outof the issue)
For example: given a word word, determine if the word is spelled correctly in the following way:
Construct a binary search tree using each word in the set of all words in the thesaurus as key
Retrieve whether the word exists in the binary search tree; if it does, it is spelled correctly; if it does not, it is spelled incorrectly.
And there are also such as: access control system, garage system and so on...
- KV model: for every key code key, there is a value Value corresponding to it, i.e. <Key, Value> key-value pair. This type of formula
The formula is very common in real life: (Finding a value by another value)
For example, the English-Chinese dictionary is the correspondence between English and Chinese, through the English can quickly find its corresponding Chinese, the English
A Chinese word and its corresponding Chinese <word, chinese> constitute a key-value pair;
Another example is counting the number of times a word is counted, and when the counting is successful, the number of times a given word appears can be quickly found, and the word with its out
The current count is <word, count> which constitutes a key-value pair.
And then there's the address book.
Performance analysis of binary search trees
Both insertion and deletion operations must be preceded by a lookup, and the lookup efficiency represents the performance of each operation in a binary search tree.
For a binary search tree with n nodes, if each element is looked up with equal probability, the average search length of the binary search tree is a function of the depth of the node in the binary search tree, i.e., the deeper the node, the more comparisons are made.
However, for the same set of keycodes, if the order of insertion of each keycode is different, a binary search tree with different structure may be obtained:
Optimally, the binary search tree is a complete binary tree (or near complete binary tree) with an average number of comparisons of $log_2 N$ ($log_2 N$)
In the worst case, the binary search tree degenerates into a single-branch tree (or similarly single-branch) with an average number of comparisons: $$\frac{N}{2}$$ ($\frac{N}{2}$)
Operations on binary search trees
find
- Starting from the root, compare and find, if it is bigger than the root, go to the right and find, if it is smaller than the root, go to the left and find.
- Lookup up to height times, go to to null, not found yet, this value does not exist.
stick
- If the tree is empty, new nodes are added directly, assigned to the root pointer (the first node is root)
- The tree is not empty, find the insertion position according to the nature of the binary search tree, and insert a new node.
particularly
-
The same set of data, inserted in a different order, the resulting binary tree is also different
-
Insertion fails when the inserted value already exists (regardless of multi).
removing
First find out if the element is in the binary search tree, if not, return .
Otherwise, according to the definition of the tree structure, three cases can be obtained
- The node to be deleted has no children
- When the node to be deleted has only a left or right child
- The nodes to be deleted have left and right child nodes
It looks like there are 4 cases of nodes to be deleted, in reality.
-
If the node to be deleted has no children, it is deleted directly.
-
If the node to be deleted has only a left or right child, give the left or right child to the father.
-
The node to be deleted may be the left or right child of the father, there are 2*2 cases (the node to be deleted is the left or right child of the father)
-
The case is also satisfied when both the left and right children are empty, so the childless node case can be combined
-
In the case of 1, it happens to be the root node, which is also the case (just let the other child be the root)
-
-
When the node to be deleted has left and right children, it is necessary to find a node that is both larger and smaller than the left and right subtrees to replace it.
according torecursive definitionWe know that only the rightmost node of the left child and the leftmost node of the right child satisfy the condition.
When choosing to use the leftmost node of the right child, there are three cases (independent of whether it is a root or not)
-
The smallest node of the right subtree of the node to be deleted is exactly the right child of the node to be deleted.
-
The minimum node of the right subtree of the node to be deleted has no right child.
-
The smallest node in the right subtree of the node to be deleted has a right child
(Examples analyzed in the chart above)
-
code implementation
template<class K>
struct BSTreeNode {
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(K key)
:_key(key),_left(nullptr),_right(nullptr)
{}
};
template<class K>
class BSTree {
public:
using Node = BSTreeNode<K>;
BSTree() = default;
BSTree(const BSTree& bst) {
_root = Copy(bst._root);
}
BSTree<K>& operator=(BSTree bst) { //copy reuse
swap(_root,);
return *this;
}
~BSTree() {
Destroy(_root);
}
public:
bool Insert(const K& key) {
if (_root == nullptr) {
_root = new Node(key);
_root->_key = key;
return true;
}
BSTreeNode<K>* cur = _root;
BSTreeNode<K>* parent = _root;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key) {
parent = cur;
cur = cur->_right;
}
else {
return false;
}
}
//break out of a cycle,Indicates that the node does not exist in the tree, Can be inserted
cur = new BSTreeNode<K>(key);
if (key < parent->_key) {
parent->_left = cur;
}
else {
parent->_right = cur;
}
return true;
}
bool Find(const K& key) {
if (_root == nullptr) return false;
Node* cur = _root;
while (cur) {
if (key < cur->_key) {
cur = cur->_left;
}
else if (key > cur->_key) {
cur = cur->_right;
}
else {
return true;
}
}
// Out of the loop,That means it's not there.
return false;
}
bool Erase(const K& key) {
if (_root == nullptr) return false;
Node* cur = _root;
Node* parent = _root;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key) {
parent = cur;
cur = cur->_right;
}
else {
//No left child.
if (cur->_left == nullptr) {
if (cur == _root) {
_root = cur->_right;
}
else if (parent->_left == cur) {
parent->_left = cur->_right;
}
else {
parent->_right = cur->_right;
}
delete cur;
return true;
}
//No right child.
else if (cur->_right == nullptr) {
if (cur == _root) {
_root = cur->_left;
}
if (parent->_left == cur) {
parent->_left = cur->_left;
}
else {
parent->_right = cur->_left;
}
delete cur;
return true;
}
//There are left and right children
else {
//Find the right child.(subtree)least node of/leftmost node
Node* rightMin = cur->_right; //Explicitly not empty
Node* rightMinParent = cur;
while (rightMin->_left) {
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
// 删除右subtree最小结点有3case(It doesn't matter if it's rooted or not.)
//1. 要删除的结点右subtree最小结点恰好是自己的右孩子.
//2. 要删除的结点的右孩子的左subtree的leftmost nodeNo right child..
//3. 要删除的结点的右孩子的左subtree的leftmost node有右孩子.
//Analysis of conclusions: Multiplexing Delete Single Node Code,DeletionrightMincan immediately (do sth)
K tmp = rightMin->_key;
Erase(rightMin->_key); //You can only traverse from the root.,performance loss,But the binary lookup is fast.,The damage is not significant.(ideal situation,BSTLearning only)
cur->_key = tmp;
return true;
} //There are left and right children的情况
} //Got it._Continuing the process of processing
}//process of circular search
//End of cycle,That means I didn't find it.
return false;
}//Erase [end]
void InOrder() {
_InOrder(_root);
std::cout << std::endl;
}
bool InsertR(const K& key) {
_InsertR(_root, key);
}
bool EraseR(const K& key) {
return _EraseR(_root,key);
}
private:
//The return value here cannot be referenced by a pointer,While certain circumstances can be used(not recommended),You can't reference null values, at least not yet..
Node* Copy(const Node* root) {
if (root == nullptr) {
return nullptr;
}
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
//It doesn't matter if it's quoted or not.,Good Habits to the End
//(When destructing a child node,Two members of the parent node will become dangling pointers,But then the father is going to be deconstructed as well,Pointer variables are also recycled)
void Destroy(Node*&root) {
if (root == nullptr) {
return ;
}
Destroy(root->_left);
Destroy(root->_right);
std::cout<<root->_key<<" ";
delete root; //Release plus auto-empty
}
//Practicing Recursion+quote -- Cleaner code
bool _EraseR(Node*& root, const K&key) {
//come up empty,That means I didn't find it.,come (or go) backfalse
if (root == nullptr) {
return false;
}
//Greater than going to the right.,Less than to the left.
if (key > root->_key) {
return _EraseR(root->_right,key);
}
else if(key<root->_key) {
return _EraseR(root->_left,key);
}
//Got it.
else {
if (root->_left == nullptr) {
Node* del = root;
root = root->_right;
delete del;
return true;
}
else if (root->_right == nullptr) {
Node* del = root;
root = root->_left;
delete del;
return true;
}
//There are left and right children
else {
Node* leftMax = root->_left;
//找左subtree最大结点
while (leftMax->_right) {
leftMax = leftMax->_right;
}
std::swap(root->_key, leftMax->_key);
return _EraseR(root->_left, key); //Recursive deletion directly from the left child.
}
}
}
//Practicing Recursion+quote指针的玩法,Exercise only
bool _InsertR(Node*& root, const K& key) { //quote的妙用,Direct access to real parameters across stack frames
if (root == nullptr) {
root == new Node(key);
return true;
}
if (key == root->_key) return false;
return (key > root->_key) ? _InsertR(root->_right, key) : _InsertR(root->_left, key);
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
std::cout << root->_key << " ";
_InOrder(root->_right);
}
private:
BSTreeNode<K>* _root = nullptr;
};
void test() {
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bst.
for (int i : a) {
(i);
}
();
////Find
//std::cout << std::boolalpha << (8) << std::endl; //true
//std::cout << std::boolalpha << (9) << std::endl; //false
BSTree<int> cp(bst).
();
// Just test three cases of two children
(8); //1. The smallest node of the right subtree of the node to be deleted happens to be the right child of the node to be deleted.
(10); //2. The minimum node of the right subtree of the node to be deleted has no right child.
(5); // Construct the smallest node that has a right child.
(3); //3. The minimum node of the right subtree of the node to be deleted has a right child.
(4);
(7);
(1);
(14);
(13).
(6).
(5).
().
// Disable explicit calls to destructors --> double release
//bst.~BSTree();
//cp.~BSTree();
}
int main() {
test(); }
}