目录
一、二叉搜索树
1.1 概念
二叉搜索树（Binary Search Tree）是一种特殊的二叉树，也称二叉排序树。
- 二叉搜索树的左右子树也分别为二叉搜索树。即对于任意节点，它的非空左子树所有节点的值都小于这个节点的值，它的非空右子树所有节点的值都大于这个节点的值。
通过中序遍历，我们可以得到一个有序数列，因此也叫二叉排序树。
1.2 操作
以此二叉搜索树为例：
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
1.2.1 查找操作
查找值 key :
- 从根节点开始比较，如果 key 小于这个节点的值，则往左边查找；如果 key 大于这个节点的值，则往右边查找；
- 重复上述过程；
- 直到找到 key 或到空节点为止。
例：
1.2.2 插入操作
插入值 key :
- 若树为空，则新增值为 key 的节点且赋值给根节点；
- 若树非空，从根节点开始，若 key 小于当前节点的值，向左子树递归插入；若 key 大于当前节点的值，向右子树递归插入，找到的空节点即要插入的位置。
1.2.3 删除操作
删除操作稍微复杂一些，需要考虑多种情况。
删除值 key :
- 查找 key 是否在二叉搜索树中，若不存在，则返回；若存在值为 key 的节点 del ，则分为4种情况：
a.del 无孩子节点 b.del 只有左孩子节点
c.del 只有右孩子节点 d.del 左右均有孩子节点 - 但实际上，情况a可以被归并到情况b或c里，因此只用考虑三种情况：
b——>删除 del 且让 del 的父节点指向 del 的左节点
c——>删除 del 且让 del 的父节点指向 del 的右节点
d——>找到右子树的最小值节点，用其值替代被删除节点的值，然后删除右子树的最小值节点。
注意b/c的特殊情况：如果 del 是根节点，那么就直接让它的孩子节点成为根节点
1.3 实现
非递归实现较为容易理解，但递归实现代码更简洁，逻辑更清晰；推荐使用递归实现。
#pragma once
#include <iostream>
using namespace std;
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;//左孩子节点
BSTreeNode<K>* _right;//右孩子节点
K _key;
BSTreeNode(const K& key)
:_left(nullptr),
_right(nullptr),
_key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool InSert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key);
if (key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
//先找到要被删除的节点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到了要被删除的节点，接下来有4种情况：
// 1.cur无孩子节点 2.cur左为空
// 3.cur右为空 4.cur左右均有节点
//但实际中，我们可以将1归类到第2或3种情况里
// 左为空
if (cur->_left == nullptr)
{
// 特殊情况
if (cur == _root)
{
_root = _root->_right;
}
// 将cur的父节点指向cur的右孩子节点,此时需要判断cur在parent左边还是右边
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 = _root->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
//左右均有节点
else
{
//找到右子树中最小的节点（即最左节点），将cur的值与其交换，再删除这个节点（找左子树的最大节点也行）
parent = cur;
Node* subLeft = cur->_right;
while (subLeft->_left)
{
parent = subLeft;
subLeft = subLeft->_left;
}
std::swap(cur->_key, subLeft->_key);
//subLeft可能有右节点，因此要将其右节点和父节点连接起来
//若之前的cur->_right有左节点，那么subLeft一定是parent的左节点
//若cur->_right无左节点，那么subLeft就是parent的右节点
//->所以还需要判断
if (subLeft == parent->_left)
{
parent->_left = subLeft->_right;
}
else
{
parent->_right = subLeft->_right;
}
delete subLeft;
}
return true;
}
}
return false;
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
//递归实现查找
bool FindR(const K& key)
{
return _FindR(_root);
}
//递归实现插入
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
//递归实现删除
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
BSTree() = default;// c++11
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
std::swap(_root, t->_root);
return *this;
}
~BSTree()
{
Destroy(_root);
}
private:
void Destroy(Node*& root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
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;
}
bool _EraseR(Node*& root, const K& key)//传引用不需要记录父节点
{
if (root == nullptr)
{
return false;
}
if (key < root->_key)
{
return _EraseR(root->_left, key);
}
else if (key > root->_key)
{
return _EraseR(root->_right, 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;
}
std::swap(root->_key, subLeft->_key);
// 转化为在右子树中删除key
return _EraseR(root->_right, 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->_left)
{
return _FindR(root->_left, key);
}
else return true;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
Node* _root = nullptr;
};1.4 性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：
因此二叉搜索树的查找时间复杂度最坏为O(N)
当退化成单支树，二叉搜索树就失去了其性能。若要保证高效性，通常会使用平衡二叉树（如 AVL 树、红黑树）来维护其平衡性，从而确保查找、插入和删除操作的时间复杂度接近 O(logn)。
二、二叉搜索树的应用
2.1 K模型
K模型即只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值。
- 应用场景:
门禁系统：以车辆的识别码作为 Key 构建二叉搜索树，通过查找树判断车辆识别码是否合法，从而决定是否放行；
单词拼写检查：以词库中所有单词作为 Key 构建二叉搜索树，检索目标单词是否存在，存在则表示拼写正确。
2.2 KV模型
KV模型的每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对。
- 应用场景：
英汉词典：通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
统计单词次数：统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。