【C++高阶】高效搜索的秘密：深入解析搜索二叉树
📝个人主页🌹：Eternity._
⏩收录专栏⏪：C++ “ 登神长阶 ”
🤡往期回顾🤡：C++多态
🌹🌹期待您的关注 🌹🌹
❀二叉搜索树
- 📒1. 二叉搜索树
- 🎩二叉搜索树概念
- 🎈二叉搜索树操作
- 📕2. 二叉搜索树模拟实现
- 🧩二叉搜索树结构
- 🧩二叉搜索树操作
- 🌈插入
- 🌞遍历
- 🌙查找
- ⭐删除
- 🧩二叉搜索树默认成员函数
- 📜3. 二叉搜索树模拟实现(递归)
- 🌞插入
- 🌙查找
- ⭐删除
- 📚4. 二叉搜索树的应用
- 🍁KV模型
- 🍂KV模型实现
- 💧英汉词典
- 🔥计数
- 🌄二叉树巩固知识
- 📖5. 总结
前言： 在数据结构和算法的广阔领域中，二叉搜索树（Binary Search Tree，简称BST）无疑是一颗璀璨的明星。它以其高效的数据检索能力和独特的树形结构，在计算机科学领域扮演着举足轻重的角色。对于任何对编程和数据结构感兴趣的人来说，掌握二叉搜索树都是至关重要的一步
二叉搜索树不仅仅是一个简单的数据结构，它更是一种解决问题的方式和思维的体现。通过维护二叉树中每个节点的左子树所有值均小于它的值，右子树所有值均大于它的值的特性，二叉搜索树在插入、查找和删除操作中展现出了卓越的性能。这种特性使得二叉搜索树在各种应用中成为了一种理想的数据结构选择，从基础的算法练习到复杂的系统优化，都能见到它的身影
学习二叉搜索树并非易事。它需要我们深入理解其性质、原理和算法实现。我们需要掌握如何构建一棵二叉搜索树，如何遍历它，以及如何在其中进行高效的查找、插入和删除操作。这些都需要我们付出大量的时间和精力去学习和实践。我们将从二叉搜索树的基本概念出发，逐步深入到其性质、构建、遍历以及操作的实现
让我们一起踏上学习二叉搜索树的旅程，探索它带来的无尽可能！
(本文重在二叉搜索树的模拟实现与理解)
📒1. 二叉搜索树
🎩二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
🎈二叉搜索树操作
首先，在二叉搜索树的操作中只支持插入，查找，删除，遍历，并不支持修改操作，因为在修改后谁也不能保证它依然是一棵二叉搜索树，二叉搜索树的时间复杂度范围在(O(logN)~O(N))
在二叉搜索树的遍历中一般采用中序遍历： 先遍历左子树，然后访问根节点，最后遍历右子树。在BST中，中序遍历会按照升序访问所有节点
二叉搜索树示例
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};📕2. 二叉搜索树模拟实现
🧩二叉搜索树结构
二叉搜索树结构的和树形结构差不多，这意味着每个元素（通常称为节点）都有两个指针：一个指向前一个左子树，另一个指向右子树，因此我们需要单独再定义一个类来表示节点结构，每个节点再串联起来构成BST
（在模拟实现二叉搜索树时，不用定义命名空间，因为不会和库中发生冲突）
节点定义（示例）：
template struct BSTreeNode { BSTreeNode* _left; BSTreeNode* _right; K _key; BSTreeNode(const K& key = K()) :_key(key) , _left(nullptr) , _right(nullptr) {} };BST定义（示例）：
template class BSTree { typedef BSTreeNode Node; public: // 构造函数等可能的其他成员函数... private: Node* _root = nullptr; };🧩二叉搜索树操作
🌈插入
插入的具体过程如下：
- 树为空，则直接新增节点，赋值给root指针
- 树不空，按二叉搜索树性质查找插入位置，插入新节点
插入代码实现（示例）：
bool Insert(const K& key) { // 当根为空时，直接插入 if (_root == nullptr) { _root = new Node(key); return true; } // 定义parent是因为，在最后找到插入位置时，需要parent将节点进行连接 Node* parent = nullptr; Node* cur = _root; while (cur) { parent = cur; // 插入的值比cur位置大时，cur往右移动 if (key > cur->_key) { cur = cur->_right; } // 插入的值比cur位置小时，cur往左移动 else if (key _key) { cur = cur->_left; } // 当插入的值和cur位置相等时，直接退出，因为二叉搜索树不允许有相同的元素 else { return false; } } // 将插入位置的新节点与二叉搜索树连接 cur = new Node(key); if (parent->_key _right = cur; } else { parent->_left = cur; } return true; }🌞遍历
在二叉搜索树的遍历上，我们依旧采用当初二叉树时的中序遍历，但是我们想要递归遍历就必须调用节点，这里我们要调用两层
遍历代码实现（示例）：
void InOrder() { _InOrder(_root); cout // 递归出口 if (root == nullptr) { return; } _InOrder(root-_left); cout _key _right); }遍历比较简单奥，我们接着往下讲
🌙查找
二叉搜索树的查找
- 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找
- 最多查找高度次，走到到空，还没找到，这个值不存在
查找代码实现（示例）：
bool Find(const K& key) { Node* cur = _root; while (cur) { // 查找的值比cur大，cur往右移动 if (key > cur->_key) { cur = cur->_right; } // 查找的值比cur小，cur往左移动 else if (key _key) { cur = cur->_left; } // 找到key,返回true else { return true; } } return false; // 找不到key,返回false }⭐删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面情况：
- 要删除的结点无孩子结点
- 要删除的结点只有左孩子结点
- 要删除的结点只有右孩子结点
- 要删除的结点有左、右孩子结点
而上面四种情况可以转化成下面的情况:
- 删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
- 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
- 在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除
这三种情况就是我们模拟实现删除的方法！
删除代码实现（示例）：
bool Erase(const K& key) { Node* cur = _root; Node* parent = nullptr; while (cur) { parent = cur; if (key > cur->_key) { cur = cur->_right; } else if (key _key) { 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; } } } // 右为空 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; } } } // 两边都不为空 else { // 这里与外层不是同一块作用域，所以可以再次定义parent，不把parent定义为nullptr是因为 //，可能不进入下面循环导致对parent空指针的使用 Node* subLeft = cur->_right; // 定义右数节点 Node* parent = cur; while (subLeft->_left) { parent = subLeft; subLeft = subLeft->_left; } swap(cur->_key, subLeft->_key); // 替换右子树的最左节点 if (subLeft == parent->_left) { // 最左节点肯定没有左孩子，所以让parent接管它的右子树 parent->_left = subLeft->_right; } else { parent->_right = subLeft->_right; } delete subLeft; } return true; } } return false; }🧩二叉搜索树默认成员函数
构造
BSTree() = default; // 显式地定义默认构造函数
拷贝构造
BSTree(const BSTree& t) { _root = Copy(t._root); } Node* Copy(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; }赋值重载
BSTree& operator=(BSTree t) { // 现代写法-> 直接调用swap swap(_root, t._root); return *this; }析构
~BSTree() { Destory(_root); } void Destory(Node*& _root) { if (_root == nullptr) { return; } // 递归调用析构 Destory(_root->_left); Destory(_root->_right); delete _root; _root == nullptr; }📜3. 二叉搜索树模拟实现(递归)
在进行递归操作的模拟实现时，一般都要传节点，进行多层的调用，因为我们都要定义两层
bool FindR(const K& key) { return _FindR(_root, key); } bool InsertR(const K& key) { return _InsertR(_root, key); } bool EraseR(const K& key) { return _EraseR(_root, key); }🌞插入
代码实现（示例）：
bool _InsertR(Node*& _root, const K& key) { // 递归出口 if (_root == nullptr) { // 这里我们无需在进行对新节点的连接，因为我们是传引用传参， _root = new Node(key); return true; } if (key > _root->_key) { return _InsertR(_root->_right, key); } else if (key _key) { return _InsertR(_root->_left, key); } else { return false; } }🌙查找
代码实现（示例）：
bool _FindR(Node* _root, const K& key) { if (_root == nullptr) { return false; } if (key > _root->_key) { return _FindR(_root->_right, key); } else if (key _key) { return _FindR(_root->_left, key); } else { return true; } }⭐删除
代码实现（示例）：
bool _EraseR(Node*& _root, const K& key) { if (_root == nullptr) { return false; } if (key > _root->_key) { return _EraseR(_root->_right, key); } else if (key _key) { return _EraseR(_root->_left, key); } 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; } else { Node* subLeft = _root->_right; while (subLeft->_left) { subLeft = subLeft->_left; } swap(_root->_key, subLeft->_key); // 让子树继续递归下去 return _EraseR(_root->_right, key); } } }📚4. 二叉搜索树的应用
🍁KV模型
KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文就构成一种键值对
- 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是就构成一种键值对
namespace kv // 避免与之前k模型冲突 { template struct BSTreeNode { BSTreeNode* _left; BSTreeNode* _right; K _key; V _value; BSTreeNode(const K& key = K(), const V& value = V()) : _left(nullptr) , _right(nullptr) , _key(key) , _value(value) {} }; template class BSTree { typedef BSTreeNode Node; public: // 构造函数等可能的其他成员函数... // 在成员函数中，我们只需要在insert中加入value元素即可 private: Node* _root = nullptr; }; }在成员函数中，我们只需要在Insert中加入value元素即可
🍂KV模型实现
💧英汉词典
代码实现（示例）：
int main() { kv::BSTree dict; dict.insert("left", "左边、剩余"); dict.insert("string", "字符串"); dict.insert("hahaha", "哈哈"); dict.insert("Eternity", "永恒"); dict.insert("sort", "排序"); dict.InOrder(); string str; while (cin >> str) { kv::BSTreeNode* ret = dict.Find(str); if (ret) { cout _value cout string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; kv::BSTree kv::BSTreeNode countTree.insert(e, 1); } else { ret-_value++; } } countTree.InOrder(); return 0; }
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
