一、二叉搜索树
1.1 二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
2.2 二叉搜索树操作
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
- 二叉搜索树的查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。 - 二叉搜索树的插入
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
- 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回,
否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
--直接删除
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
--替换法删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点 中，再来处理该结点的删除问题
2.3 二叉搜索树的实现
定义二叉搜索树节点结构体 BSTreeNode
// 二叉搜索树节点结构体
/*template<class K> 表示定义了一个模板类 BSTree，
并且该类可以使用一个类型参数 K，
这样在实际使用时可以将任意类型作为 K 的具体类型*/
template<class K>
struct BSTreeNode
{
// 定义一个别名 Node，指向 BSTreeNode 类型的节点
typedef BSTreeNode<K> Node;
Node* _left; // 左子节点指针
Node* _right; // 右子节点指针
K _key; // 节点键值
// 构造函数，初始化节点的键值，并将左右子节点指针初始化为空指针
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
二叉搜索树类整体结构
// 二叉搜索树类
template<class K>
class BSTree
{
// 定义一个别名 Node，指向 BSTreeNode 类型的节点
typedef BSTreeNode<K> Node;
public:
// 强制生成默认构造函数
// 拷贝构造函数
// 赋值重载运算符
// 析构函数
// 插入节点
// 查找节点
// 删除节点
// 中序遍历
// 递归查找节点
// 递归插入节点
// 递归删除节点
private:
// 递归销毁节点
// 拷贝节点
// 递归删除节点
// 递归插入节点
// 递归查找节点
// 中序遍历
private:
Node* _root = nullptr;
};
- 构造函数
当我们在类的声明中声明了其他构造函数（拷贝构造函数、有参构造函数等）时，如果希望也保留默认构造函数，就可以使用 "= default" 来显式指定生成默认构造函数。在这里，BSTree 类使用 "= default" 来生成默认构造函数，表示编译器将会自动生成默认的构造函数，即无参数的构造函数。这样做的好处是可以确保类的对象能够被正确地创建和初始化
// 强制生成默认构造函数 BSTree() = default;
- 拷贝构造函数
在拷贝构造函数中，首先通过递归调用 Copy 函数拷贝整棵树，保证了深度拷贝，然后将拷贝得到的根节点赋给当前对象的根节点。Copy 函数的作用是拷贝一个节点及其子树，返回新创建的节点，实现对整棵树的拷贝。在 Copy 函数中，如果传入的节点为空，则直接返回空指针；否则，首先创建一个新节点，值为原节点的值。然后递归拷贝左子树和右子树，将拷贝得到的左右子树分别赋给新节点的左右指针，最后返回新创建的节点。
// 拷贝构造函数 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 对象，并在函数内部交换了当前对象的根节点和传入对象的根节点，从而实现了对象之间的赋值操作。具体来说，赋值重载运算符的原理是利用传值方式传递参数，导致会调用传入对象的拷贝构造函数创建一个临时对象，然后通过交换临时对象和当前对象的根节点实现赋值操作。最终返回当前对象的引用，完成赋值过程。
// 赋值重载运算符 BSTree<K>& operator=(BSTree<K> t) { /*原理：=的右值由于参数传递的不是引用， 所以会调用自身的拷贝构造形成一个临时对象， 交换临时对象与左值根节点后，此时左值根节点已经是之前的右值根节点了， 然后返回左值根节点完成赋值， 结束后右值根节点会被析构（即之前的左值）。*/ swap(_root, t._root); //交换两个节点的值 return *this; }
- 析构函数
在析构函数中，调用 Destroy 函数来递归销毁整棵树。Destroy 函数的作用是递归销毁节点及其子树，首先判断当前节点是否为空，如果为空则直接返回；否则，递归调用 Destroy 函数来销毁左子树和右子树，最后释放当前节点的内存。
// 析构函数 ~BSTree() { Destroy(_root); }// 递归销毁节点 void Destroy(Node* root) { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; }
- 插入节点
在该函数中，首先判断树是否为空，如果为空则直接插入新节点作为根节点。若树不为空，则通过循环遍历二叉搜索树，找到合适的位置进行插入。
具体的插入过程如下：
- 初始化父节点指针 parent 为空，当前节点指针 cur 指向根节点。
- 通过循环遍历二叉搜索树，直到找到合适的插入位置。
- 如果待插入值大于当前节点的值，则向右子树移动；如果待插入值小于当前节点的值，则向左子树移动；如果待插入值等于当前节点的值，则说明已存在相同值节点，插入失败。 找到插入位置后，创建新节点并插入到树中，以维持二叉搜索树的性质。
// 插入节点 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; }
递归插入节点
递归插入的函数接收一个节点和目标键值作为参数，如果当前节点为空，则表示找到了要插入新节点的位置，创建新节点并返回 true；否则根据当前节点的键值与目标键值的大小关系选择向左子树或右子树递归插入，直到找到合适的插入位置为止。// 递归插入节点 bool InsertR(const K& key) { return _InsertR(_root, key); }// 递归插入节点 bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) { return _InsertR(root->_right, key); } else if (root->_key > key) { return _InsertR(root->_left, key); } else { return false; } }
- 查找节点
从根节点开始，通过循环遍历二叉搜索树，根据当前节点的键值与目标键值的比较结果来不断向左子树或右子树移动，直到找到目标节点或遍历到空节点为止。
具体的查找过程如下：
- 初始化当前节点指针 cur 指向根节点。
- 通过循环遍历二叉搜索树，不断根据当前节点的键值和目标键值的比较结果来移动到左子树或右子树。
- 如果当前节点的键值小于目标键值，则向右子树移动；如果当前节点的键值大于目标键值，则向左子树移动；如果当前节点的键值等于目标键值，则说明找到目标节点，返回 true。如果遍历到空节点仍未找到目标节点，则返回 false。
// 查找节点 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; }
- 递归查找节点
根据节点的键值与目标键值的大小关系来不断向左子树或右子树递归查找。// 递归查找节点 bool FindR(const K& key) { return _FindR(_root, key); }// 递归查找节点 bool _FindR(Node* root, const K& key) { if (root == nullptr) return false; if (root->_key < key) { return _FindR(root->_right, key); } else if (root->_key > key) { return _FindR(root->_left, key); } else { return true; } }
- 删除节点
删除节点的操作需要考虑节点的左右子节点以及替换节点，具体的删除过程如下：
- 初始化当前节点指针 cur 指向根节点，父节点指针 parent 为 nullptr。
- 通过循环遍历二叉搜索树，根据当前节点的键值与目标键值的比较结果来移动到左子树或右子树，同时更新父节点指针 parent。
- 如果找到待删除节点：
- 如果待删除节点没有左子节点，则将其父节点指向其右子节点，如果待删除节点为根节点，则直接将根节点指向其右子节点；否则将其父节点的左/右子节点指向其右子节点，并释放待删除节点的内存。
- 如果待删除节点没有右子节点，则将其父节点指向其左子节点，如果待删除节点为根节点，则直接将根节点指向其左子节点；否则将其父节点的左/右子节点指向其左子节点，并释放待删除节点的内存。
- 如果待删除节点既有左子节点又有右子节点，则采用替换法删除节点：
- 找到右子树中最小节点 rightMin 及其父节点 rightMinParent，将当前节点的值替换为 rightMin 的值。
- 调整 rightMinParent 的左/右子节点指针，连接 rightMin 的右子节点到其父节点的左/右子节点上，并释放 rightMin 的内存。
// 删除节点 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) // 1.如果当前节点没有左子节点 { if (cur == _root) // 如果当前节点是根节点 { _root = cur->_right; // 将根节点指向当前节点的右子节点 } else { if (cur == parent->_right) // 如果当前节点是父节点的右子节点 { parent->_right = cur->_right; // 将父节点的右子节点指向当前节点的右子节点 } else // 如果当前节点是父节点的左子节点 { parent->_left = cur->_right; // 将父节点的左子节点指向当前节点的右子节点 } } delete cur; // 删除当前节点 return true; } else if (cur->_right == nullptr) // 2.如果当前节点没有右子节点 { if (cur == _root) // 如果当前节点是根节点 { _root = cur->_left; // 将根节点指向当前节点的左子节点 } else { if (cur == parent->_right) // 如果当前节点是父节点的右子节点 { parent->_right = cur->_left; // 将父节点的右子节点指向当前节点的左子节点 } else 如果当前节点是父节点的左子节点 { parent->_left = cur->_left; // 将父节点的左子节点指向当前节点的左子节点 } } delete cur; // 删除当前节点 return true; } else // 3.如果当前节点既有左子节点又有右子节点，采用替换法删除节点 { Node* rightMinParent = cur; // 右子树中最小节点的父节点指针初始化为当前节点 Node* rightMin = cur->_right; // 右子树中最小节点指针初始化为当前节点的右子节点 while (rightMin->_left) // 找到右子树中最小节点 { rightMinParent = rightMin; rightMin = rightMin->_left; } cur->_key = rightMin->_key; // 将当前节点的值替换为右子树中最小节点的值 //通过判断 rightMin 是否等于 rightMinParent 的左子节点，确定应该将右子树中最小节点的右子节点连接到其父节点的左子节点还是右子节点上。 if (rightMin == rightMinParent->_left) rightMinParent->_left = rightMin->_right; // 调整右子树中最小节点的父节点指针 else rightMinParent->_right = rightMin->_right; // 调整右子树中最小节点的父节点指针 delete rightMin; // 删除右子树中最小节点 return true; } } } return false; }
递归删除节点
递归删除的函数接收一个节点和目标键值作为参数，如果当前节点为空，则表示未找到目标节点，返回 false；否则根据当前节点的键值与目标键值的大小关系选择向左子树或右子树递归删除，直到找到目标节点为止。找到目标节点后，根据其子节点情况进行相应的删除操作，并保持二叉搜索树的性质不变。// 递归删除节点 bool EraseR(const K& key) { return _EraseR(_root, key); }// 递归删除节点 bool _EraseR(Node*& root, const K& key) { if (root == nullptr) return false; if (root->_key < key) { return _EraseR(root->_right, key); } else if (root->_key > key) { return _EraseR(root->_left, key); } else { Node* del = root; if (root->_right == nullptr) { root = root->_left; } else if (root->_left == nullptr) { root = root->_right; } else { Node* rightMin = root->_right; while (rightMin->_left) { rightMin = rightMin->_left; } swap(root->_key, rightMin->_key); return _EraseR(root->_right, key); } delete del; 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); }
下面是使用这个二叉搜索树模板类的测试代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include"BinarySearchTree.h"
int main()
{
key::BSTree<int> t;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
t.Erase(3);
t.InOrder();
if (t.Find(4))
{
cout << "找到了该节点" << endl;
}
else
{
cout << "未找到该节点" << endl;
}
return 0;
} 
二、二叉树搜索树的应用
- K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。- KV模型：每一个关键码key，都有与之对应的值Value，即<Key,Value>的键值对。该种方 式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出 现次数就是就构成一种键值对。// 改造二叉搜索树为KV结构 // 结构体：键值对二叉搜索树节点 template<class K, class V> struct BSTreeNode { typedef BSTreeNode<K, V> Node; Node* _left; // 左子节点指针 Node* _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> //K 和 V 分别是模板类的类型参数，用于表示键和值的类型。 class BSTree { typedef BSTreeNode<K, V> Node; public: // 插入节点 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->_right) // 如果当前节点是父节点的右子节点 { parent->_right = cur->_right; // 将父节点的右子节点指针指向当前节点的右子节点 } else { parent->_left = cur->_right; // 将父节点的左子节点指针指向当前节点的右子节点 } } delete cur; // 释放当前节点内存 return true; } else if (cur->_right == nullptr) // 如果当前节点的右子节点为空 { if (cur == _root) // 如果当前节点是根节点 { _root = cur->_left; // 将根节点指针指向当前节点的左子节点 } else { if (cur == parent->_right) // 如果当前节点是父节点的右子节点 { parent->_right = cur->_left; // 将父节点的右子节点指针指向当前节点的左子节点 } else { parent->_left = cur->_left; // 将父节点的左子节点指针指向当前节点的左子节点 } } delete cur; // 释放当前节点内存 return true; } else // 如果当前节点的左右子节点都不为空 { // 替换法 Node* rightMinParent = cur; // 记录当前节点的右子树中最小节点的父节点 Node* rightMin = cur->_right; // 记录当前节点的右子树中最小节点 while (rightMin->_left) // 寻找右子树中最小节点 { rightMin = rightMin->_left; // 不断向左子节点移动直到最小节点 } cur->_key = rightMin->_key; // 将当前节点的键值替换为右子树中最小节点的键值 if (rightMin == rightMinParent->_left) // 如果最小节点是其父节点的左子节点 rightMinParent->_left = rightMin->_right; // 将最小节点的右子树连接到其父节点的左子节点上 else rightMinParent->_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 << " "; _InOrder(root->_right); } private: Node* _root = nullptr; };
应用测试:
创建一个二叉搜索树在词典中查找输入的单词并输出对应的中文翻译#define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; #include"BinarySearchTree.h" int main() { // 输入单词，查找单词对应的中文翻译 key_value::BSTree<string, string> 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) { cout << str << "中文翻译:" << ret->_value << endl; } else { cout << "单词拼写错误，词库中没有这个单词:" << str << endl; } } return 0; }
创建二叉搜索树统计水果出现的次数
#define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; #include"BinarySearchTree.h" int main() { // 统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; key_value::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; }
三、二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
在最优情况下，当二叉搜索树为完全二叉树或者接近完全二叉树时，其平均比较次数为log_2N，其中N是二叉搜索树中节点的个数。这是因为在完全二叉树或接近完全二叉树的情况下，每个节点的左右子树的高度差不超过 1，。当进行查找操作时，由于树的平衡性，每次比较都会将搜索范围减半，类似于二分查找的思想。具体地说，对于一个包含 N 个节点的完全平衡二叉树，大致拥有 2^h - 1 个节点,所以其高度 h 约为 log2(N+1) - 1（或者取整后的值）。树的高度近似为log_2N，而在二叉搜索树中查找一个节点的平均比较次数与树的高度成正比，因此平均比较次数近似为log_2N,时间复杂度为log(N)。
在最差情况下，当二叉搜索树退化为单支树（或者类似单支树）时，其平均比较次数是N/2。
当二叉搜索树完全不平衡、退化成为链状结构时，即每个节点只有一个子节点，导致树的高度与节点数量呈线性关系（树的高度等于节点数量减去1）。假设我们要查找的键在树的最深部，那么的确需要进行N次比较，但这只是一个极端情况。如果我们平均考虑所有可能的查找，比如可能查找的键在树的任何位置，那么平均比较次数就不再是N次。考虑这样一个情况，1到N的数字构成了这个单支树，我们要查找的键可能是这些数字中的任何一个。对于1，我们只需要比较1次；对于2，我们需要比较2次；对于3，我们需要比较3次，以此类推。所以，总的比较次数是1+2+3+...+N，平均比较次数就是(1+2+3+...+N)/N，根据等差数列的求和公式，这个数等于(N+1)/2，也就是约等于N/2。所以在最差情况下，需要遍历大约一半的节点才能找到目标节点，因此平均比较次数为N/2。时间复杂度为O(N)，需要遍历大部分节点才能找到目标节点，效率较低。
