二叉搜索树 (Binary Search Tree, BST)
每个节点左子树值小于根、右子树值大于根。中序遍历得到有序序列。不平衡时退化为链表。
结构定义
typedef struct BSTNode {
int key;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;函数签名
| 函数 | 平均复杂度 | 最坏复杂度 | 说明 |
|---|---|---|---|
BSTNode* bst_insert(BSTNode *root, int key) | O(log n) | O(n) | 插入 |
BSTNode* bst_search(BSTNode *root, int key) | O(log n) | O(n) | 查找 |
BSTNode* bst_delete(BSTNode *root, int key) | O(log n) | O(n) | 删除 |
BSTNode* bst_min(BSTNode *root) | O(log n) | O(n) | 最小节点 |
void bst_inorder(BSTNode *root) | O(n) | O(n) | 中序遍历 |
void bst_free(BSTNode *root) | O(n) | O(n) | 后序释放 |
删除的三种情况
BSTNode* bst_delete(BSTNode *root, int key) {
if (!root) return NULL;
if (key < root->key)
root->left = bst_delete(root->left, key);
else if (key > root->key)
root->right = bst_delete(root->right, key);
else {
/* 情况 1: 叶子节点 */
if (!root->left && !root->right) { free(root); return NULL; }
/* 情况 2: 仅一个子节点 */
if (!root->left) { BSTNode *t = root->right; free(root); return t; }
if (!root->right) { BSTNode *t = root->left; free(root); return t; }
/* 情况 3: 两个子节点 — 找后继（右子树最小）替换 */
BSTNode *succ = bst_min(root->right);
root->key = succ->key;
root->right = bst_delete(root->right, succ->key);
}
return root;
}退化问题
插入有序序列 1, 2, 3, …, n 时 BST 退化为单链表，高度 O(n)。解决方案：AVL树 或 二叉堆。