摘要：本文介绍了二叉搜索树（BST）的基本概念及其在C++中的实现。二叉搜索树是一种特殊的二叉树，其每个节点的值都大于其左子树中的任意节点的值且小于其右子树中的任意节点的值。BST在搜索、插入和删除操作中具有较好的性能，常用于数据存储和算法实现。C++中可以通过递归或迭代的方式实现BST的相关操作。
🔥个人主页：Quitecoder
🔥专栏：c++笔记仓
朋友们大家好，本篇文章来到二叉搜索树的内容
目录
- `1.二叉搜索树的介绍`
- `2.二叉搜索树的操作与实现`
- `insert插入`
- `Find查找`
- `InOrder中序遍历`
- `Erase删除`
- `3.二叉搜索树的应用（K与KV模型）`
- `改造二叉树为KV结构`
- `4.二叉搜索树性能分析`
1.二叉搜索树的介绍
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
它在动态数据集合中维护了一定的排序顺序，以便实现快速的数据查找、插入和删除操作
左子树比根小，右子树比根大
比如我想查找13，就不需要暴力比较，按照大小往左边或者右边走
对于二叉搜索树，进行中序遍历为升序
2.二叉搜索树的操作与实现
首先我们构建节点：
template struct 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
接着我们来完成主体部分：
template class 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
template struct 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) {} };代码主题部分只需要进行简单的修改即可：
template class 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放在原来的位置上。
还没有评论，来说两句吧...