行业知识
【c++】二叉搜索树（BST）
个人主页：Quitecoder
专栏：c++笔记仓
朋友们大家好，本篇文章来到二叉搜索树的内容
目录
- `1.二叉搜索树的介绍`
- `2.二叉搜索树的操作与实现`
- `insert插入`
- `Find查找`
- `InOrder中序遍历`
- `Erase删除`
- `3.二叉搜索树的应用（K与KV模型）`
- `改造二叉树为KV结构`
- `4.二叉搜索树性能分析`
1.二叉搜索树的介绍
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
它在动态数据集合中维护了一定的排序顺序，以便实现快速的数据查找、插入和删除操作
左子树比根小，右子树比根大
比如我想查找13，就不需要暴力比较，按照大小往左边或者右边走
对于二叉搜索树，进行中序遍历为升序
2.二叉搜索树的操作与实现
首先我们构建节点：
templatestruct BSTreeNode{K _key;BSTreeNode* _left;BSTreeNode* _right;BSTreeNode():_key(K()),_left(nullptr),_right(nullptr){}BSTreeNode(const K& key): _key(key), _left(nullptr), _right(nullptr){}};每个节点有两个指针，分别指向它的左子节点和右子节点。如果子节点不存在，则这些指针为nullptr
- 默认构造函数：
BSTreeNode():_key(K()),_left(nullptr),_right(nullptr){}默认构造函数，它初始化键值为K类型的默认值（通过调用K的默认构造函数），并将左右子节点指针都设置为nullptr，表示节点没有子节点
- 参数化构造函数：
BSTreeNode(const K& key): _key(key), _left(nullptr), _right(nullptr){}采用键值作为参数的构造函数，它会创建一个节点，这个节点的键值为传入的key值，同时初始化左右子节点指针为nullptr
接着我们来完成主体部分：
templateclass BSTree{public:typedef BSTreeNode Node;private:Node* _root = nullptr;};insert插入
比如插入5，我们从根节点开始，比8小，往左走，比3大，往右走…：
bool Insert(const T& key){Node* cur = _root;while (cur){if (cur->_key _right;}else if (cur->_key > key){cur = cur->_left;}else{return false;}}return true;}比当前节点小，往左走，反之往右走，搜索树默认是不允许插入重复键值
所以遇到相同的直接返回false，但是最后一步插入，我们还需要父亲位置的节点来完成左边插入或者右边插入，所以我们需要一个父亲节点来记录位置：
bool Insert(const T& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key _right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key _right = cur;}else{parent->_left = cur;}return true;}由于我们是从根部开始向下遍历直到达到叶节点，parent->_key必定不等于key（因为有重复检查）。如果parent的键值小于插入的键值key，新节点被设置为父节点的右子树；否则设置为左子树
注意
这里如果起始为**空树*
Node* cur = _root;while (cur){ // ...}由于cur是从_root开始的，如果跳过判空且_root实际上为nullptr，这个循环不会执行任何操作，因为它的条件立即不满足（cur此时为nullptr），并且会跳到循环之后的代码，如下：
cur = new Node(key);// ...
这里将创建一个新的节点，但此时变量parent仍然是nullptr。代码会接着尝试访问parent的_key成员：
if (parent->_key
因为parent是nullptr，这会导致未定义行为，最常见的是程序崩溃，因为你不能对nullptr解引用。另外，即使程序不崩溃，新的节点cur也没有父节点可以挂载到，这样二叉搜索树的结构就不完整了
所以完整代码如下：
bool Insert(const T& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key _right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key _right = cur;}else{parent->_left = cur;}return true;}Find查找
find这里思路很简单，就按照大小关系往下遍历即可：
bool Find(const T& key){Node* cur = _root;while (cur){if (cur->_key _right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;}InOrder中序遍历
void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout _key _right);}这里我们需要传入根节点，为类成员，单独一个函数是无法实现的，所以我们先完成上面的子函数书写，再一个主函数传入_root即可
void InOrder(){_InOrder(_root);cout 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (int e : a){b1.Insert(e);}b1.InOrder();if (_root == nullptr)return false;Node* parent = nullptr;Node* cur = _root;while (cur){if (cur-_key _right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else {if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{//左右都不为空，替换法删除Node* rightminparent = cur;Node* rightmin = cur->_right;while (rightmin->_left){rightminparent = rightmin;rightmin = rightmin->_left;}cur->_key = rightmin->_key;if (rightminparent->_left = rightmin){rightminparent->_left = rightmin->_right;}else{rightminparent->_right = rightmin->_right;}delete rightmin;}return true;}}return false;}我们拆分来看这串代码：
- 检查树是否为空:
if (_root == nullptr) return false;
-
查找需删除的节点:
代码通过while循环遍历树找到匹配key的节点。在循环中使用变量cur作为当前节点，变量parent作为cur的父节点
-
节点匹配:
当找到与key匹配的节点后:
- 如果该节点没有左子节点(cur->_left == nullptr), 那么它的右子节点直接替换它（也适用于它没有子节点的情况）
- 如果该节点没有右子节点(cur->_right == nullptr), 那么它的左子节点直接替换它
if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}如果cur恰好是根节点，我们直接将树的根 _root 指向cur的右子节点。这个更新意味着我们在树中移除了根节点，并将右子节点（如果存在）提升为新的根节点。
如果cur不是根节点，我们需要更新它父节点的相应指针。我们检查cur是其父节点的左子还是右子，并相应地更新父节点的左指针或右指针，使其指向cur的右子节点。这样，在二叉搜索树中删除了cur节点，并保持了其右子树
-
- 如果该节点既有左子节点也有右子节点, 那么需要找到该节点的中序后继节点来替代它。中序后继节点是在其右子树中值最小的节点。我们替换cur的键为中序后继节点的键，并将rightmin放在原来的位置上。
else{//左右都不为空，替换法删除Node* rightminparent = cur;Node* rightmin = cur->_right;while (rightmin->_left){rightminparent = rightmin;rightmin = rightmin->_left;}cur->_key = rightmin->_key;if (rightminparent->_left == rightmin){rightminparent->_left = rightmin->_right;}else{rightminparent->_right = rightmin->_right;}delete rightmin;}注意，在替换完成后需要删除原始的中序后继节点。这时rightmin的右子节点（如果存在）会替换rightmin。
每次删除一个节点后，代码会释放该节点的内存。
- 维护父节点指针:
删除过程中对父节点指针的适当维护是必须的，以确保删除节点后树的结构保持正确。比如，如果待删除节点是其父节点的左子节点，那么父节点的左指针应该指向待删除节点的相应子节点
最后，如果在树中找到并成功删除了key对应的节点，则函数返回true。如果没有找到，则函数返回false。
3.二叉搜索树的应用（K与KV模型）
- K模型：
- K模型指的是二叉树的节点仅存储键Key）信息，而没有与键相关联的特定“值”（Value）。换句话说，节点中的数据只有一个维度，节点的排序和组织就是基于这些键
- 在K模型的二叉树中，例如二叉搜索树（BST），节点的位置由其键的顺序决定。所有的节点操作，包括插入、查找和删除都是根据这个键来执行的。
- 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
- 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误
- KV模型：
- KV模型指的是二叉树的节点存储“键值对”（Key-Value Pair）。这里“键”（Key）用于确定节点的位置跟顺序，“值”（Value）则是与键关联的数据。
- 在KV模型的二叉树中，节点依然是根据键的顺序进行排列和组织的，但是与每个键都有一个相对应的值。这种模式适用于情况更为复杂的场景，如实现映射或字典结构。
- KV模型的一个典型例子是映射（Map）或词典（Dictionary）
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对
改造二叉树为KV结构
节点构建，加一个模版参数V
templatestruct BSTreeNode{V _value;K _key;BSTreeNode* _left;BSTreeNode* _right;BSTreeNode():_key(K()), _value(V());, _left(nullptr), _right(nullptr){}BSTreeNode(const K& key,const V& value): _key(key),_value(value), _left(nullptr), _right(nullptr){}};代码主题部分只需要进行简单的修改即可：
templateclass BSTree{public:typedef BSTreeNode Node;bool Insert(const K& key,const V& value){........cur = new Node(key,value); ........}Node* Find(const K& key) {Node* cur = _root;while (cur){if (cur->_key _right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr; }........};其余部分不需要改变
简单示例如下：
void TestBSTree2(){BSTree dict;dict.Insert("string", "字符串");dict.Insert("left", "左边");dict.Insert("insert", "插入");//...string str;while (cin >> str){BSTreeNode* ret = dict.Find(str);if (ret){cout _value cout - KV模型：
- 维护父节点指针:
- 如果该节点既有左子节点也有右子节点, 那么需要找到该节点的中序后继节点来替代它。中序后继节点是在其右子树中值最小的节点。我们替换cur的键为中序后继节点的键，并将rightmin放在原来的位置上。
