【C++高阶】高效搜索的秘密：深入解析搜索二叉树
前言： 在数据结构和算法的广阔领域中，二叉搜索树（Binary Search Tree，简称BST）无疑是一颗璀璨的明星。它以其高效的数据检索能力和独特的树形结构，在计算机科学领域扮演着举足轻重的角色。对于任何对编程和数据结构感兴趣的人来说，掌握二叉搜索树都是至关重要的一步
二叉搜索树不仅仅是一个简单的数据结构，它更是一种解决问题的方式和思维的体现。通过维护二叉树中每个节点的左子树所有值均小于它的值，右子树所有值均大于它的值的特性，二叉搜索树在插入、查找和删除操作中展现出了卓越的性能。这种特性使得二叉搜索树在各种应用中成为了一种理想的数据结构选择，从基础的算法练习到复杂的系统优化，都能见到它的身影
学习二叉搜索树并非易事。它需要我们深入理解其性质、原理和算法实现。我们需要掌握如何构建一棵二叉搜索树，如何遍历它，以及如何在其中进行高效的查找、插入和删除操作。这些都需要我们付出大量的时间和精力去学习和实践。我们将从二叉搜索树的基本概念出发，逐步深入到其性质、构建、遍历以及操作的实现
让我们一起踏上学习二叉搜索树的旅程，探索它带来的无尽可能！ (本文重在二叉搜索树的模拟实现与理解)
📒1. 二叉搜索树
🎩二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
🎈二叉搜索树操作
首先，在二叉搜索树的操作中只支持插入，查找，删除，遍历，并不支持修改操作，因为在修改后谁也不能保证它依然是一棵二叉搜索树，二叉搜索树的时间复杂度范围在(O(logN)~O(N))
在二叉搜索树的遍历中一般采用中序遍历： 先遍历左子树，然后访问根节点，最后遍历右子树。在BST中，中序遍历会按照升序访问所有节点
二叉搜索树示例
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};🧩二叉搜索树结构
二叉搜索树结构的和树形结构差不多，这意味着每个元素（通常称为节点）都有两个指针：一个指向前一个左子树，另一个指向右子树，因此我们需要单独再定义一个类来表示节点结构，每个节点再串联起来构成BST
（在模拟实现二叉搜索树时，不用定义命名空间，因为不会和库中发生冲突）
节点定义（示例）：
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key = K())
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};BST定义（示例）：
template<class K>
class BSTree
{
typedef BSTreeNode<K> 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 < cur->_key)
{
cur = cur->_left;
}
// 当插入的值和cur位置相等时，直接退出，因为二叉搜索树不允许有相同的元素
else
{
return false;
}
}
// 将插入位置的新节点与二叉搜索树连接
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}🌞遍历
在二叉搜索树的遍历上，我们依旧采用当初二叉树时的中序遍历，但是我们想要递归遍历就必须调用节点，这里我们要调用两层
遍历代码实现（示例）：
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
// 递归出口
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " " ;
_InOrder(root->_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 < cur->_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 < cur->_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<K>& 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<K>& operator=(BSTree<K> 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 < _root->_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 < _root->_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 < _root->_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，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文<word, chinese>就构成一种键值对
- 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出 现次数就是<word, count>就构成一种键值对
namespace kv // 避免与之前k模型冲突
{
template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
V _value;
BSTreeNode(const K& key = K(), const V& value = V())
: _left(nullptr)
, _right(nullptr)
, _key(key)
, _value(value)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
// 构造函数等可能的其他成员函数...
// 在成员函数中，我们只需要在insert中加入value元素即可
private:
Node* _root = nullptr;
};
}在成员函数中，我们只需要在Insert中加入value元素即可
🍂KV模型实现
💧英汉词典
代码实现（示例）：
int main()
{
kv::BSTree<string, string> 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<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "无此单词" << endl;
}
}
}🔥计数
代码实现（示例）：
int main()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
kv::BSTree<string, int> countTree;
for (auto& e : arr)
{
kv::BSTreeNode<string, int>* ret = countTree.Find(e);
if (ret == nullptr)
{
countTree.insert(e, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
return 0;
}🌄二叉树巩固知识
最后在这给大家推荐几道巩固二叉树的编程题 二叉树创建字符串 二叉树的分层遍历 找到树中两个指定节点的最近公共祖先 二叉树搜索树转换成排序双向链表 根据一棵树的前序遍历与中序遍历构造二叉树 二叉树中序遍历 ，非递归迭代实现
📖5. 总结
经过我们一同对搜索二叉树的深入学习和探索，相信你已经对这种数据结构有了全面而深刻的理解。搜索二叉树以其独特的性质在数据检索领域展现了出色的性能，无论是插入、删除还是查找操作，都体现了其高效和灵活的特点
学习的道路永无止境。虽然我们已经走过了搜索二叉树的基本概念和操作的学习之旅，但这只是你编程旅程中的一个站点。前方还有更多数据结构等待你去探索，更多算法等待你去实践
不要忘记持续学习和自我提升。计算机科学是一个日新月异的领域，新的技术和算法不断涌现。只有保持对知识的渴望和追求，我们才能在这个领域中不断前行,让我们一起在学习的道路上不断前行! 希望本文能够为你提供有益的参考和启示，让我们一起在编程的道路上不断前行！ 谢谢大家支持本篇到这里就结束了，祝大家天天开心！