二叉搜索树：高效查找与增删详解

引言在上一篇树结构开篇文章中我们建立了树的基本概念、二叉树的定义和四种遍历方式。本文将继续深入讲解二叉搜索树Binary Search TreeBST——它是最基础的有组织二叉树也是后续学习 AVL 树、红黑树的必经之路。BST 的核心思想非常简单左子树所有节点 根节点 右子树所有节点。这条看似简单的规则让查找、插入、删除操作的时间复杂度从 O(n) 降到了 O(log n)在树保持平衡的前提下。第一部分BST 的定义与性质一、严格定义二叉搜索树BST要么是空树要么满足以下三个条件若左子树非空则左子树上所有节点的值均小于根节点的值若右子树非空则右子树上所有节点的值均大于根节点的值左、右子树本身也是二叉搜索树二、核心性质性质1中序遍历得到有序序列性质2最小值在最左边最大值在最右边// 查找最小值一直向左走 TreeNode* findMin(TreeNode* root) { if (root NULL) return NULL; while (root-left ! NULL) { root root-left; } return root; } // 查找最大值一直向右走 TreeNode* findMax(TreeNode* root) { if (root NULL) return NULL; while (root-right ! NULL) { root root-right; } return root; }性质3每个节点的值域形成区间约束三、BST 节点结构定义#include stdio.h #include stdlib.h #include stdbool.h typedef int ElemType; typedef struct BSTNode { ElemType data; // 数据域 struct BSTNode* left; // 左子节点 struct BSTNode* right; // 右子节点 // 可选struct BSTNode* parent; // 父节点便于向上回溯 } BSTNode;第二部分查找操作一、查找算法原理二、递归实现BSTNode* search_recursive(BSTNode* root, ElemType key) { // 基本情况空树或找到目标 if (root NULL || root-data key) { return root; } // key 小于当前节点去左子树找 if (key root-data) { return search_recursive(root-left, key); } // key 大于当前节点去右子树找 else { return search_recursive(root-right, key); } }三、迭代实现推荐无递归栈溢出风险BSTNode* search_iterative(BSTNode* root, ElemType key) { BSTNode* cur root; while (cur ! NULL) { if (key cur-data) { return cur; // 找到了 } else if (key cur-data) { cur cur-left; // 去左边 } else { cur cur-right; // 去右边 } } return NULL; // 遍历完没找到 }递归 vs 迭代对比实现方式优点缺点递归代码简洁树很深时可能栈溢出迭代无栈溢出风险效率更高代码稍长第三部分插入操作一、插入算法原理BST 的插入总是从根开始找到合适的空位NULL然后创建新节点插入。二、递归实现// 返回插入后的新根节点 BSTNode* insert_recursive(BSTNode* root, ElemType key) { // 找到空位创建新节点 if (root NULL) { BSTNode* newnode (BSTNode*)malloc(sizeof(BSTNode)); if (newnode NULL) { fprintf(stderr, 内存分配失败\n); return NULL; } newnode-data key; newnode-left NULL; newnode-right NULL; return newnode; } if (key root-data) { root-left insert_recursive(root-left, key); } else if (key root-data) { root-right insert_recursive(root-right, key); } // key root-data已存在不插入不允许重复 return root; }三、迭代实现同时记录父节点bool insert_iterative(BSTNode** root, ElemType key) { // 创建新节点 BSTNode* newnode (BSTNode*)malloc(sizeof(BSTNode)); if (newnode NULL) return false; newnode-data key; newnode-left newnode-right NULL; // 空树新节点就是根 if (*root NULL) { *root newnode; return true; } BSTNode* cur *root; BSTNode* parent NULL; // 找到插入位置 while (cur ! NULL) { parent cur; if (key cur-data) { cur cur-left; } else if (key cur-data) { cur cur-right; } else { // 重复值不插入 free(newnode); return false; } } // 挂载到父节点 if (key parent-data) { parent-left newnode; } else { parent-right newnode; } return true; }插入性质新节点始终作为叶子节点插入插入不会改变已有节点的位置插入顺序不同生成的 BST 形状不同第四部分删除操作BST 最复杂的操作一、三种情况总览二、情况1删除叶子节点三、情况2删除只有一个子节点的节点四、情况3删除有两个子节点的节点重点核心思想不是直接删除节点会破坏树结构而是替换值 删除替换节点。两种替换策略为什么后继/前驱一定可以安全删除后继是右子树中最小的节点它一定没有左子树否则更小的值在左边。因此后继最多只有一个右子节点属于情况1或情况2可以直接删除。前驱同理。五、删除操作的完整实现// 查找最小值节点 BSTNode* findMin(BSTNode* node) { if (node NULL) return NULL; while (node-left ! NULL) { node node-left; } return node; } // 删除指定 key 的节点返回新树的根 BSTNode* deleteNode(BSTNode* root, ElemType key) { if (root NULL) return NULL; // 第一步找到要删除的节点 if (key root-data) { root-left deleteNode(root-left, key); } else if (key root-data) { root-right deleteNode(root-right, key); } else { // 第二步找到了分情况处理 // 情况12只有一个子节点或无子节点 if (root-left NULL) { BSTNode* temp root-right; free(root); return temp; } else if (root-right NULL) { BSTNode* temp root-left; free(root); return temp; } // 情况3有两个子节点 // 找中序后继右子树中最小的 BSTNode* successor findMin(root-right); // 用后继的值覆盖当前节点 root-data successor-data; // 递归删除后继节点必定是情况1或2 root-right deleteNode(root-right, successor-data); } return root; }六、删除操作图解总结第五部分完整代码与测试一、完整 BST 实现#include stdio.h #include stdlib.h #include stdbool.h typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode* left; struct BSTNode* right; } BSTNode; // 创建节点 BSTNode* createNode(ElemType val) { BSTNode* node (BSTNode*)malloc(sizeof(BSTNode)); if (node NULL) { fprintf(stderr, 内存分配失败\n); return NULL; } node-data val; node-left NULL; node-right NULL; return node; } // 查找 BSTNode* search(BSTNode* root, ElemType key) { BSTNode* cur root; while (cur ! NULL) { if (key cur-data) return cur; else if (key cur-data) cur cur-left; else cur cur-right; } return NULL; } // 插入 BSTNode* insert(BSTNode* root, ElemType key) { if (root NULL) return createNode(key); if (key root-data) root-left insert(root-left, key); else if (key root-data) root-right insert(root-right, key); return root; } // 查找最小值 BSTNode* findMin(BSTNode* node) { if (node NULL) return NULL; while (node-left ! NULL) node node-left; return node; } // 删除 BSTNode* deleteNode(BSTNode* root, ElemType key) { if (root NULL) return NULL; if (key root-data) root-left deleteNode(root-left, key); else if (key root-data) root-right deleteNode(root-right, key); else { if (root-left NULL) { BSTNode* temp root-right; free(root); return temp; } else if (root-right NULL) { BSTNode* temp root-left; free(root); return temp; } BSTNode* successor findMin(root-right); root-data successor-data; root-right deleteNode(root-right, successor-data); } return root; } // 遍历 void inorder(BSTNode* root) { if (root NULL) return; inorder(root-left); printf(%d , root-data); inorder(root-right); } void preorder(BSTNode* root) { if (root NULL) return; printf(%d , root-data); preorder(root-left); preorder(root-right); } // 释放整棵树 void freeTree(BSTNode* root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); } // 测试主函数 int main() { BSTNode* root NULL; // 构建 BST int values[] {8, 3, 10, 1, 6, 14, 4, 7, 13}; int n sizeof(values) / sizeof(values[0]); printf(插入顺序); for (int i 0; i n; i) { printf(%d , values[i]); root insert(root, values[i]); } printf(\n); // 中序遍历验证有序性 printf(中序遍历); inorder(root); printf(\n); // 前序遍历展示树结构 printf(前序遍历); preorder(root); printf(\n); // 查找测试 printf(\n 查找测试 \n); int keys[] {6, 5, 13}; for (int i 0; i 3; i) { BSTNode* found search(root, keys[i]); printf(查找 %d: %s\n, keys[i], found ? 找到 : 不存在); } // 删除测试 printf(\n 删除测试 \n); // 删除叶子节点 4 printf(删除叶子 4\n); root deleteNode(root, 4); printf(中序遍历); inorder(root); printf(\n); // 删除有一个子节点的节点 10 printf(删除节点 10只有一个右子 14\n); root deleteNode(root, 10); printf(中序遍历); inorder(root); printf(\n); // 删除有两个子节点的节点 3 printf(删除节点 3有两个子节点\n); root deleteNode(root, 3); printf(中序遍历); inorder(root); printf(\n); // 释放 freeTree(root); return 0; }运行结果二、BST 的构建形状与插入顺序的关系第六部分BST 的性能分析一、时间复杂度操作最好情况平衡平均情况最坏情况退化链表查找O(log n)O(log n)O(n)插入O(log n)O(log n)O(n)删除O(log n)O(log n)O(n)二、退化问题退化原因数据以有序升序或降序顺序插入。解决方案使用自平衡二叉搜索树AVL 树、红黑树保证树的高度始终为 O(log n)。总结一、BST 核心操作速查操作核心思想复杂度平衡查找比大小决定向左还是向右O(log n)插入找到合适的空位叶子位置O(log n)删除叶子直接释放O(log n)删除单子子节点顶替O(log n)删除双子找后继/前驱替换值递归删除后继O(log n)二、BST 的三条核心性质性质内容有序性左子树 根 右子树中序有序中序遍历得到升序序列形状不定同一组数据不同插入顺序 → 不同形状三、删除三种情况记忆口诀删除叶子直接删删除单子用子换删除双子找后继替换值后再删原。四、一句话记忆二叉搜索树保证左小右大通过比较大小决定查找方向每次排除一半子树插入始终在叶子位置删除分三种情况处理最核心的是双子找后继替换值中序遍历即得有序序列但插入顺序不当会退化成链表。