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

二叉搜索树（Binary Search Tree）完全指南

news 2026/5/26 4:05:01

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 与当前节点值比较决定向左或向右。
直到找到一个空位置，将新节点插入。

注意：通常不允许插入重复值，若允许则可约定插入到左子树或右子树，或增加计数字段。

cpp

Node* 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 中最复杂的操作，需要分三种情况处理：

删除叶子节点：直接删除，将其父节点对应指针置空。
删除只有一个子节点的节点：用其子节点替换该节点。
删除有两个子节点的节点：找到该节点的中序后继（或中序前驱），用后继的值替换当前节点，然后递归删除后继节点（后继最多只有一个右子节点，问题退化）。

中序后继：当前节点右子树中的最小值节点（即右子树中最左边的节点）。

cpp

Node* 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）：借助队列，按层访问。

cpp

void 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 节点结构定义

cpp

struct Node { int val; Node* left; Node* right; Node(int x) : val(x), left(nullptr), right(nullptr) {} };

4.2 查找（迭代版本）

cpp

Node* 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 插入（迭代版本）

cpp

Node* 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 辅助函数：最小值、最大值、前驱、后继

cpp

Node* 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::map，Java 的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₂(n+1)。

五条性质：

每个节点是红色或黑色。
根节点是黑色。
每个叶子节点（NIL）是黑色。
红色节点的子节点必须为黑色（即不能有两个连续红色）。
从任一节点到其每个叶子的所有路径包含相同数目的黑色节点。

操作：插入和删除后通过变色和旋转（左旋、右旋）维护性质。

应用：Linux 内核、C++ STL map/set、Java TreeMap 等。

6.3 树堆（Treap）

Treap = Tree + Heap，每个节点有一个随机优先级，同时满足 BST 性质（按键值）和堆性质（按优先级）。通过旋转维护堆性质，实现简单，期望 O(log n)。

6.4 B 树/B+ 树

用于磁盘存储的平衡多路搜索树，节点可存储多个键值，降低树高，减少 I/O 次数。B+ 树的所有数据均存储在叶子节点，并形成链表，广泛用于数据库索引。

7. 常见面试题与算法题精选

7.1 验证二叉搜索树

题目：给定一棵二叉树，判断其是否为合法的 BST。

解法：中序遍历判断是否递增，或递归传递上下界。

cpp

bool 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); }