红黑树基本概念 · 融合风（象牙 + Obsidian 入口）

速查

满足5 条性质的二叉排序树：根黑、叶(NIL)黑、红节点子必黑、根到叶黑高相同、非红即黑。高度 $h \leq 2\log_2(n+1)$，查找 O(log n)；插入/删除最多 2/3 次旋转。

核心概念 ▾

红黑树是一棵满足五条性质的二叉排序树：

每个节点非红即黑；
根节点是黑色；
叶节点（NIL 哨兵）是黑色；
若一节点是红色，则它的两个子节点都是黑色（不存在连续红）；
任意节点到其所有后代叶子路径上，黑色节点数相同（黑高相同）。

黑高 bh(x)：从某节点（不含它自身）到叶节点路径上的黑色节点数。

关键推论有 n 个内部节点的红黑树高度 $h \leq 2\log_2(n+1)$，这保证所有操作 O(log n)。

红黑树 vs AVL 树

比较项	红黑树	AVL 树
平衡标准	黑高相同（宽松）	左右子树高差 ≤ 1（严格）
高度	$\leq 2\log_2(n+1)$	$\leq 1.44\log_2(n+2)$
插入旋转	最多 2 次	最多 2 次
删除旋转	最多 3 次	O(log n) 次
查找效率	略低	略高
适用场景	插入删除频繁	查找频繁

常见考法 ▾

考法	解题套路
判断是否红黑树	逐条验证 5 条性质
插入后的调整	新节点红色，依据叔父节点颜色分情况旋转 / 变色
删除后的调整	依据兄弟节点及其子节点颜色分情况处理
求树高上界	$h \leq 2\log_2(n+1)$
与 AVL 对比	红黑树插入删除效率高，AVL 查找效率高

易错点 ▾

易错清单

⚠️ 性质 4 是「红节点的孩子必黑」，不是「黑节点的孩子必红」。
⚠️ NIL 叶节点也算节点，且必须为黑色。
⚠️ 黑高计算不含当前节点本身。
⚠️ 高度上界是 $2\log_2(n+1)$，不是 $\log_2 n$。
⚠️ 插入的节点一定为红色（减少违反性质 5 的可能）。

核心结论 ▾

红黑树是二叉排序树的自平衡实现，5 条性质保证树不退化。
高度上界 $h \leq 2\log_2(n+1)$，保证 O(log n) 操作。
插入时新节点为红色，最多 2 次旋转 + 变色。
删除时最多 3 次旋转 + 变色。
比 AVL 更适合频繁插入删除；工程应用广泛（Java TreeMap、Linux CFS 调度器）。

记忆卡片 ▾

5 条性质是什么？

①非红即黑 ②根黑 ③叶(NIL)黑 ④红子必黑 ⑤根到叶黑高相同。

高度上界？

$h \leq 2\log_2(n+1)$。

插入时新节点颜色？

红色（避免违反性质 5）。

删除最多几次旋转？

3 次；插入最多 2 次。

交互动画 · 逐条验证 5 条性质 ▾

验证一棵红黑树是否满足全部 5 条性质

点各按钮逐条检验；黄色圈 = 正在检查的结点

性质 2 根黑、3 NIL 黑、4 无连续红、5 黑高相同均为合法判定；高度上界 $h \leq 2\log_2(n+1)$。

相关知识点

avl-tree binary-search-tree b-tree

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。