问题精选-数据结构

一、红黑树及应用

1.1 红黑树

红黑树(R-B Tree, 全称 Red-Black Tree)是一种特殊的二叉查找树, 其中每个节点都有颜色, 红色或者黑色。

红黑树(平衡的排序二叉树)，满足以下性质：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点
根据性质5，我们得出：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

红黑树的关键性质：内部保证有序，旋转开销小，整体相对平衡。

1.2 红黑树的应用和时间复杂度

• 主要是 Java 中的 TreeMap 和 TreeSet. jdk1.8 之后, HashMap 的table中的链表长度大于8的时候也是用红黑树。

• 时间复杂度: 查找, 插入, 删除都可以在 O(log n) 内完成. 且节点数为 n 的数高度最大为 2log(n+1)。