二叉查找树

二叉搜索树是一种二叉树，对任意结点，其左子树所有结点值小于该结点值，右子树所有结点值大于该结点值，利用该性质可高效完成查找、插入与删除操作。

January 1, 1968数据结构1分钟阅读

二叉查找树（Binary Search Tree，简称 BST），也称二叉搜索树、二叉排序树，是一种非常经典且基础的数据结构。它在二叉树的基础上增加了一条核心性质，使得查找、插入和删除节点的操作都能高效完成。

对于二叉查找树中的任意一个节点 $N$ ：

左子树 中所有节点的值都小于节点 $N$ 的值。
右子树 中所有节点的值都大于节点 $N$ 的值。
节点 $N$ 的左、右子树也各自是一棵二叉查找树。

关键特性：如果对一棵二叉查找树进行中序遍历（左 -> 根 -> 右），得到的结果是一个严格递增的有序序列。

从根节点开始。

如果目标值等于当前节点值，查找成功。
如果目标值小于当前节点值，向左子树继续查找。
如果目标值大于当前节点值，向右子树继续查找。

平衡二叉搜索树 — 例如查找值 5：先访问根 4，5>4 转向右孩子 6； $5<6$ 转向左孩子 5，查找成功。

类似于查找过程。

从根节点出发比较，比当前节点小就往左走，大就往右走。
直到找到空位置（NULL），将新节点作为叶子节点插入该位置。

二叉搜索树 insert (8) 插入过程 — 二叉搜索树插入示例 insert (8)：从根节点沿比较规则向下遍历，橙色线条为查找路径，最终将 8 作为新叶子节点完成插入

对于二叉查找树（BST）来说，删除操作相当棘手。主要的挑战源于一个节点最多可以有两个子节点。因此，如果你从树中删除一个节点，该如何处理它的子节点？别忘了，我们还必须维护 BST 的性质：左子树中的值必须小于或等于该节点的值，而右子树中的值必须大于或等于该节点的值。

事实证明，在删除节点时主要有三种特殊情况：

节点没有子节点（它是一个叶子节点）
节点恰好有一个子节点
节点有两个子节点

要删除的节点是叶子节点（无子节点）：直接删除即可。

二叉搜索树 remove (7)，删除叶子结点示例 — 二叉搜索树删除示例 remove (7)：待删除节点 7 是叶子节点，直接移除该节点即可，不改动树其余部分

要删除的节点只有一个子节点：用其子节点替代当前节点的位置。

二叉搜索树 remove (4)，删除单孩子结点示例 — 二叉搜索树删除示例 remove (4)：待删节点 4 仅有一个左子节点 3，删除节点 4 后，由其子节点 3 向上接替它在树中的位置

要删除的节点有两个子节点：

找到该节点的前驱（左子树中的最大值）或后继（右子树中的最小值）。
用前驱或后继的值替换当前节点的值。
转而删除原来的前驱或后继节点（此时目标变成了情况 1 或情况 2）。

二叉搜索树 remove (2)，删除双孩子结点示例 — 二叉搜索树删除示例 remove (2)：待删节点 2 拥有左右两棵子树，选取其中序后继 3 顶替被删节点的位置，再移除原后继节点，维持二叉搜索树有序特性。

操作	平均时间复杂度	最坏时间复杂度
查找	$O(\log n)$	$O(n)$
插入	$O(\log n)$	$O(n)$
删除	$O(\log n)$	$O(n)$

如果插入的数据本身就是有序的（例如依次插入 1, 2, 3, 4, 5, 6, 7），BST 会退化成一条单链表：

二叉搜索树斜树，最坏退化形态 — 二叉搜索树最坏退化形态：全部节点仅有右子节点，树退化为单向链表

此时树的高度从 $\log n$ 变为 $n$ ，所有操作的时间复杂度都会降级为 $O(n)$ 。

为了解决 BST 在极端情况下退化成链表的问题，后续衍生出了多种自平衡二叉查找树，它们通过在插入/删除时进行旋转等调整，保持树的高度近似为 $\log n$ ：

AVL 树：严格平衡树，查找效率极高，但插入和删除时的旋转成本稍高。
红黑树 (Red-Black Tree)：弱平衡树，在查找效率与插入/删除开销之间取得了极佳平衡，广泛应用于各种编程语言的标准库中（如 C++ std::map/std::set、Java TreeMap 等）。