【C++高阶】二叉搜索树的全面解析与高效实现
✨ 人生到处知何似，应似飞鸿踏雪泥 🌏
📃个人主页：island1314
🔥个人专栏：C++学习
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞
二叉搜索树目录
一、二叉搜索树的概念
二、二叉搜索树的功能
三、二叉搜索树的实现
🧩1. 节点定义：
🧩2. BST定义：
🧩3. 二叉搜索树的操作
🌈a. 查找
🌈b. 插入
🌈c. 删除
🌈d. 遍历
🧩4、二叉搜索树默认成员函数
🎉构造
🎉拷贝构造
🎉赋值重载
🎉析构
4. 二叉搜索树的应用
🍁1. K模型
💧数组的排序实现
🍁2. KV模型
🍁3. KV模型实现
💧英汉词典的查找实现
💧计数
5.二叉搜索树的性能分析
🌄二叉树巩固知识
一、二叉搜索树的概念
二叉搜索树(BST,Binary Search Tree)又称二叉排序树，是一种特殊的二叉树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
二叉搜索树（Binary Search Tree）的每个节点的左子树中的所有节点都比该节点小，右子树中的所有节点都比该节点大。这个特性使得二叉搜索树可以用来实现非常高效的查找、插入和删除操作。
二、二叉搜索树的功能
🎈首先，在二叉搜索树的操作中只支持插入，查找，删除，遍历，并不支持修改操作，因为在修改后谁也不能保证它依然是一棵二叉搜索树，二叉搜索树的时间复杂度范围在(O(logN)~O(N))
🎈在二叉搜索树的遍历中一般采用中序遍历： 先遍历左子树，然后访问根节点，最后遍历右子树。在BST中，中序遍历会按照升序访问所有节点
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};三、二叉搜索树的实现
二叉搜索树结构的和树形结构差不多，这意味着每个元素（通常称为节点）都有两个指针：一个指向前一个左子树，另一个指向右子树，因此我们需要单独再定义一个类来表示节点结构，每个节点再串联起来构成BST
（在模拟实现二叉搜索树时，不用定义命名空间，因为不会和库中发生冲突）
🧩1. 节点定义：
template struct BSTNode { K _key; BSTNode* _left; BSTNode* _right; BSTNode(const K&key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} };🧩2. BST定义：
template class BSTree { typedef BSTreeNode Node; public: // 构造函数等可能的其他成员函数... private: Node* _root = nullptr; };🧩3. 二叉搜索树的操作
🌈a. 查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key _right; } else if (cur->_key > key) { //查找的值比cur大，往右走 cur = cur->_left; } else return true;//找到就返回true } 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; } }🌈b. 插入
a、树为空，则直接新增节点，赋值给root指针
b、树不空，按二叉搜索树性质查找插入位置，插入新节点
bool Insert(const K&key) //需要找个节点保留插入节点的父节点，先找到要插入位置 { if (_root == nullptr) { //根为空时直接插入 _root = new Node(key); return true; } // 定义parent是因为，在最后找到插入位置时，需要parent将节点进行连接 Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key _right; } else if (cur->_key > key) {// 插入的值比cur位置小，cur往左走 parent = cur; cur = cur->_left; } // 当插入的值和cur位置相等时，直接退出，因为二叉搜索树不允许有相同的元素 else return false; } //新插入节点与二叉搜索树连接 cur = new Node(key); if (parent->_key _right = cur; else parent->_left = cur; return true; }递归版本
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; } }🌈c. 删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，但是实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
⭐情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
⭐情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
⭐情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除
bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key _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; else parent->_right = cur->_right; } //先判断该节点为父节点的左还是右 if (parent->_left == cur) parent->_left = cur->_right; else parent->_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; else parent->_right = cur->_left; } delete cur; return true; } else { //两个孩子的情况，找右子树的最小节点为替代节点 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; else rightMinP->_right = rightMin->_right; delete rightMin; return true; } } } return false; }递归
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); } } }🌈d. 遍历
在二叉搜索树的遍历上，我们依旧采用当初二叉树时的中序遍历，但是我们想要递归遍历就必须调用节点，这里我们要调用两层。
void Inorder() //避免_root私有，无法提供的问题 { _Inorder(_root); } private: void _Inorder(Node* root) { if (root == nullptr) return; //递归截止 _Inorder(root->_left); printf("%d ", root->_key); _Inorder(root->_right); }🧩4、二叉搜索树默认成员函数
🎉构造
BSTree() = default; // 显式地定义默认构造函数
🎉拷贝构造
BSTree(const BSTree& t) { _root = Copy(t._root); } private: 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; }🎉赋值重载
BSTree& operator=(BSTree t) { // 现代写法-> 直接调用swap swap(_root, t._root); return *this; }🎉析构
~BSTree() { Destory(_root); } private: void Destroy(Node* root) { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; }4. 二叉搜索树的应用
🍁1. K模型
K模型：即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值，其实现如上所示。
比如：给一个数据库，判断该数据是否存在，具体方式如下：
以该数据库中所有数据集合中的每个数据作为key，构建一棵二叉搜索树
在二叉搜索树中检索该数据是否存在，存在则正确，不存在则错误。
💧数组的排序实现
代码实现（示例）：
void test1() //二叉排序树 { int a[] = { 8,3,1,10,6,4,7,14,13 }; BSTree t; for (auto e : a) { t.Insert(e); } t.Insert(16); t.Insert(4); t.Inorder(); cout _key > key) { cur = cur->_left; } else return cur; } return nullptr; }namespace keyValue // 避免与之前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; }; }💧英汉词典的查找实现
代码实现（示例）：
void test2() { // 输入单词，查找单词对应的中文翻译 keyValue::BSTree dict; dict.Insert("string", "字符串"); dict.Insert("tree", "树"); dict.Insert("left", "左边、剩余"); dict.Insert("right", "右边"); dict.Insert("sort", "排序"); // 插入词库中所有单词 string str; while (cin >> str) { auto ret = dict.Find(str); if (ret == nullptr) { cout
