一、简介

  红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。   红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。   由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

二、特征

  红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。   在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

1.结点是红色或黑色。 2. 根结点是黑色。 3. 所有叶子都是黑色。（叶子是NIL结点） 4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点） 5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。

三、时间复杂度

  由红黑树特征得知，操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，因此想要得出时间复杂度，需要先根据树节点数n得出树的高度h。

定义：从某个结点 x 到叶结点的黑色结点数, 称为此结点的黑高度, 记为 h b ( x ) h_b(x) hb(x)。 结论

1. 以 x 为 根的子树至少包含 2 h b ( x ) − 1 2^{h_b(x)}−1 2hb(x)−1个结点
2. 一棵有 n 个内结点的红黑树高度至多为 2log(n+1)

结论2证明： 设树高 h 由红黑性质 (4), 根结点到叶子路径上的黑结点数至少 h 2 frac{h}{2} 2h, 即 h b ( r o o t ) ⩾ h 2 h_b(root)⩾frac{h}{2} hb(root)⩾2h 再由 1, 得出 n ⩾ 2 h b ( x ) − 1 ⩾ 2 h 2 − 1 n⩾2^{h_b(x)}−1⩾2^{frac{h}{2}}−1 n⩾2hb(x)−1⩾22h−1

  由推导黑色树的高度得出，红黑树的时间复杂为 O ( l o g ( n ) ) O(log(n)) O(log(n))

参考地址

1. 红黑树解读与Java实现

项目源代码地址：https://gitee.com/gaogzhen/algorithm.git