当前位置:网站首页>7.5 binary search (sort) tree
7.5 binary search (sort) tree
2022-07-21 13:26:00 【123_ YQH】
Binary sort tree ( Binary search tree )
Sequential lookup table insert 、 The deletion operation is very efficient , But because it is disordered , So the search efficiency is very low . And the efficiency of ordered lookup table is OK , But because of order , Therefore, it takes a lot of time to maintain order after insert and delete operations . If we want to find a way to insert 、 Delete and delete efficient data structures to store dynamic lookup tables , You can use binary search ( Sort ) Trees .
1. Binary search ( Sort ) Tree definition
Binary sort tree (Binary Sort Tree), Also known as binary search tree . It could be an empty tree , Or a binary tree that has the following properties :
- If it's Zuozi tree is not empty , be The value of all nodes of the left subtree is less than the value of its root .
- If it's Right subtree is not empty , be The value of all nodes on the right subtree is greater than that of its root node .
- its Left 、 The right subtree is also a binary sort tree .
Construct a search tree ( Sort ) The purpose of the tree , It's not about sorting , It is In order to improve the speed of finding, inserting and deleting keywords .
Such as : Use a binary sort tree to store collections {62,88,58,47,35,73,51,99,37,93}.
The creation process is as follows :
- 62 As root node .
- 88 Than 62 Big , As 62 The right subtree .
- 58 Than 62 Small , As 62 The left subtree .
- 47 Than 58 Small , As 58 The left subtree .
- 35 Than 47 Small as 47 The left subtree .
- 73 Than 62 Big 、 Than 88 Small , As 88 The left subtree .
- 51 Than 47 Big 、 Than 58 Small , As 47 The right subtree .
- 99 Than 88 Big , As 88 The right subtree .
- 37 Than 35 Big 、 Than 47 Small , As 35 The right subtree .
- 93 Than 88 Big 、 Than 99 Small , As 99 The left subtree .
Its C++ The code implementation is as follows :
// Search binary tree node definition
template<typename V, typename K>
struct BSTreeNode {
V val;
K key;
BSTreeNode* left;
BSTreeNode* right;
BSTreeNode(const V& v, const K& k) : val(v), key(k), left(nullptr), right(nullptr) {
}
};
//1. Search binary tree definition
template<typename V, typename K>
class BSTree {
using Node = BSTreeNode<V, K>;
public:
BSTree() : _root(nullptr) {
}
//1. Search operation
Node* find(const K& k) {
return find_(_root, k);
}
Node* find_(Node* root, const K& k) {
if (root == nullptr) return nullptr;
if (root->key > k) {
return find_(root->left, k);
} else if (root->key < k) {
return find_(root->right, k);
} else {
return root;
}
}
//2. The insert
void insert(const V &v, const K &k) {
insert_(_root, v, k);
}
// Be careful Node* & Is a reference to a node pointer , In order to change the value of the node pointer ( Instead of the node pointer pointing to the value of the node ).
void insert_(Node* &root, const V& v, const K& k) {
if (root == nullptr) {
root = new Node(v, k);
return;
} if (root->key > k) {
insert_(root->left, v, k);
} else if (root->key < k) {
insert_(root->right, v, k);
} else {
return;
}
}
//3. Delete operation
void remove(const K& k) {
remove_(_root, k);
}
void remove_(Node* &root, const K& k) {
//1. Without nodes , Go straight back to
if (root == nullptr) return;
//2. Only the root node
if (root->left == nullptr && root->right == nullptr) {
if (root->key == k) {
delete root;
root = nullptr;
return;
} else {
return;
}
}
if (root->key > k) {
remove_(root->left, k);
} else if (root->key < k) {
remove_(root->right, k);
} else {
Node* del = nullptr;
//3. Only the case of right subtree , Directly move the right subtree to the deleted node
if (root->left == nullptr) {
del = root;
root = root->right;
delete del;
del = nullptr;
return;
} else if (root->right == nullptr) {
//4. Only the case of left subtree , Move the left subtree directly to the deleted node
del = root;
root = root->left;
delete del;
del = nullptr;
return;
} else {
//5. There are subtrees on both sides , The right node adjacent to the deleted node is replaced by the middle order traversal of the search binary tree .
Node* rightFirst = root->right;
while (rightFirst->left) {
rightFirst = rightFirst->left;
}
swap(root->key, rightFirst->key);
swap(root->val, rightFirst->val);
remove_(root->right, k);
return;
}
}
}
//4. Display search Binary Tree
void outPut() {
outPut_(_root);
cout << endl;
}
void outPut_(Node* root) {
if (root == nullptr) {
return;
}
outPut_(root->left);
cout << root->key << " ";
outPut_(root->right);
}
private:
Node* _root;
};
int main() {
BSTree<int, int> b;
b.insert(0, 62);
b.insert(0, 88);
b.insert(0, 58);
b.insert(0, 47);
b.insert(0, 35);
b.insert(0, 73);
b.insert(0, 51);
b.insert(0, 99);
b.insert(0, 37);
b.insert(0, 93);
b.outPut();
b.remove(47);
b.outPut();
}
2. Binary search ( Sort ) Tree lookup operation
The code is as follows :
Node* find_(Node* root, const K& k) {
if (root == nullptr) return nullptr;
if (root->key > k) {
return find_(root->left, k);
} else if (root->key < k) {
return find_(root->right, k);
} else {
return root;
}
}
The idea of searching is recursion , The algorithm idea is as follows :
- If the current node is empty , If the search fails, the null pointer will be returned ;
- If the searched key value is greater than the current node key value , Then, the node to be searched belongs to the right subtree of the current node , Recursively find the right child node of the current node .
- If the key value searched is equal to the key value of the current node , It indicates that the searched node belongs to the left subtree of the current node , Recursively find the left child node of the current node .
- If the key value searched is equal to the key value of the current node , Find success , Returns the address of the current node .
3. Binary search ( Sort ) Tree insert operation
The code is as follows :
void insert_(Node* &root, const V& v, const K& k) {
if (root == nullptr) {
root = new Node(v, k);
return;
} if (root->key > k) {
insert_(root->left, v, k);
} else if (root->key < k) {
insert_(root->right, v, k);
} else {
return;
}
}
The idea of delete operation is also recursive , as follows :
- If the current node is a null pointer , There are no nodes , Create a new node directly in the heap .
- If the key value of the current node is greater than the key value to find , The node to be inserted is in the left subtree of the current node , The left child node of the current node is inserted recursively .
- If the key value of the current node is less than the key value to find , The node to be inserted is in the right subtree of the current node , Recursively insert the right child node of the current node .
- If the key value of the current node is equal to the key value to find , Insert the failure , Do not perform operation .
4. Binary search ( Sort ) Tree deletion
It is easier to insert than to delete , Three cases of deleting nodes are analyzed :
① The deleted node is a leaf node
It's very simple , Just delete it .
If the delete key value is 37 The node of , It can be seen that after deletion , The structure of other nodes is not affected .
② The deleted node has only left subtree or right subtree
This situation is also relatively easy to solve , As long as the node is deleted , Move its left subtree or right subtree to the position where the node is deleted .
Such as : Delete 58 node , Move the entire left subtree to the delete node .
③ The deleted node has both left and right subtrees
This situation is relatively complex , If you follow the above idea , hold Its left subtree is spelled on , Then re insert the right subtree , This method Not only is the efficiency not high , It will also lead to great changes in the structure of the whole binary search tree .
Let's take a look ,47 Whether there are nodes in the two subtrees of 47 node , This will not only improve efficiency , And the structure of the whole binary tree remains basically unchanged .
37 and 48 Nodes can replace 47 node , They happen to be The result of order traversal in binary sort tree 47 The precursor and successor of . We can choose 37 perhaps 48 Node to replace 47 node .
The code is as follows :
void remove_(Node* &root, const K& k) {
//1. Without nodes , Go straight back to
if (root == nullptr) return;
//2. Only the root node
if (root->left == nullptr && root->right == nullptr) {
if (root->key == k) {
delete root;
root = nullptr;
return;
} else {
return;
}
}
if (root->key > k) {
remove_(root->left, k);
} else if (root->key < k) {
remove_(root->right, k);
} else {
Node* del = nullptr;
//3. Only the case of right subtree , Directly move the right subtree to the deleted node
if (root->left == nullptr) {
del = root;
root = root->right;
delete del;
del = nullptr;
return;
} else if (root->right == nullptr) {
//4. Only the case of left subtree , Move the left subtree directly to the deleted node
del = root;
root = root->left;
delete del;
del = nullptr;
return;
} else {
//5. There are subtrees on both sides , The right node adjacent to the deleted node is replaced by the middle order traversal of the search binary tree .
Node* rightFirst = root->right;
while (rightFirst->left) {
rightFirst = rightFirst->left;
}
swap(root->key, rightFirst->key);
swap(root->val, rightFirst->val);
remove_(root->right, k);
return;
}
}
}
边栏推荐
- 如何优雅的实现MySQL 数据库定时备份(荣耀典藏版)
- 软件性能测试方法有哪些?性能测试报告需要多少钱?
- 【图像处理】Pyefd.elliptic_fourier_descriptors的使用方式
- 【开发教程4】开源蓝牙心率防水运动手环-外部 Flash 读写
- 腾讯云服务器的搭建
- PHP uses PDO to connect to the database
- 使用MySQL, JSON 这张牌你一定要善用
- 16 package
- Kubesphere 3.3.0 offline installation tutorial
- How do PR video editors choose notebooks? ASUS lingyao pro16 2022 brings you to play with content creation
猜你喜欢
大国“粮”策|小麦专家刘录祥:我国口粮绝对安全,增粮潜力关键在科技
专业创作本华硕ProArt 创16 2022预售,高效创作新旗舰
Operation and maintenance experience sharing of stolen mailbox disposal in Colleges and Universities - Tsinghua University
如何优雅的实现MySQL 数据库定时备份(荣耀典藏版)
17 多态
使用Helm部署Harbor
CH单库数据迁移到读写分离模式
【开发教程4】开源蓝牙心率防水运动手环-外部 Flash 读写
Openbmb x Tsinghua NLP: the 20 hour large model open class will take you from introduction to mastery
带你认识一下数仓的分区自动管理
随机推荐
以通俗易懂的方式了解MySQL 索引和 B+Tree(至尊典藏版)
每日刷题记录 (二十九)
Chia mining, investment value, 2021-04-18
C language - Sanzi game
关于Coinbase成长历程的感悟 2021-04-15
使用Helm部署Harbor
阿里云联合平行云推出云XR平台,支持沉浸式体验应用快速落地
7.6平衡二叉树(AVL树)
CCF201503-1图像旋转
阿裏雲聯合平行雲推出雲XR平臺,支持沉浸式體驗應用快速落地
11.3构造方法
[translation] in depth understanding of modern web browsers (4)
7.5二叉搜索(排序)树
从头开始实现 Promise
各国程序员薪资水平,最高都知道、垫底想不到...
Implement promise from scratch
15 super用法
从“AI玩具”到“创作工具”的云原生改造之路
7.7 B树和B+树
股票开户申万宏源?安全可靠吗?