当前位置：首页 > ds >正文

数据结构：二叉搜索树（Binary Search Tree）

ds 2025/8/18 18:30:54

我们想解决什么问题？

二叉搜索树的诞生

定义、结构与性质

定义

结构（代码实现）

核心性质

一个重要的警告：最坏情况

用途

总结一下今天的内容：

我们想解决什么问题？

在学习任何数据结构之前，我们先忘掉所有高大上的名词，回到一个最原始、最基本的需求：查找数据。

假设我们有一堆杂乱无章的数据，比如 [15, 8, 20, 3, 12]。

场景1：使用普通数组（或链表）

如果数据存放在一个普通数组或链表中，你想找一个数字，比如 12，你唯一的办法就是从头到尾一个一个地看。

15 是不是 12？不是。
8 是不是 12？不是。
...
12 是不是 12？是！找到了。

这种方法最差情况下需要把所有元素都看一遍。如果数据量是 n 个，那么查找的时间复杂度就是 O(n)。当数据量非常大时，比如几百万、上亿，这种查找速度是无法接受的。

场景2：能不能快一点？—— 排序数组 + 二分查找

我们马上想到一个优化：如果数组是有序的，事情就好办了。

比如我们把上面的数据排序后得到 [3, 8, 12, 15, 20]。

现在再找 12，我们可以用“二分查找”：

先看中间的元素 12。哦，一次就找到了！运气真好。
如果我们想找 10 呢？

先看中间的 12。10 < 12，说明 10 如果存在，一定在 12 的左边。
我们在左边的 [3, 8] 这个子数组里找，看它的中间元素 3 (或8)。10 > 3，说明 10 在 3 的右边。
... 最终我们发现找不到。

这个过程，每一步都把搜索范围缩小一半。这使得查找速度变得飞快，时间复杂度是 O(logn)。这是一个巨大的飞跃！

新的矛盾：插入和删除的代价

有序数组的查找效率顶级，但它有一个致命弱点：插入和删除非常困难。

假设我们想在 [3, 8, 12, 15, 20] 中插入一个 10。为了维持数组的有序性，我们必须：

找到 10 应该插入的位置（在 8 和 12 之间）。
将 12, 15, 20 这些元素集体向后移动一个位置，给 10 腾出空间。
放入 10。

这个“移动”操作，在最坏的情况下（比如插入一个比所有数都小的数），需要移动 n 个元素，时间复杂度是 O(n)。删除同理。

小结一下我们当前的困境：

数据结构	查找效率	插入/删除效率
普通数组/链表	O(n)	O(1) (链表) / O(n) (数组)
有序数组	O(logn)	O(n)

我们想要一个两全其美的方案：

既有像有序数组一样 O(logn) 的查找速度，又有像链表一样 O(1) 或近似的插入/删除效率（不需要大规模移动元素）。

二叉搜索树的诞生

如何把“有序数组的二分查找思想”和“链表的灵活插入/删除”结合起来呢？

让我们回头看二分查找的核心思想：

每一次比较，都把数据分为“比我小的”、“比我大的”两部分，然后只在其中一部分继续查找。

我们可以用“链表”的指针思想来模拟这个“划分”的过程。

我们不把数据排成一条线，而是让每个数据节点像链表一样，有指针。但是它不止一个next指针。
为了划分出“左边（小的）”和“右边（大的）”两个区域，我们给每个节点两个指针：一个 left 指针，指向比它小的数的集合；一个 right 指针，指向比它大的数的集合。

我们来模拟一下这个结构是如何形成的。假设我们依次收到这些数字：15, 8, 20, 3, 12。

第一个数 15：它是第一个，就作为我们的“根”（root）。

    15/  \NULL NULL

第二个数 8：8 < 15，根据我们的规则（小的放左边），它应该在 15 的左边。所以我们让 15 的 left 指针指向 8。

    15/8

第三个数 20：20 > 15，根据规则（大的放右边），它在 15 的右边。

    15/  \8    20

第四个数 3：

和根 15 比较，3 < 15，应该去左边。
到了 8，和 8 比较，3 < 8，应该去 8 的左边。

    15/  \8    20/
3

第五个数 12：

和根 15 比较，12 < 15，去左边。
到了 8，和 8 比较，12 > 8，应该去 8 的右边。

    15/  \8    20/ \
3   12

看！我们凭空创造出了一个“树”形结构。这个结构就叫做二叉搜索树 (Binary Search Tree, BST)。

定义、结构与性质

现在我们可以给它一个正式的定义了。

定义

二叉搜索树，首先它是一棵二叉树（每个节点最多有两个子节点），同时它必须满足搜索树特性：对于树中的任意一个节点 node：

如果 node 的左子树不为空，则其左子树上所有节点的值都小于 node 的值。
如果 node 的右子树不为空，则其右子树上所有节点的值都大于 node 的值。
node 的左、右子树也分别是二叉搜索树。

这是一个递归的定义，非常重要。它保证了整个树的任何一部分都满足这个“左小右大”的规则。

结构（代码实现）

根据上面的推导，一个“节点”需要包含三个信息：

