1. 基础概念与定义1.1 什么是二叉搜索树二叉搜索树Binary Search Tree简称 BST是一种特殊的二叉树它满足左小右大的递归性质。更正式地说对于树中的任意节点node若其左子树非空则左子树上所有节点的值均小于node.val若其右子树非空则右子树上所有节点的值均大于node.val左子树和右子树本身也各自是一棵二叉搜索树。这一性质使得 BST 能够高效地支持查找、插入、删除等动态集合操作平均时间复杂度为 O(log n)。1.2 BST 的性质与结构唯一性通常假设 BST 中不存在重复元素实际可通过增加计数或允许重复并约定放置规则处理。有序性对 BST 进行中序遍历左-根-右将得到一个递增序列。动态性元素可随时插入或删除而不需要像数组那样整体移动。1.3 术语解释节点Node包含键值key、左孩子指针、右孩子指针。根节点Root树的入口。叶子节点Leaf左右孩子均为空的节点。父节点Parent、子节点Child、兄弟节点Sibling等常规二叉树术语同样适用。高度Height从该节点到最远叶子节点的边数或节点数依定义不同。2. 核心操作详解2.1 查找Search给定一个键值key在 BST 中查找是否存在该元素。算法逻辑从根节点开始。若当前节点为空返回null未找到。若key 当前节点值返回当前节点。若key 当前节点值递归进入左子树。若key 当前节点值递归进入右子树。时间复杂度O(h)其中 h 为树的高度。cpp// 递归实现 Node* search(Node* root, int key) { if (root nullptr || root-val key) return root; if (key root-val) return search(root-left, key); else return search(root-right, key); }2.2 插入Insert在 BST 中插入一个新节点必须保持 BST 性质。算法逻辑若树为空直接创建新节点作为根。否则从根开始根据 key 与当前节点值比较决定向左或向右。直到找到一个空位置将新节点插入。注意通常不允许插入重复值若允许则可约定插入到左子树或右子树或增加计数字段。cppNode* insert(Node* root, int key) { if (root nullptr) return new Node(key); if (key root-val) root-left insert(root-left, key); else if (key root-val) root-right insert(root-right, key); // 若 key 已存在根据需求忽略或更新计数 return root; }2.3 删除Delete删除操作是 BST 中最复杂的操作需要分三种情况处理删除叶子节点直接删除将其父节点对应指针置空。删除只有一个子节点的节点用其子节点替换该节点。删除有两个子节点的节点找到该节点的中序后继或中序前驱用后继的值替换当前节点然后递归删除后继节点后继最多只有一个右子节点问题退化。中序后继当前节点右子树中的最小值节点即右子树中最左边的节点。cppNode* findMin(Node* root) { while (root root-left) root root-left; return root; } Node* deleteNode(Node* root, int key) { if (root nullptr) return root; if (key root-val) root-left deleteNode(root-left, key); else if (key root-val) root-right deleteNode(root-right, key); else { // 找到要删除的节点 // 情况1 2只有一个子节点或没有子节点 if (root-left nullptr) { Node* temp root-right; delete root; return temp; } else if (root-right nullptr) { Node* temp root-left; delete root; return temp; } // 情况3有两个子节点 Node* temp findMin(root-right); // 中序后继 root-val temp-val; // 复制值 root-right deleteNode(root-right, temp-val); // 删除后继 } return root; }2.4 遍历Traversal前序遍历Preorder根 → 左 → 右。用于复制树。中序遍历Inorder左 → 根 → 右。结果有序。后序遍历Postorder左 → 右 → 根。用于删除树。层序遍历Level-order借助队列按层访问。cppvoid inorder(Node* root) { if (root) { inorder(root-left); cout root-val ; inorder(root-right); } }3. 性能分析与退化问题3.1 时间复杂度推导在理想情况下BST 是平衡的高度 h ≈ log₂(n)因此查找、插入、删除的平均时间复杂度为 O(log n)。但在最坏情况下例如插入顺序为递增或递减序列BST 退化为一条链表高度 h n此时所有操作退化为 O(n)。3.2 平衡树的概念为了解决退化问题计算机科学家发明了自平衡二叉搜索树如 AVL 树、红黑树它们通过旋转等机制保证树的高度始终维持在 O(log n)。我们将在第 6 节详细讨论。3.3 空间复杂度每个节点存储常数额外信息值、左右指针因此空间复杂度为 O(n)。4. 代码实现C/Java 风格4.1 节点结构定义cppstruct Node { int val; Node* left; Node* right; Node(int x) : val(x), left(nullptr), right(nullptr) {} };4.2 查找迭代版本cppNode* searchIter(Node* root, int key) { while (root ! nullptr root-val ! key) { if (key root-val) root root-left; else root root-right; } return root; }4.3 插入迭代版本cppNode* insertIter(Node* root, int key) { if (root nullptr) return new Node(key); Node* cur root; Node* parent nullptr; while (cur ! nullptr) { parent cur; if (key cur-val) cur cur-left; else if (key cur-val) cur cur-right; else return root; // 已存在不插入 } if (key parent-val) parent-left new Node(key); else parent-right new Node(key); return root; }4.4 辅助函数最小值、最大值、前驱、后继cppNode* getMin(Node* root) { while (root root-left) root root-left; return root; } Node* getMax(Node* root) { while (root root-right) root root-right; return root; } // 前驱左子树的最大值 或 向上追溯到第一个作为右子树的祖先 Node* getPredecessor(Node* root, Node* target) { if (target-left) return getMax(target-left); Node* pred nullptr; while (root) { if (target-val root-val) { pred root; root root-right; } else if (target-val root-val) { root root-left; } else break; } return pred; } // 后继右子树的最小值 或 向上追溯到第一个作为左子树的祖先 Node* getSuccessor(Node* root, Node* target) { if (target-right) return getMin(target-right); Node* succ nullptr; while (root) { if (target-val root-val) { succ root; root root-left; } else if (target-val root-val) { root root-right; } else break; } return succ; }5. 二叉搜索树的应用5.1 动态数据集合的维护BST 提供了一种高效的动态数据结构支持插入、删除、查找、最小值、最大值等操作常用于需要频繁变动的有序集合。5.2 排序与顺序统计排序将元素依次插入 BST然后中序遍历得到有序序列。时间复杂度 O(n log n)但最坏 O(n²)。顺序统计若在每个节点维护子树大小可在 O(log n) 时间内找到第 k 小的元素即顺序统计树。5.3 作为其他数据结构的基础许多高级数据结构如 C STL 的std::set和std::mapJava 的TreeSet和TreeMap内部基于红黑树一种平衡 BST实现。BST 也是数据库索引B 树和文件系统的基础。6. 进阶变体平衡二叉搜索树6.1 AVL 树定义AVL 树是最早的自平衡二叉搜索树它要求对于任意节点其左子树和右子树的高度差平衡因子的绝对值不超过 1。平衡因子BF(node) height(node.left) - height(node.right)取值 -1、0、1。旋转操作当插入或删除导致平衡因子超出范围时通过以下四种旋转恢复平衡LL 旋转右旋在左子树的左子树插入。RR 旋转左旋在右子树的右子树插入。LR 旋转先左旋后右旋在左子树的右子树插入。RL 旋转先右旋后左旋在右子树的左子树插入。复杂度所有操作 O(log n)但旋转开销略高于红黑树。6.2 红黑树定义红黑树是一种近似平衡的 BST通过节点的颜色红/黑和五条性质保证树的高度不超过 2 log₂(n1)。五条性质每个节点是红色或黑色。根节点是黑色。每个叶子节点NIL是黑色。红色节点的子节点必须为黑色即不能有两个连续红色。从任一节点到其每个叶子的所有路径包含相同数目的黑色节点。操作插入和删除后通过变色和旋转左旋、右旋维护性质。应用Linux 内核、C STL map/set、Java TreeMap 等。6.3 树堆TreapTreap Tree Heap每个节点有一个随机优先级同时满足 BST 性质按键值和堆性质按优先级。通过旋转维护堆性质实现简单期望 O(log n)。6.4 B 树/B 树用于磁盘存储的平衡多路搜索树节点可存储多个键值降低树高减少 I/O 次数。B 树的所有数据均存储在叶子节点并形成链表广泛用于数据库索引。7. 常见面试题与算法题精选7.1 验证二叉搜索树题目给定一棵二叉树判断其是否为合法的 BST。解法中序遍历判断是否递增或递归传递上下界。cppbool isValidBST(TreeNode* root, long long minVal LONG_MIN, long long maxVal LONG_MAX) { if (!root) return true; if (root-val minVal || root-val maxVal) return false; return isValidBST(root-left, minVal, root-val) isValidBST(root-right, root-val, maxVal); }7.2 恢复二叉搜索树题目BST 中有两个节点被错误交换请在不改变结构的情况下恢复。解法中序遍历找到两个逆序对交换节点值。7.3 二叉搜索树与双向链表的转换题目将 BST 转换为有序的双向链表要求原地转换即不能创建新节点。解法中序遍历维护前驱指针进行链接。7.4 第 K 小的元素题目在 BST 中找到第 k 小的元素。解法中序遍历计数或利用节点子树大小信息进行二分。7.5 最近公共祖先LCA题目给定 BST 中两个节点求它们的最近公共祖先。解法利用 BST 性质从根开始若当前节点值介于两者之间则为 LCA否则进入同侧子树。8. 总结与扩展思考二叉搜索树是一种基础而强大的数据结构它将有序性与动态性完美结合。然而原始 BST 的性能依赖于输入顺序这催生了平衡二叉搜索树的出现。理解 BST 的核心操作是掌握所有树形数据结构的关键而它的各种变体AVL、红黑树、Treap、B 树则在实际系统中发挥着不可替代的作用。进阶方向实现一个支持顺序统计、区间操作、持久化可持久化 Treap的 BST。深入学习红黑树的插入和删除实现细节。研究 B 树在数据库索引中的具体应用。
二叉搜索树（Binary Search Tree）完全指南
发布时间：2026/5/26 4:03:17
1. 基础概念与定义1.1 什么是二叉搜索树二叉搜索树Binary Search Tree简称 BST是一种特殊的二叉树它满足左小右大的递归性质。更正式地说对于树中的任意节点node若其左子树非空则左子树上所有节点的值均小于node.val若其右子树非空则右子树上所有节点的值均大于node.val左子树和右子树本身也各自是一棵二叉搜索树。这一性质使得 BST 能够高效地支持查找、插入、删除等动态集合操作平均时间复杂度为 O(log n)。1.2 BST 的性质与结构唯一性通常假设 BST 中不存在重复元素实际可通过增加计数或允许重复并约定放置规则处理。有序性对 BST 进行中序遍历左-根-右将得到一个递增序列。动态性元素可随时插入或删除而不需要像数组那样整体移动。1.3 术语解释节点Node包含键值key、左孩子指针、右孩子指针。根节点Root树的入口。叶子节点Leaf左右孩子均为空的节点。父节点Parent、子节点Child、兄弟节点Sibling等常规二叉树术语同样适用。高度Height从该节点到最远叶子节点的边数或节点数依定义不同。2. 核心操作详解2.1 查找Search给定一个键值key在 BST 中查找是否存在该元素。算法逻辑从根节点开始。若当前节点为空返回null未找到。若key 当前节点值返回当前节点。若key 当前节点值递归进入左子树。若key 当前节点值递归进入右子树。时间复杂度O(h)其中 h 为树的高度。cpp// 递归实现 Node* search(Node* root, int key) { if (root nullptr || root-val key) return root; if (key root-val) return search(root-left, key); else return search(root-right, key); }2.2 插入Insert在 BST 中插入一个新节点必须保持 BST 性质。算法逻辑若树为空直接创建新节点作为根。否则从根开始根据 key 与当前节点值比较决定向左或向右。直到找到一个空位置将新节点插入。注意通常不允许插入重复值若允许则可约定插入到左子树或右子树或增加计数字段。cppNode* insert(Node* root, int key) { if (root nullptr) return new Node(key); if (key root-val) root-left insert(root-left, key); else if (key root-val) root-right insert(root-right, key); // 若 key 已存在根据需求忽略或更新计数 return root; }2.3 删除Delete删除操作是 BST 中最复杂的操作需要分三种情况处理删除叶子节点直接删除将其父节点对应指针置空。删除只有一个子节点的节点用其子节点替换该节点。删除有两个子节点的节点找到该节点的中序后继或中序前驱用后继的值替换当前节点然后递归删除后继节点后继最多只有一个右子节点问题退化。中序后继当前节点右子树中的最小值节点即右子树中最左边的节点。cppNode* findMin(Node* root) { while (root root-left) root root-left; return root; } Node* deleteNode(Node* root, int key) { if (root nullptr) return root; if (key root-val) root-left deleteNode(root-left, key); else if (key root-val) root-right deleteNode(root-right, key); else { // 找到要删除的节点 // 情况1 2只有一个子节点或没有子节点 if (root-left nullptr) { Node* temp root-right; delete root; return temp; } else if (root-right nullptr) { Node* temp root-left; delete root; return temp; } // 情况3有两个子节点 Node* temp findMin(root-right); // 中序后继 root-val temp-val; // 复制值 root-right deleteNode(root-right, temp-val); // 删除后继 } return root; }2.4 遍历Traversal前序遍历Preorder根 → 左 → 右。用于复制树。中序遍历Inorder左 → 根 → 右。结果有序。后序遍历Postorder左 → 右 → 根。用于删除树。层序遍历Level-order借助队列按层访问。cppvoid inorder(Node* root) { if (root) { inorder(root-left); cout root-val ; inorder(root-right); } }3. 性能分析与退化问题3.1 时间复杂度推导在理想情况下BST 是平衡的高度 h ≈ log₂(n)因此查找、插入、删除的平均时间复杂度为 O(log n)。但在最坏情况下例如插入顺序为递增或递减序列BST 退化为一条链表高度 h n此时所有操作退化为 O(n)。3.2 平衡树的概念为了解决退化问题计算机科学家发明了自平衡二叉搜索树如 AVL 树、红黑树它们通过旋转等机制保证树的高度始终维持在 O(log n)。我们将在第 6 节详细讨论。3.3 空间复杂度每个节点存储常数额外信息值、左右指针因此空间复杂度为 O(n)。4. 代码实现C/Java 风格4.1 节点结构定义cppstruct Node { int val; Node* left; Node* right; Node(int x) : val(x), left(nullptr), right(nullptr) {} };4.2 查找迭代版本cppNode* searchIter(Node* root, int key) { while (root ! nullptr root-val ! key) { if (key root-val) root root-left; else root root-right; } return root; }4.3 插入迭代版本cppNode* insertIter(Node* root, int key) { if (root nullptr) return new Node(key); Node* cur root; Node* parent nullptr; while (cur ! nullptr) { parent cur; if (key cur-val) cur cur-left; else if (key cur-val) cur cur-right; else return root; // 已存在不插入 } if (key parent-val) parent-left new Node(key); else parent-right new Node(key); return root; }4.4 辅助函数最小值、最大值、前驱、后继cppNode* getMin(Node* root) { while (root root-left) root root-left; return root; } Node* getMax(Node* root) { while (root root-right) root root-right; return root; } // 前驱左子树的最大值 或 向上追溯到第一个作为右子树的祖先 Node* getPredecessor(Node* root, Node* target) { if (target-left) return getMax(target-left); Node* pred nullptr; while (root) { if (target-val root-val) { pred root; root root-right; } else if (target-val root-val) { root root-left; } else break; } return pred; } // 后继右子树的最小值 或 向上追溯到第一个作为左子树的祖先 Node* getSuccessor(Node* root, Node* target) { if (target-right) return getMin(target-right); Node* succ nullptr; while (root) { if (target-val root-val) { succ root; root root-left; } else if (target-val root-val) { root root-right; } else break; } return succ; }5. 二叉搜索树的应用5.1 动态数据集合的维护BST 提供了一种高效的动态数据结构支持插入、删除、查找、最小值、最大值等操作常用于需要频繁变动的有序集合。5.2 排序与顺序统计排序将元素依次插入 BST然后中序遍历得到有序序列。时间复杂度 O(n log n)但最坏 O(n²)。顺序统计若在每个节点维护子树大小可在 O(log n) 时间内找到第 k 小的元素即顺序统计树。5.3 作为其他数据结构的基础许多高级数据结构如 C STL 的std::set和std::mapJava 的TreeSet和TreeMap内部基于红黑树一种平衡 BST实现。BST 也是数据库索引B 树和文件系统的基础。6. 进阶变体平衡二叉搜索树6.1 AVL 树定义AVL 树是最早的自平衡二叉搜索树它要求对于任意节点其左子树和右子树的高度差平衡因子的绝对值不超过 1。平衡因子BF(node) height(node.left) - height(node.right)取值 -1、0、1。旋转操作当插入或删除导致平衡因子超出范围时通过以下四种旋转恢复平衡LL 旋转右旋在左子树的左子树插入。RR 旋转左旋在右子树的右子树插入。LR 旋转先左旋后右旋在左子树的右子树插入。RL 旋转先右旋后左旋在右子树的左子树插入。复杂度所有操作 O(log n)但旋转开销略高于红黑树。6.2 红黑树定义红黑树是一种近似平衡的 BST通过节点的颜色红/黑和五条性质保证树的高度不超过 2 log₂(n1)。五条性质每个节点是红色或黑色。根节点是黑色。每个叶子节点NIL是黑色。红色节点的子节点必须为黑色即不能有两个连续红色。从任一节点到其每个叶子的所有路径包含相同数目的黑色节点。操作插入和删除后通过变色和旋转左旋、右旋维护性质。应用Linux 内核、C STL map/set、Java TreeMap 等。6.3 树堆TreapTreap Tree Heap每个节点有一个随机优先级同时满足 BST 性质按键值和堆性质按优先级。通过旋转维护堆性质实现简单期望 O(log n)。6.4 B 树/B 树用于磁盘存储的平衡多路搜索树节点可存储多个键值降低树高减少 I/O 次数。B 树的所有数据均存储在叶子节点并形成链表广泛用于数据库索引。7. 常见面试题与算法题精选7.1 验证二叉搜索树题目给定一棵二叉树判断其是否为合法的 BST。解法中序遍历判断是否递增或递归传递上下界。cppbool isValidBST(TreeNode* root, long long minVal LONG_MIN, long long maxVal LONG_MAX) { if (!root) return true; if (root-val minVal || root-val maxVal) return false; return isValidBST(root-left, minVal, root-val) isValidBST(root-right, root-val, maxVal); }7.2 恢复二叉搜索树题目BST 中有两个节点被错误交换请在不改变结构的情况下恢复。解法中序遍历找到两个逆序对交换节点值。7.3 二叉搜索树与双向链表的转换题目将 BST 转换为有序的双向链表要求原地转换即不能创建新节点。解法中序遍历维护前驱指针进行链接。7.4 第 K 小的元素题目在 BST 中找到第 k 小的元素。解法中序遍历计数或利用节点子树大小信息进行二分。7.5 最近公共祖先LCA题目给定 BST 中两个节点求它们的最近公共祖先。解法利用 BST 性质从根开始若当前节点值介于两者之间则为 LCA否则进入同侧子树。8. 总结与扩展思考二叉搜索树是一种基础而强大的数据结构它将有序性与动态性完美结合。然而原始 BST 的性能依赖于输入顺序这催生了平衡二叉搜索树的出现。理解 BST 的核心操作是掌握所有树形数据结构的关键而它的各种变体AVL、红黑树、Treap、B 树则在实际系统中发挥着不可替代的作用。进阶方向实现一个支持顺序统计、区间操作、持久化可持久化 Treap的 BST。深入学习红黑树的插入和删除实现细节。研究 B 树在数据库索引中的具体应用。
