15 红黑树总结
一、红黑树的介绍
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
红黑树，作为一棵二叉查找树，满足二叉查找树的一般性质。下面，来了解下 二叉查找树的一般性质。
二叉查找树
二叉查找树，指一棵空树或者具有下列性质的二叉树：
因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。
红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色、旋转和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质：
正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。
补充
补充：红黑树的 5 条性质：
- 每个节点要么红色，要么黑色。
- 根节点是黑色。
- 每个叶子节点（NIL 空节点）是黑色。
- 红色节点的子节点必须是黑色（不能连续两红）。
- 从任一节点到其所有后代叶子节点的简单路径上，包含相同数目的黑色节点（黑高一致）。
由性质 4、5 可推出：根到叶的最长路径不超过最短路径的 2 倍，因此 n 个节点的红黑树高度稳定在 O(log n)，查找/插入/删除最坏 O(log n)。插入新节点默认染红色（避免立刻违反性质 5），若插入后父节点也是红色则需要通过 变色 + 旋转（左旋/右旋）修复。
来源整理自：我的有道云笔记
