文章目录
- 二叉搜索树
- 1. 二叉搜索树的概念
- 2. 二叉搜索树的接口
- 2.1 查找
- 非递归查找
- 递归查找
- 2.2 中序遍历
- 2.3 插入
- 非递归插入
- 递归插入
- 2.4 删除
- 非递归删除
- 递归删除
- 3. 二叉搜索树的应用
- key搜索模型
- kv搜索模型
- 5. oj题
二叉搜索树
1. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它可以是一颗空树，或者是一个满足如下性质的二叉树：
- 如果左子树不为空，左子树上所有节点的值都小于根节点；
- 如果右子树不为空，右子树上所有节点的值都大于根节点；
且它的左右子树，也满足上述性质。
举个栗子吧，以6为根节点的BST树结构：
template<class K>
struct bstree_node
{
bstree_node<K>(K key)
: _left(nullptr), _right(nullptr), _key(key)
{}
bstree_node<K>* _left;
bstree_node<K>* _right;
K _key;
};
template<class K>
class bstree
{
public:
typedef bstree_node<K> node;
private:
node* _root = nullptr;
};
两个又相同数组构成的二叉树，但是却形成了两个不同树结构。二叉搜索树最大的问题是会退化，比如右单枝，顺序插入时就会退化成一个链表。
搜索二叉树的效率体现在搜索上，最坏情况搜索高度次。所以树的高度越低，性能越好。所以一般不会使用单纯的搜索二叉树，而是使用升级版的AVL 树（平衡二叉搜索树）和红黑树
大概了解一下
AVL 树（平衡二叉搜索树）：
红黑树
2. 二叉搜索树的接口
2.1 查找
若根节点不为空：
- 如果节点值等于 k e y key key，返回 t r u e true true，
- 如果节点值小于 k e y key key，到其右子树中查找，
- 如果节点值大于 k e y key key，到其左子树中查找，
走到空树还没找到，则返回 f a l s e false false。
非递归查找
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;
}
二叉搜索树的查找非常的迅速，在二叉树相对平衡的情况下，时间复杂度高度次 O ( l o g N ) O(logN) O(logN)。最差是线性状态，为 O ( N ) O(N) O(N)。
递归查找
递归函数 find_r 会沿着树的结构向下搜索，每次比较 key 和当前节点的键值，决定向左或向右移动。这种递归调用会一直持续到找到匹配的键值或者遍历完整个树。
基本情况（终止条件）：
如果 root 是 nullptr，表示已经到达了树的末端，没有找到匹配的键值，因此返回 false。
递归调用：
如果 key 小于 root->_key，说明要查找的键值可能在左子树中，因此递归调用 _find_r(root->_left, key)。
如果 key 大于 root->_key，说明要查找的键值可能在右子树中，因此递归调用 _find_r(root->_right, key)。
找到匹配键值：
如果 key 等于 root->_key，表示找到了匹配的键值，立即返回 true。
bool find_r(const K& key)
{
return _find_r(_root, key);
}
bool _find_r(node* root, const K& key)
{
if (root == nullptr)
return false;
if (key < root->_key)
return _find_r(root->_left, key);
else if (key > root->_key)
return _find_r(root->_right, key);
else
return true;
}
2.2 中序遍历
二叉搜索树的中序遍历结果，就是树中元素排成升序的结果。
void inorder()
{
_inorder(_root);
std::cout << std::endl;
}
void _inorder(node* root)
{
if (root == nullptr)
return;
_inorder(root->_left);
std::cout << root->_key << " ";
_inorder(root->_right);
}
一般成员函数在类外调用时，无法直接传入成员变量作参数。故可以将主体逻辑包装成子函数，再由成员函数去调用即可。
void TestBSTree()
{
BSTree<int> t;
int a[] = { 7,1,3,6,4,8,7,9,3,2,5 }; //排序数组
for (auto e : a) {
t.Insert(e); //插入二叉搜索树
}
t.Inorder(); //中序遍历
}
如上代码，相当于利用二叉搜索树排序数组，而二叉搜索树结构天然具有排序加去重的功能。
2.3 插入
二叉搜索树的插入也很简单，共分两种情况：
- 树为空，则直接插入，
- 树不为空，则按性质查找到插入位置，再插入新节点。
cur指针进行比较并向下移动的同时，父指针parent始终指向cur的父节点。当cur走到空的时候，就创建新节点并链接到父节点的指针上。
- 插入的值比当前节点的值小，则插入到左子树中，
- 反之，比当前节点的值大，则插入到右子树中。
非递归插入
非递归插入方法通过迭代遍历二叉搜索树来找到新节点的插入位置。首先检查树是否为空，如果是，则直接将新节点设为根节点。如果树不为空，则从根节点开始，使用一个当前节点指针 cur 和一个父节点指针 parent 来跟踪遍历过程。在遍历过程中，根据新键值与当前节点键值的比较结果，决定向左子树还是右子树移动。如果新键值小于当前节点键值，则移动到左子节点；如果大于，则移动到右子节点。如果遇到相同键值的节点，则插入失败并返回 false。当 cur 为空时，表示已经到达了插入位置，此时根据新键值与 parent 节点键值的比较结果，在父节点的左或右子节点位置插入新节点。这种方法直观且易于理解，不需要额外的栈空间，适用于大多数情况下的树操作。
bool insert(const K& key)
{
// 如果根节点为空，直接将新节点作为根节点
if (_root == nullptr)
{
_root = new node(key);
return true;
}
node* cur = _root;
node* parent = nullptr;
// 循环找到合适的插入位置
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
return false; // 如果存在相同键值的节点，不插入
}
// 根据键值大小插入新节点
if (key < parent->_key)
parent->_left = new node(key);
else
parent->_right = new node(key);
return true;
}
可见，二叉搜索树的每次插入都是把节点放在叶节点的位置上。
递归插入
递归插入方法通过递归调用函数自身来遍历二叉搜索树，并找到新节点的插入位置。递归函数 _insert_r 接受当前节点指针的引用和要插入的键值作为参数。如果当前节点为空，表示到达了插入位置，此时创建一个新节点并将其赋值给当前节点指针，然后返回 true 表示插入成功。如果新键值小于当前节点键值，则递归调用函数在左子树中继续查找插入位置；如果新键值大于当前节点键值，则递归调用函数在右子树中查找。如果遇到相同键值的节点，则返回 false 表示插入失败。递归插入方法简洁优雅，代码量少，但可能会因为递归调用导致栈空间的使用增加，对于大型树结构可能存在性能问题。然而，对于小型或中型树结构，递归插入是一种高效且易于实现的方法。
bool insert_r(const K& key)
{
return _insert_r(_root, key);
}
bool _insert_r(node*& root, const K& key)
{
// 如果当前节点为空，创建新节点并返回true
if (root == nullptr)
{
root = new node(key);
return true;
}
// 根据键值大小递归插入左子树或右子树
if (key < root->_key)
return _insert_r(root->_left, key);
else if (key > root->_key)
return _insert_r(root->_right, key);
else
return false; // 如果存在相同键值的节点，不插入
}
参数类型是节点指针的引用，使得root不仅是节点指针，还是其父节点的左或右孩子指针，修改root也就修改了父节点的左右孩子。
2.4 删除
二叉搜索树的难点在于删除，因为节删除节点需要维护剩余节点的链接关系。
删除叶节点很容易，释放节点并置空父节点的指针即可。删除非叶结点，可以将子树中满足条件的节点替换上来。
如果节点不存在先返回
f
a
l
s
e
false
false，如果存在，则分以下几种情况：
1.直接删除：
| 直接删除 | 解释 |
|---|---|
| 删除的节点有单个子节点 | 左为空就让父节点指向右子树，右为空就让父节点指向左子树 |
| 删除的节点无子节点 | 归类到上一类处理 |
2.替换删除：
| 替换删除 | 解释 |
|---|---|
| 删除的节点左右子节点都有 | 用左树的最大节点，或右树的最小节点，替换被删节点。 |
- 先将左树最大节点的左孩子托，或是右树最小节点的右孩子托付给父节点。
- 再将左树最大节点覆盖待删除的节点。
非递归删除
bool erase(const K& key)
{
node* parent = nullptr; // 父节点指针初始化为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 // 如果搜到到匹配的键值
{
if (!cur->_left) // 如果当前节点没有左子节点
{
if (parent == nullptr)
_root = _root->_right;
else if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
delete cur; // 删除当前节点
}
else if (!cur->_right) // 如果当前节点没有右子节点
{
if (parent == nullptr)
_root = _root->_left;
else if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
delete cur; // 删除当前节点
}
else // 如果当前节点有左右子节点
{
#ifdef 方式1 // 采用方式1删除节点--直接删除
node* min = cur->_right; // 当前节点的右子树中找到最小节点
while (min->_left)
min = min->_left;
K minkey = min->_key;
erase(min->_key);
cur->_key = minkey;
#endif
#ifdef 方式2 // 采用方式2删除节点--替换删除
node* min_parent = cur; // 最小节点的父节点
node* min = cur->_right; // 当前节点的右子树中找到最小节点
while (min->_left)
{
min_parent = min;
min = min->_left;
}
cur->_key = min->_key; // 更新当前节点的键值为最小节点的键值
if (min == min_parent->_left)
min_parent->_left = min->_right;
else
min_parent->_right = min->_right;
delete min; // 删除最小节点
#endif
}
return true;
}
}
return false;
}
递归删除
bool erase_r(const K& key)
{
// 调用递归删除函数，传入根节点指针和搜索键值
return _erase_r(_root, key);
}
bool _erase_r(node*& root, const K& key)
{
// 如果当前子树根节点为空，返回false
if (root == nullptr)
return false;
// 根据搜索键值与当前节点键值的比较，决定进入左子树或右子树进行递归删除
if (key < root->_key)
return _erase_r(root->_left, key);
else if (key > root->_key)
return _erase_r(root->_right, key);
else
{
// 保存当前节点指针
node* del = root;
// 如果当前节点没有左子节点，将右子节点替换当前节点
if (!root->_left)
root = root->_right;
// 如果当前节点没有右子节点，将左子节点替换当前节点
else if (!root->_right)
root = root->_left;
else
{
// 寻找右子树中的最小节点
node* min = root->_right;
while(min->_left)
min = min->_left;
root->_key = min->_key; // 更新当前节点键值为最小节点键值
// 递归删除最小节点，并返回结果
return _erase_r(root->_right, min->_key);
}
// 释放删除节点
delete del;
return true; // 返回删除成功
}
}
3. 二叉搜索树的应用
搜索树有两种应用，key搜索模型和key/value搜索模型。此外，二叉搜索树插入重复值会失败，所以自带去重功能。
key搜索模型
key搜索模型查找返回真假，只能用来判断数据是否存在。应用场景如存储车牌号判断是否放行等。
kv搜索模型
通过key查找对应value，两个值是强相关的映射关系。 应用场景如中英互译，身份绑定等。
cpp
Copy code
// 结构体定义包括键值对节点和左右子节点指针
template<class K, class V>
struct bstree_node
{
bstree_node<K, V>* _left;
bstree_node<K, V>* _right;
K _key;
V _val;
// 构造函数初始化键、值和左右子节点指针
bstree_node<K, V>(const K& key, const V& val)
: _key(key), _val(val), _left(nullptr), _right(nullptr)
{}
};
// 二叉搜索树类
template<class K, class V>
class bstree
{
typedef bstree_node<K, V> node; // 节点类型定义为树节点结构体
public:
// 插入节点函数，传入键值和值，返回插入是否成功
bool insert(const K& key, const V& val)
{
if (_root == nullptr) // 如果根节点为空
{
_root = new node(key, val); // 创建新节点作为根节点
return true;
}
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
return false; // 如果键值相等，返回失败
}
if (key < parent->_key) // 根据父节点键值判断位置插入左子节点或右子节点
parent->_left = new node(key, val); // 创建新节点作为左子节点
else if (key > parent->_key)
parent->_right = new node(key, val); // 创建新节点作为右子节点
return true; // 返回插入成功
}
// 查找键值对应节点，返回找到的节点指针，如果不存在返回空指针
node* 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 cur; // 找到匹配键值时返回当前节点
}
return nullptr; // 没找到返回空指针
}
// 删除节点函数，传入键值，返回删除是否成功
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 // 找到匹配键值的节点
{
if (!cur->_left) // 如果当前节点没有左子节点
{
if (!parent) // 如果父节点为空，说明当前节点为根节点
_root = _root->_right; // 将根节点替换为右子节点
else if (cur == parent->_left) // 如果当前节点是父节点的左子节点
parent->_left = cur->_right; // 将父节点的左子节点替换为当前节点的右子节点
else
parent->_right = cur->_right; // 将父节点的右子节点替换为当前节点的右子节点
delete cur; // 删除当前节点
}
else if (!cur->_right) // 如果当前节点没有右子节点
{
if (!parent) // 如果父节点为空，说明当前节点为根节点
_root = _root->_left; // 将根节点替换为左子节点
else if (cur == parent->_left) // 如果当前节点是父节点的左子节点
parent->_left = cur->_left; // 将父节点的左子节点替换为当前节点的左子节点
else
parent->_right = cur->_left; // 将父节点的右子节点替换为当前节点的左子节点
delete cur; // 删除当前节点
}
else // 如果当前节点有左右子节点
{
node* min_parent = cur; // 最小节点的父节点初始化为当前节点
node* min = cur->_right; // 最小节点指针初始化为当前节点的右子节点
while (min->_left) // 寻找右子树中的最小节点
{
min_parent = min;
min = min->_left;
}
cur->_key = min->_key; // 更新当前节点键值为最小节点键值
cur->_val = min->_val; // 更新当前节点值为最小节点值
if (min == min_parent->_left) // 将最小节点的父节点指向最小节点右子节点
min_parent->_left = min->_right;
else
min_parent->_right = min->_right;
delete min; // 删除最小节点
}
return true; // 返回删除成功
}
}
return false; // 未找到匹配键值，返回删除失败
}
// 中序遍历函数，输出键值对
void inorder()
{
_inorder(_root); // 调用内部中序遍历函数
cout << endl; // 换行
}
// 中序遍历辅助函数
void _inorder(node* root)
{
if (!root) // 如果当前节点为空，返回
return;
_inorder(root->_left); // 递归遍历左子树
cout << root->_key << "-" << root->_val << endl; // 输出当前节点键值对
_inorder(root->_right); // 递归遍历右子树
}
private:
node* _root = nullptr; // 根节点指针初始化为空
};
5. oj题
| OJ链接 | 题解链接 |
|---|---|
| 606. 根据二叉树创建字符串 | 题解 |
| 102. 二叉树的分层遍历 | 题解 |
| 107. 二叉树的层序遍历 II | 题解 |
| 236. 二叉树的最近公共祖先 | 题解 |
| 剑指 Offer 36. 二叉搜索树与双向链表 | 题解 |
| 105. 从前序与中序遍历序列构造二叉树 | 题解 |
| 106. 从中序与后序遍历序列构造二叉树 | 题解 |
| 144. 二叉树的前序遍历 | 题解 |
| 94. 二叉树的中序遍历 | 题解 |
| 145. 二叉树的后序遍历 | 题解 |
![[第五空间 2021]WebFTP、[HCTF 2018]Warmup](https://img-blog.csdnimg.cn/direct/2f7534d5deef4261aa6b0a45e5b9dbdc.png)