它自己的数据值（data 或 key）。
一个指向它左边子节点的指针（left）。
一个指向它右边子节点的指针（right）。

所以，我们可以用 C/C++ 的 struct 来定义这个节点。

// 定义二叉搜索树的节点
struct Node {int data;       // 节点存储的数据Node* left;     // 指向左子树的指针Node* right;    // 指向右子树的指针
};

这个定义非常清晰，但每次创建一个新节点时，我们都需要手动给 data, left, right 赋值，有点麻烦。比如：

Node* newNode = new Node();
newNode->data = 15;
newNode->left = NULL;  // 在C++中，更推荐用 nullptr，但为了兼容C风格和避免高级语法，我们用 NULL
newNode->right = NULL;

用构造函数来简化

为了方便，我们可以给这个结构体加一个构造函数（Constructor），让创建节点这个动作变得更简单。这不算高级语法，是 C++ 结构体/类的基础功能。

#include <cstddef> // 为了使用 NULL// 定义二叉搜索树的节点 (带构造函数)
struct Node {int data;Node* left;Node* right;// 构造函数：当我们创建一个新节点时，会自动调用这个函数Node(int value) {data = value;left = NULL;   // 初始化时，新节点没有左右孩子right = NULL;}
};

现在，创建一个新节点就干净多了：

Node* newNode = new Node(15); // 一行代码完成创建和初始化

这个 Node 结构就是二叉搜索树的基本组成单位。整棵树由这些节点通过 left 和 right 指针连接而成。我们通常会用一个单独的指针，比如 Node* root;，来指向整棵树的根节点。

核心性质

二叉搜索树最重要的性质，都源于它“左小右大”的定义。

有序性：这是 BST 最核心的性质。它不是像数组一样线性有序，而是一种结构化的有序。
中序遍历得到有序序列：这是一个非常神奇且重要的性质。如果我们按照“左子树 -> 根节点 -> 右子树”的顺序来访问树中的所有节点（这被称为中序遍历），我们得到的结果序列一定是有序的！
- 以上面的树为例：[15, 8, 20, 3, 12]
- 中序遍历过程：先遍历15的左子树[8, 3, 12] -> 再访问15 -> 再遍历15的右子树[20]
- 遍历[8, 3, 12]时：先遍历8的左子树[3] -> 再访问8 -> 再遍历8的右子树[12]
- 最终访问顺序是：3, 8, 12, 15, 20。看，一个有序的序列诞生了！这个性质让 BST 可以用来排序。
查找效率：在一个“比较平衡”（即不过于偏向一边）的BST中，查找一个元素的路径长度大致是树的高度。每次比较，我们都可以在左子树或右子树中选择一个，从而将问题规模减半，这和二分查找的逻辑一模一样。因此，在理想情况下，查找、插入、删除的时间复杂度都是 O(logn)，其中 n 是节点的数量。

一个重要的警告：最坏情况

如果插入的数据本身就是有序的，比如 [1, 2, 3, 4, 5]，会发生什么？

1 成为根。
2 > 1，成为 1 的右孩子。
3 > 1 且 3 > 2，成为 2 的右孩子。
...

最终形成的树会是这样：

1\2\3\4\5

这棵树退化成了一个链表！在这种情况下，查找一个元素（比如 5）需要从头走到尾，时间复杂度退化为 O(n)。这是 BST 的一个主要缺点。

为了解决这个问题，后来才发展出了更复杂的自平衡二叉搜索树，如 AVL 树和红黑树，它们通过一些旋转操作来确保树不会变得过于“倾斜”。但这是后话了，我们先理解基础的 BST。

用途

理解了它的定义和性质，它的用途也就水到渠成了。

快速查找/索引：这是它的核心价值。当需要频繁地查找、插入、删除一个动态集合中的元素时，BST 是一个非常好的选择。比如数据库的索引系统，很多就是基于 BST 的变种（如 B+ 树）来实现的。
实现 Map 和 Set：在很多编程语言的标准库中，需要保持元素有序的关联容器（如 C++ 的 std::map 和 std::set）的底层实现通常就是一种自平衡的二叉搜索树（红黑树）。它们利用 BST 的特性来保证 key 的唯一性和有序性，并提供高效的操作。
排序：如前所述，对一个 BST 进行中序遍历，就可以得到一个有序的元素序列。这可以作为一种排序算法，虽然效率不如专门的排序算法（如快速排序），但也是其性质的一个直接应用。

总结一下今天的内容：

动机（第一性）：我们想同时拥有有序数组的快速查找能力和链表的灵活插入/删除能力。
推导：通过“指针”来模拟二分查找的“划分”思想，即用 left 指针域代表“小的部分”，right 指针域代表“大的部分”，自然而然地构建出了一棵“树”。
定义：对于任意节点，其左子树所有节点的值都比它小，右子树所有节点的值都比它大。
结构：用一个包含 data、left 指针、right 指针的 struct Node 来表示，并通过构造函数简化创建过程。
性质：核心是有序性，一个重要的体现是中序遍历可以得到有序序列。理想情况下的操作效率是 O(logn)，但存在退化成链表的 O(n) 的最坏情况。
用途：主要用于需要高效动态操作（查、增、删）的有序数据集。