C++ 二叉搜索树详解与实现
一、概念与性能分析
1.1 二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
C++算法
C++ 二叉搜索树详解与实现
二叉搜索树是一种特殊的二叉树，左子树节点值小于等于根节点，右子树大于等于根节点，中序遍历为升序。其时间复杂度在平衡时为 O(logN)，最坏退化为 O(N)。二叉搜索树的概念、性能分析，以及插入、删除、查找和中序遍历的实现细节，包含 Key 和 Key-Value 两种结构的代码示例及典型应用场景。
二叉搜索树是一种特殊的二叉树，左子树节点值小于等于根节点，右子树大于等于根节点，中序遍历为升序。其时间复杂度在平衡时为 O(logN)，最坏退化为 O(N)。二叉搜索树的概念、性能分析，以及插入、删除、查找和中序遍历的实现细节，包含 Key 和 Key-Value 两种结构的代码示例及典型应用场景。
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。例如：map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。
由于它本身和它的子树都是二叉搜索树，不难发现：二叉搜索树的中序遍历一定是升序序列（所以二叉搜索树又称二叉排序树）。
二叉搜索树顾名思义，其只有由于搜索（或者搜索效率高），下面我们来分析其最优情况和最差情况。
最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：log₂N。 最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：N。
所以综合而言二叉搜索树增删查改时间复杂度为：O(N)。
那么这样的效率显然是无法满足我们需求的，必须将二叉搜索树优化即二叉搜索树的变形：平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。
需要说明的是，二分查找也可以实现 O(log₂N) 级别的查找效率，但是二分查找有两大缺陷：
这里也就体现出了平衡二叉搜索树的价值。
这里不支持修改（修改一个就可能不是二叉搜索树的结构了）。
由于后面实现二叉搜索树要访问节点成员所以这里使用 struct 定义（默认是公有）。
template<class K> struct BSTreeNode {
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) { }
};
由于二叉搜索树涉及到节点资源的开辟、拷贝、删除，所以这里我们需要自己写拷贝构造，赋值重载，析构函数，默认构造一般不满足我们的需求所以看情况是否要写，而这里由于我们需要写拷贝构造（一种特殊的默认构造）所以这里一定要手写默认规则（可以缺省值）。
template<class K> class BSTree {
typedef BSTreeNode<K> Node;
private:
Node* _root = nullptr;
};
BSTree() = default;
前面的链式结构的树的拷贝需要递归完成（即使用了递归），所以访问私有成员（在类外面调用该函数会出错），而这个函数的实现过程仅供内部使用所以这里应该定义一个私有函数，在定义一个公有函数来调用对应的私有函数。
public:
// 拷贝构造
BSTree(const BSTree<K>& t) {
_root = Copy(t._root);
}
private:
Node* Copy(Node* root) {
if (root == nullptr) {
return nullptr;
}
Node* copy = new Node(root->_key); // 深拷贝需重新分配内存
copy->_left = Copy(root->_left);
copy->_right = Copy(root->_right);
return copy;
}
public:
// 赋值重载
BSTree<K>& operator=(const BSTree<K>& t) {
swap(_root, t._root);
return *this;
}
public:
// 析构函数
~BSTree() {
Destroy(_root);
}
private:
void Destroy(Node* root) {
if (root == nullptr) {
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
// 1 插入数据 - 不支持插入已有数据
bool Insert(const K& key) {
// 树为空，则直接新增结点，赋值给 root 指针
if (_root == nullptr) {
_root = new Node(key);
return true;
}
// 由于二叉搜索树的特征，所以要先找到插入的位置；
// 由于要改变节点直接之间的指向关系，所以要定义两个变量
// 一个变量用于遍历，一个用于储存要插入位置的父节点，方便改变节点之间的指向关系
Node* cur = _root; // 用于遍历
Node* parent = nullptr; // 用于储存要插入位置的父节点
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;
}
// 2 查找数据
bool Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_key < key) // 从根开始比较，查找 x，x 比根的值大则往右边查找
{
cur = cur->_right;
}
else if (cur->_key > key) // x 比根值小则往左边查找
{
cur = cur->_left;
}
else {
return true; // 找到返回
}
}
return false; // 走到到空，还没找到，这个值不存在。
}
首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。
如果查找元素存在则分以下四种情况：（假设要删除的结点为 x）
总结：情况 1 可以当成 2 或者 3 处理，效果是一样的。
// 删除数据
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 {
// 找到了，准备删除数据
// 分为三种情况
// 1 左孩子为空，左右孩子为空可以一起处理
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* pMinRight = cur;
Node* minRight = cur->_right;
// 找到右子树中值最小的节点
while (minRight->_left) {
pMinRight = minRight;
minRight = minRight->_left;
}
// 交换键值
std::swap(cur->_key, minRight->_key);
// 删除最小节点
if (pMinRight->_left == minRight) {
pMinRight->_left = minRight->_right;
} else {
pMinRight->_right = minRight->_right;
}
delete minRight;
}
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 << " ";
_InOrder(root->_right);
}
上面我们实现的二叉搜索树，节点中只储存了一个值 (key)，key，称为关键码，关键码即为需要搜索到的值，使用这种搜索二叉树只需要判断 key 是否存在。key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了（性质）。
这里还有一种搜索二叉树：(key, value) 结构的二叉搜索树：
每一个关键码还是 key，但是每一个关键码都有与之对应的值 value，value 可以任意类型对象。所以树的结构中 (结点) 除了需要存储 key 还要存储对应的 value，注意增/删/查还是以 key 为关键字在二叉搜索树的规则下操作，这里不支持修改 key，支持修改 value。
namespace key_value {
template<class K, class V> struct BSTreeNode {
BSTreeNode<K, V>* _left;
BSTreeNode<K, V>* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value) :_left(nullptr), _right(nullptr), _key(key), _value(value) {}
};
template<class K, class V> class BSTree {
typedef BSTreeNode<K, V> Node;
public:
// 强制生成
BSTree() = default;
// 拷贝构造
BSTree(const BSTree<K, V>& t) {
_root = Copy(t._root);
}
// 赋值重载
BSTree<K, V>& operator=(const BSTree<K, V>& t) {
swap(_root, t._root);
return *this;
}
~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 {
// 准备删除
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* pMinRight = cur;
Node* minRight = cur->_right;
while (minRight->_left) {
pMinRight = minRight;
minRight = minRight->_left;
}
std::swap(cur->_key, minRight->_key);
if (pMinRight->_left == minRight) {
pMinRight->_left = minRight->_right;
} else {
pMinRight->_right = minRight->_right;
}
delete minRight;
}
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* copy = new Node(root->_key, root->_value);
copy->_left = Copy(root->_left);
copy->_right = Copy(root->_right);
return copy;
}
private:
Node* _root = nullptr;
};
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online