个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创C++二叉搜索树(二叉树进阶)
收录于专栏 [C++进阶学习]
本专栏旨在分享学习C++的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1. 二叉搜索树的概念
2. 二叉搜索树的操作
2.1 二叉搜索树的查找
2.2 二叉搜索树的插入
2.3 二叉搜索树的删除
3. 二叉搜索树的实现
3.1 二叉搜索树的基本结构
3.2 二叉搜索树的插入操作
3.3 二叉搜索树的查找操作
3.4 二叉搜索树的删除操作
3.5 二叉搜索树的中序遍历
4. 二叉搜索树的的应用
1. K模型:
2. KV模型：
3.KV模型实现
5. 二叉搜索树的的性能分析
1. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
由于二插搜索树的性质:二叉搜索树的中序遍历是有序的
2. 二叉搜索树的操作
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
2.1 二叉搜索树的查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。
2.2 二叉搜索树的插入
插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
2.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情 况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点 中，再来处理该结点的删除问题--替换法删除
没有孩子或者一个孩子的情况:
删除两个孩子的节点需要用右子树的最小节点作为替代节点,因为这个替代节点一定比它的左孩子大也一定比它的右孩子小,满足二叉搜索树的性质.
当删除的节点有两个孩子并且它的右子树没有左孩子时:
直接使用右子树的根节点替换
3. 二叉搜索树的实现
3.1 二叉搜索树的基本结构
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};template<class K>
class BSTree
{typedef BSTNode<K> Node;
public:bool Insert(const K& key);bool Find(const K& key);bool Erase(const K& key);void InOrder();
private:Node* _root = nullptr;
};这段代码定义了一个简单的二叉搜索树（BST）的结构。BSTNode 是节点的结构体，包含一个键值和两个子节点指针。BSTree 是二叉搜索树的类，提供了插入、查找、删除和中序遍历的接口，_root 是指向树根节点的指针。
3.2 二叉搜索树的插入操作
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;
}1.检查树是否为空：
如果树为空（即根节点 _root 为 nullptr），则创建一个新的节点并将其设为根节点，然后返回 true 表示插入成功。
2.查找插入位置：
如果树非空，则从根节点开始，遍历树以找到适当的插入位置。parent 记录当前节点的父节点，而 cur 遍历树以查找插入点。根据键值与当前节点的比较，决定向左子树还是右子树移动。若找到相同的键值，返回 false 表示键值已存在，插入失败。
3.插入新节点：
找到插入位置后，创建一个新节点 cur 并将其作为 parent 的子节点。根据键值比较结果，将新节点插入为父节点的右子节点或左子节点。
4.返回插入成功：
插入操作完成，返回 true 表示成功插入新节点。
3.3 二叉搜索树的查找操作
bool Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;
}3.4 二叉搜索树的删除操作
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 删除// 0-1个孩子的情况if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{// 2个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;
}删除的节点是根节点或者只有一个孩子时(左孩子||右孩子):
1. 节点没有左子树（cur->_left == nullptr）
if (cur->_left == nullptr)
{if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;
}cur->_left == nullptr：当前节点没有左子树，只可能有右子树或没有子树。
parent == nullptr：当前节点是根节点。将根节点 _root 更新为当前节点的右子树。
parent != nullptr：当前节点是某个节点的子节点。根据 parent->_left == cur 判断当前节点是其父节点的左子节点还是右子节点，并将父节点的对应子节点指针更新为当前节点的右子树。
2. 节点没有右子树（cur->_right == nullptr）
else if (cur->_right == nullptr)
{if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;
}cur->_right == nullptr：当前节点没有右子树，只可能有左子树或没有子树。
parent == nullptr：当前节点是根节点。将根节点 _root 更新为当前节点的左子树。
parent != nullptr：当前节点是某个节点的子节点。根据 parent->_left == cur 判断当前节点是其父节点的左子节点还是右子节点，并将父节点的对应子节点指针更新为当前节点的左子树。
3. 节点两个孩子都不为空
else
{// 2个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;
}1. 找到右子树的最小节点
Node* rightMinP = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{rightMinP = rightMin;rightMin = rightMin->_left;
}rightMinP：指向 rightMin 的父节点。
rightMin：初始化为当前节点 (cur) 的右子节点。
while (rightMin->_left)：在右子树中向下遍历，找到最小节点。最小节点是右子树中最左边的节点。
更新 rightMinP 为当前节点（rightMin）。
更新 rightMin 为 rightMin 的左子节点。
2. 替代当前节点的值
cur->_key = rightMin->_key;cur->_key = rightMin->_key：将 rightMin 节点的键值复制到当前节点 cur。这样 cur 节点的键值就与要删除的节点的键值一致。
3. 删除右子树最小节点
if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;
elserightMinP->_right = rightMin->_right;delete rightMin;rightMinP->_left == rightMin：检查 rightMin 是否是 rightMinP 的左子节点。
如果是，则将 rightMinP 的左子节点指向 rightMin 的右子节点（因为 rightMin 节点没有左子树，右子节点可能存在）。
else：如果 rightMin 是 rightMinP 的右子节点。
将 rightMinP 的右子节点指向 rightMin 的右子节点。
delete rightMin：释放 rightMin 节点的内存，因为它已经被当前节点取代。
3.5 二叉搜索树的中序遍历
void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
4. 二叉搜索树的的应用
1. K模型:
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型：
KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。
该种方式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对
3.KV模型实现
//key-valuetemplate<class K, class V>class BSTree{typedef BSTNode<K, V> Node;public:BSTree() = default;BSTree(const BSTree<K, V>& t){_root = Copy(t._root);}~BSTree(){Destroy(_root);_root = nullptr;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 删除// 0-1个孩子的情况if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{// 2个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};
}实现和key模型差不多,这里就不在过多解释.
测试:
int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };keyValue::BSTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();return 0;
}
5. 二叉搜索树的的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log(N)
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N
问题：
如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插 入关键码，二叉搜索树的性能都能达到最优？那么我们的重量级AVL树和红黑树就可以上场了。 感兴趣的宝子们赶紧点赞关注支持一下吧!我马上回更新下一个内容!