二叉排序树（BST）

为什么需要二叉排序树

顺序查找太慢（O(n)），折半查找虽快但依赖有序顺序表、插入删除代价高。我们需要一种既能高效查找，又能灵活插入删除的数据结构——二叉排序树（Binary Search Tree, BST）应运而生。

BST 将查找与树形结构结合，在理想情况下可以实现 O(log₂n) 的查找、插入和删除，是构造动态查找表的重要方法，也是理解平衡二叉树（AVL）、红黑树等高级结构的基础。

核心思想

二叉排序树是一棵二叉树，它满足以下性质（递归定义）：

左子树上所有结点的值 < 根结点的值
右子树上所有结点的值 > 根结点的值
左、右子树本身也分别是二叉排序树

由此可得一个重要推论：对 BST 进行中序遍历，可以得到一个递增的有序序列。

结点定义：

typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

交互可视化

通过下方的交互动画，你可以逐步观察二叉排序树的执行过程：

加载可视化中...

操作详解

查找操作

从根结点出发，将目标值 key 与当前结点比较：

若 key == 当前结点值，查找成功
若 key < 当前结点值，在左子树中继续查找
若 key > 当前结点值，在右子树中继续查找
若走到空结点，查找失败

BSTNode *BST_Search(BSTree T, int key) {
    while (T != NULL && key != T->key) {
        if (key < T->key)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

查找过程实质上是走了一条从根到目标结点的路径，比较次数 = 路径上的结点数 = 结点所在层次。

插入操作

BST 的插入基于查找：先查找 key 是否已存在，若不存在，则在查找失败的位置插入新结点。

关键步骤：

若树为空，创建新结点作为根
若 key < 当前结点值，递归插入左子树
若 key > 当前结点值，递归插入右子树
若 key == 当前结点值，不插入（BST 中不允许重复关键字）

int BST_Insert(BSTree *T, int key) {
    if (*T == NULL) {
        *T = (BSTree)malloc(sizeof(BSTNode));
        (*T)->key = key;
        (*T)->lchild = (*T)->rchild = NULL;
        return 1;  // 插入成功
    }
    if (key == (*T)->key)
        return 0;  // 已存在，插入失败
    else if (key < (*T)->key)
        return BST_Insert(&((*T)->lchild), key);
    else
        return BST_Insert(&((*T)->rchild), key);
}

插入的新结点一定是叶子结点，这是 BST 插入的重要特征。

不同的插入顺序会构造出不同形态的 BST。例如，序列 {50, 30, 70, 20, 40} 和 {20, 30, 40, 50, 70} 包含相同元素，但前者构造出较平衡的树，后者退化为单支树（类似链表）。

删除操作

BST 的删除较复杂，需要分三种情况讨论（设待删除结点为 z）：

情况一：z 是叶子结点 直接删除，将其父结点对应指针置空。

情况二：z 只有一棵子树 让 z 的子树替代 z 的位置，即用 z 的子结点顶替 z。

情况三：z 有两棵子树 ⭐ 找到 z 的中序后继（即 z 的右子树中最左下的结点 s），用 s 的值替换 z 的值，然后转而删除 s（s 一定没有左子树，转化为情况一或情况二）。

void BST_Delete(BSTree *T, int key) {
    if (*T == NULL) return;
    if (key < (*T)->key) {
        BST_Delete(&((*T)->lchild), key);
    } else if (key > (*T)->key) {
        BST_Delete(&((*T)->rchild), key);
    } else {  // 找到待删除结点
        if ((*T)->lchild == NULL) {
            // 情况一、二：无左子树（含叶子结点）
            BSTNode *temp = *T;
            *T = (*T)->rchild;
            free(temp);
        } else if ((*T)->rchild == NULL) {
            // 情况二：无右子树
            BSTNode *temp = *T;
            *T = (*T)->lchild;
            free(temp);
        } else {
            // 情况三：左右子树都存在，找中序后继
            BSTNode *s = (*T)->rchild;
            while (s->lchild != NULL)
                s = s->lchild;
            (*T)->key = s->key;
            BST_Delete(&((*T)->rchild), s->key);
        }
    }
}

复杂度分析

操作	最好时间复杂度	最坏时间复杂度	说明
查找	O(log₂n)	O(n)	取决于树的高度
插入	O(log₂n)	O(n)	先查找再插入，查找决定时间
删除	O(log₂n)	O(n)	先查找再删除，查找决定时间

查找长度分析（ASL）：

最好情况：BST 接近完全二叉树，树高 h ≈ log₂n，ASL ≈ O(log₂n)
最坏情况：BST 退化为单支树（输入序列有序时），树高 h = n，ASL ≈ (n+1)/2 = O(n)，与顺序查找相同

树形	ASL	等价于
平衡 BST	O(log₂n)	折半查找判定树
单支树	O(n)	顺序查找

空间复杂度：O(1)，查找、插入、删除操作只需常数级辅助空间（递归实现需 O(h) 栈空间）。

考研高频考点

⭐ BST 的性质：中序遍历得到递增序列（选择题/判断题高频）
⭐ 根据插入序列构造 BST（画图题必考）
⭐ 删除操作三种情况的处理方式，特别是有两棵子树时用中序后继替换（大题高频）
⭐ ASL 的计算：给定 BST 求查找成功/失败的 ASL（计算题高频）
⭐ 不同插入顺序 → 不同树形 → 不同查找效率（概念题）
相同关键字集合，不同插入顺序得到不同 BST，但中序遍历结果相同
BST 与折半查找的对比：BST 是动态结构，折半查找依赖静态有序表

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

二叉排序树（BST） ​

为什么需要二叉排序树 ​

核心思想 ​

交互可视化 ​

操作详解 ​

查找操作 ​

插入操作 ​

删除操作 ​

复杂度分析 ​

考研高频考点 ​

相关文章