红黑树可视化
当前序列—
树为空。插入一个整数开始。
记口诀
左根右，根叶黑，不红红，黑路同
- 左根右
- 左子 < 根 < 右子（二叉搜索树顺序）。
- 根叶黑
- 根是黑色；NIL 空叶也视为黑色。
- 不红红
- 红色节点的两个孩子都必须是黑色，不能红连红。
- 黑路同
- 从任一节点到其后代空叶的每条路径，黑色节点数目相同。
插入手算
黑叔旋转染色，红叔染色上移
黑叔旋转染色
叔叔为黑（含 NIL）：按 LL / LR / RL / RR 旋转，再把父染黑、祖父染红。
红叔染色上移
叔叔为红：父和叔染黑、祖父染红，把红连红冲突上移到祖父，再继续检查。
红黑树五条性质
- 01每个节点不是红就是黑。
- 02根节点是黑色。
- 03所有 NIL 空叶视为黑色。
- 04红色节点的两个子节点都是黑色（不能红连红）。
- 05从任一节点到其后代空叶的每条路径，黑色节点数目相同。