Data Structure 05 - Binary Search Tree
# 前置知识
在阅读本文档前,请确保你已经掌握二叉树的基础知识,详见 Data Structure 知识板块中的 04 - Binary Tree 文档。
# 基本概念
二叉查找树 (Binary Search Tree, BST) 是一种追加了特殊限制的二叉树。它对二叉树上的每个节点追加了一个保证,对于任意一个节点上的值p->value
,我们保证:
如果 的左子树非空,那么对于左子树上的任意一个节点 ,都保证
p->value > q->value
。如果 的右子树非空,那么对于右子树上的任意一个节点 ,都保证
p->value < q->value
。
下图是一棵二叉查找树的例子。
二叉查找树也可以递归地定义,根据上述定义,显然每个节点的左子树和右子树也都是二叉查找树。
为便于理解,我们先假设树上不存在等值的节点,并在后文中给出处理多个相同元素的方法。
# 原理
二叉查找树相比于二叉树仅仅追加了两条约束,但这两条约束是具有重大价值的。
考虑一棵普通的二叉树,每个节点上存储了一个值,如果你希望查找二叉树上是否存在某个值 ,那么你只能穷竭搜索整棵树上的所有节点,无论是什么存储方式都是一样。也就是说,在二叉树上查找某个值 是否存在的时间复杂度为 。
当然,在线性表中查找某个值 是否存在的时间复杂度也是 ,不过这在很多情况下是可以设法改进的,不过这不是本文的讨论范围。
事实上,二叉查找树的这一限制,会使得查找某个值 是否存在的期望时间复杂度达到 ,这显然是一个巨大的改进。二叉查找树的核心原理就在于它的查找,无论是插入还是删除操作都是由查找衍生而成的。下面我们将对查找的原理给出详细解释。
首先,在平均情况下,一棵节点个数为 的二叉树的高度是 的。这一点从完全二叉树的高度就能看出,此处不予赘述。
其次,我们考虑如何进行查找。我们从根节点出发开始递归查找,设当前节点为 。
如果
x == p->value
,那么查找成功。如果
x < p->value
,又已知p->value
小于 的右子树上的任意值,这就意味着 的右子树上不可能存在一个节点的值为 ,所以我们只需要在左子树上继续进行查找,递归左子树即可。如果
x > p->value
,又已知p->value
大于 的左子树上的任意值,这就意味着 的左子树上不可能存在一个节点的值为 ,所以我们只需要在右子树上继续进行查找,递归右子树即可。如果
p == nullptr
,表明查找失败。当然,4.要在1.之前进行判断。
递归过程是不断向下的,也就是说,我们最多递归 次,其中 为树的高度,那么在平均情况下查找的时间复杂度为 。
为便于理解,我们以上一小节中的图示为例,举两个查找的例子。
对于 :
来到值为 的根节点,因为
x = 4 < 5 = p->value
,所以答案肯定不可能在右子树,令p = p->left
。来到值为 的节点,因为
x = 4 > 3 = p->value
,所以答案肯定不可能在左子树,令p = p->right
。来到值为 的节点,发现
x = 4 = 4 = p->value
,查找成功。
对于 :
来到值为 的根节点,因为
x = 6 > 4 = p->value
,所以答案肯定不可能在左子树,令p = p->right
。来到值为 的节点,因为
x = 6 < 7 = p->value
,所以答案肯定不可能在右子树,令p = p->left
。发现
p == nullptr
,查找失败。
不知你是否注意到,我们一直强调的是平均情况,因为树的结构并不总是接近、或至少和完全二叉树相差不太远的。对于一棵退化的二叉查找树,树的结构是近似或者就是一条链的。而如果我们又查找的是某个叶子节点处的值,那么查找的时间复杂度将会退化为 。也就是说,在最坏情况下查找的时间复杂度为 。
下图中给出了一棵退化的二叉查找树的例子,如果我们不停地查找 ,那么每次查找都是 的。
# 代码实现
# 定义
二叉查找树的节点定义与二叉树完全一致。
// 定义
class Node {
public:
int value;
Node * left;
Node * right;
public:
Node(int v = 0) : value(v), left(nullptr), right(nullptr) {}
};
Node * root = nullptr;
# 查找操作
前文已经提到过,二叉查找树的核心原理就在于它的查找,无论是插入还是删除操作都是由查找衍生而成的,因此我们就先给出查找的代码实现。至于原理前文已经介绍过了。
查找操作的递归实现如下:
// 查找
Node * find(int value, Node * p = root) {
// 查找失败
if (p == nullptr) {
return nullptr;
}
// 查找成功
if (value == p->value) {
return p;
}
// 递归
if (value < p->value) {
return find(value, p->left);
} else {
return find(value, p->right);
}
}
初始调用 即可。
查找操作的非递归实现如下:
// 查找
Noed * find(int value) {
// 主循环
Node * p = root;
while (p != nullptr) {
// 查找成功
if (value == p->value) {
return true;
}
// 迭代
if (value < p->value) {
p = p->left;
} else {
p = p->right;
}
}
// 查找失败
return false;
}
不比二叉树的遍历,这一非递归实现很好理解。
二叉查找树上的查找操作有很多扩展,其中最简单的就是求二叉查找树上的最大值或最小值。这是很容易做到的事情,比如查询最大值,那么我们只需不断令p = p->right
,直到p->right == nullptr
为止即可。查询最小值同理。
对此我们还可以扩展到求某一棵子树上的最大值或最小值,下面的代码中,传入的参数 即为子树根节点的指针。
查找子树最值的代码实现如下:
// 查找子树最大值
Node * find_max(Node * p) {
// 特判空子树
if (p == nullptr) {
return nullptr;
}
// 主循环
while (p->right != nullptr) {
p = p->right;
}
// 返回
return p;
}
// 查找子树最小值
Node * find_min(Node * p) {
// 特判空子树
if (p == nullptr) {
return nullptr;
}
// 主循环
while (p->left != nullptr) {
p = p->left;
}
// 返回
return p;
}
# 建树
现在我们考虑如何建树,例如给定 个数值 ,你要如何用这些数值来建立一棵二叉查找树。
事实上,二叉查找树的建树并没有什么特别的,我们只需要将这些数值依次插入树中即可。
# 插入操作
二叉查找树的插入是不会破坏树上已有节点的结构的,对于任意的数值,在被插入后都将会成为树上的叶子节点,这一点需要牢记。这样的规定是为了插入的方便,毕竟胡乱插入的话也没有意义。
插入操作事实上是基于查找的,我们只需先在二叉查找树中查找待插入的值,如果找到,则说明已存在,不需要重复插入(当然,如果你希望支持重复元素存在的话,用第一小节所述的方法即可)。否则,直到查找失败为止,那么这一空位就是该数值应当插入的位置,将其插入为叶子节点。
插入操作的递归实现非常简单,和查找的递归实现基本一致。
插入操作的递归实现如下:
// 插入
void insert(Node * & p, int value) {
// 递归终止
if (p == nullptr) {
p = new Node(value);
return;
}
// 递归
if (value < p->value) {
insert(p->left, value);
} else {
insert(p->right, value);
}
}
需要注意的是函数参数中的Node * &
类型,这是一个指针的引用,不能写成Node *
类型,否则你只是修改了一个形参,其父节点的子指针并没有被修改。
插入操作的非递归实现则相对复杂,此时我们无法维护一个指针的引用,因为引用是不能修改其所指向的对象的。因此我们需要维护一个 指针,记录当前节点的父节点,这样我们才能据此进行插入。例如我们在查找失败时的上一步是向左递归的,那么prv->left
即为待插入节点的位置。
至于如何判断上一步是从哪个方向过来的,其实不需要这么麻烦地考虑,我们只需要判断value
和prv->value
的大小关系即可,例如如果value < prv->value
,那么自然是沿着左指针下来的。
事实上,和查找的非递归实现也是非常相似的,所以主体逻辑应该不难理解,注意前文所述的细节问题即可。
插入操作的非递归实现如下:
// 插入
void insert(int value) {
// 特判
if (root == nullptr) {
root = new Node(value);
return;
}
// 主循环
Node * prv = nullptr;
Node * p = root;
while (p != nullptr) {
// 已存在的情况
if (value == p->value) {
return;
}
// 迭代
prv = p;
if (value < p->value) {
p = p->left;
} else {
p = p->right;
}
}
// 插入
if (value < prv->value) {
prv->left = new Node(value);
} else {
prv->right = new Node(value);
}
}
之前提到过,退化的二叉查找树的性能很差,并且二叉查找树非常容易发生退化。学完插入操作后你应该能明白,只要我们有序地插入若干个元素,例如依次插入 ,就会得到一条链。此时二叉查找树的各种操作的时间复杂度都将退化到 。
# 删除操作
要想删除指定的某个数值,显然我们需要先查找到它的位置,如果查找失败自然就不需要删除了。
如果待删除节点是一个叶子节点,那么问题很好解决,但它还可能是非叶子节点,我们必须对此进行处理。总之,删除操作比插入操作要复杂不少。
为便于描述,我们设 为待删除节点, 为 的父节点, 为 的左右子节点。
对删除操作的处理可以分三种情况讨论:
- 待删除节点是叶子节点。
此时直接将节点删除即可。
- 待删除节点只有一个子节点。
此时将 或 连同以该子节点为根节点的子树一起上移,用 或 代替 的位置即可。
我们证明这不会破坏二叉查找树的性质,这很简单。假设 是 的左子节点(是右子节点同理可证),那么以 为根节点的子树上的所有节点上的值都比 上的值要小,因此将以 或 为根节点的子树代替原先以 为根节点的子树,都不会破坏 的性质。而 或 的性质本就未受影响,因此以这样的策略删除 是合理的。
注意在代码实现时不能直接 delete q
,在前面更基础的教程中应当已经提到过类似的问题了。
- 待删除节点有两个子节点。
这种情况则有些复杂,但也并没有那么困难,只是相对复杂而已。
因为存在两个子树 和 ,我们不能像第二种情况那样直接挪移上去。我们考虑从这两棵子树中找到一个合适的节点代替 的位置,使得二叉查找树的性质不变。找到思路就容易了,显然可以选择左子树中的最大值或者右子树中的最小值。
以左子树中的最大值为例,记最大节点为 。首先,因为 是选定的最大值,所以 必然大于以 为根节点的子树上的所有节点上的值。其次,因为 原本属于左子树,所以 必然小于以 为根节点的子树上所有节点上的值。因此用 替代 后二叉查找树的性质不变。右子树中的最小值同理,二者等价,凭个人喜好选择即可。
根据二叉查找树的基本原理,左子树中的最大节点 ,要么是叶子节点,要么只有左子节点。因为如果 有右子节点,则它的右子树上一定存在更大的节点。因此在将 移走时,只需执行类似于处理删除操作的情况1和情况2的处理方式即可。
在实际的代码实现中,我们有如下的一些技巧可以精简代码。
对于情况1和情况2,在代码实现时,情况1可以被归入情况2内,因为用 的空左子树 来替换 事实上等价于将 直接删除,本来就是令
p = nullptr
。对于情况3,在用左子树最大值 来代替当前节点 时,为减少复杂的指针操作,我们直接将 中的数值替换掉 中的数值,然后递归去将节点 真正删除。也可以直接将节点 删除然后让 取代 ,但那样需要一些比较复杂的指针操作,既然可以避免,为什么不呢。
删除操作的递归实现如下:
// 删除
void erase(Node * & p, int value) {
// 递归终止
if (value == p->value) {
// 分类讨论
if (p->left != nullptr && p->right != nullptr) {
// 获取左子树最大值
Node * np = find_max(p->left);
// 更新
p->value = np->value;
// 递归
erase(p->left, np->value);
} else {
// 删除
Node * q = p;
p = (p->left != nullptr ? p->left : p->right);
delete q;
}
return;
}
// 递归
if (value < p->value) {
erase(p->left, value);
} else {
erase(p->right, value);
}
}
删除操作的非递归实现待补。
# 处理重复元素
之前我们假设树上不存在等值的节点,现在我们考虑如何处理多个相同的元素。有两种主要的方法。
# 用多个节点来存储副本
其实很简单,只要将二叉查找树的判断条件 x < p->value
和 x > p->value
改为如下两组之一即可:
判断条件
x <= p->value
和x > p->value
。判断条件
x < p->value
和x >= p->value
。
但是不能使用x <= p->value
和 x >= p->value
,学完二叉查找树你应该能发现,如果这样设置判断条件,当 x == p->value
时,我们究竟应该插入到左子树还是右子树?这在逻辑上就有很大的问题。
这种解决方案非常简单粗暴,但是存在较大的弊端,例如难以支持一些高级查询操作,也难以对某个元素的出现次数进行计数。
# 在节点上添加统计信息
我们为每个节点额外增加一个成员变量 ,用于记录该元素值的出现次数,这可以省去很多麻烦,且易于扩展。
// 定义
class Node {
public:
int value;
Node * left;
Node * right;
int cnt;
public:
Node(int v = 0) : value(v), left(nullptr), right(nullptr), cnt(1) {}
};
此时我们需要对插入和删除操作稍作修改,以便维护 的值。下面的代码示例均以递归实现为例。
在插入操作中,如果在查找过程中发现存在一个节点满足 value == p->value
,则应当修改 值,而不是创建新的节点。
void insert(Node * & p, int value) {
// 递归终止
// ...
// 更新
if (p->value == value) {
p->cnt ++;
return;
}
// 递归
// ...
}
在删除操作中,如果在查找过程中发现存在一个节点满足 value == p->value
,则应当修改 值,而不是执行删除动作。
// 删除
void erase(Node * & p, int value) {
// 递归终止
if (value == p->value) {
// 更新
if (p->cnt > 1) {
p->cnt --;
return;
}
// 分类讨论
// ...
return;
}
// 递归
// ...
}
你也可以扩展出全部删除的操作,将所有值为 value
的元素全部删除,不考虑 cnt
的值并和过去一样直接执行删除动作即可。
# 应用
二叉查找树的一个重要性质是,对一棵二叉查找树进行中序遍历,可以直接得到一个有序的升序序列。这个性质只要知道就很简单,自己想一下就明白了。
但是除此以外,因为退化的二叉查找树的性能很差,各类操作的时间复杂度可以退化到 ,和在一个普通的线性表上操作一样低效,而且二叉查找树还非常容易发生退化,比如进行一系列有序元素的插入。
因此,普通的二叉查找树缺乏实用价值。幸运的是,平衡树能够很好地解决二叉查找树的退化问题,此处不予赘述,详见下一篇文档。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01