数据结构

搜索二叉树

左子树小于根小于右子树，中序遍历升序有序

平衡二叉树（AVL树）

严格平衡，左子树和右子树高度差不超过1，通过旋转平衡，O(log n)

红黑树

规则：

• 节点要么是红色要么是黑色
• 根节点一定是黑色
• 叶子节点（NIL）一定是黑色
• 红色节点的子节点一定是黑色的
• 一个节点到他的每个叶子节点一定经过相同数量的黑色节点

近似平衡，最长路径不超过最短路径的 2 倍，O(log n)

B树

平衡n叉树 key数量是子树数量-1 B 树除了“平衡”，还有严格的节点规则（设最小度数 t）：

• 除根节点外，每个节点至少有 t-1 个 key
• 每个节点最多有 2t-1 个 key（也就是最多 2t 个子节点）
• 所有叶子在同一层（这是“平衡”的体现）
• 节点内的 key 有序，查找时在节点内二分 + 选子树往下走

B+树

和B树相比key和子树数量是一致的 叶子节点用链表链起 只在叶子节点存 record/指针

堆

完全二叉树，通常用数组存储（下标 i 的父节点 (i-1)/2，左/右孩子 2i+1、2i+2）

• 大根堆：父 ≥ 子，堆顶是最大值
• 小根堆：父 ≤ 子，堆顶是最小值

核心操作：

• 插入：尾插后向上调整（sift up），O(log n)
• 删除堆顶：堆顶与末尾交换，删末尾，向下调整（sift down），O(log n)
• 建堆：自底向上 heapify，O(n)（不是 n 次插入的 O(n log n)）
• 取最值：O(1)

典型应用：优先队列、Top K、堆排序、Dijkstra / 多路归并

与 BST 对比：堆只保证「父子大小关系」，不保证左右有序；找全局最值 O(1)，但查任意元素无序

哈希表

数组+链表 解决哈希冲突：链地址，开放寻址（线性探测，二次探测）

查找一般用什么数据结构？

最常用的是哈希表（HashMap），平均查找复杂度 O(1)。

如果需要有序查找或范围查询，则使用平衡二叉树（O(log n)）。

对于数据库索引，通常使用 B+ 树。