在了解红黑树之前，先了解下查找树与二叉查找树 。
查找树(search tree)
查找树 是一种数据结构，它支持多种动态集合操作，包括SEARCH，MINIMUM，MAXIMUM，PREDECESSOR,SUCCESSOR,INSERT以及DELETE。它既可以做字典，也可以用作优先队列。
在二叉查找树上执行的基本操作的时间与树的高度成正比。对于一颗含n个结点的完全二叉树，这些操作的最坏情况运行时间为O（n）。
在实际中，并不总能保证二叉查找树是随机构造的，但对于有些二叉查找树的变形来说，各基本操作的最坏情况性能却能保证是很好的。这种变形即为红黑树，其高度为O（lg n）。这种结构对维护随机访问的二级（磁盘）存储器上的数据库特别有效。
二叉查找树
二叉查找树: 设x为二叉查找树中的一个结点。如果y是x的左子树一个结点，则key[y] <=key[x]。如果y是x的右子树中的一个结点，则key[x]<=key[y]。
定理1：
如果x是一棵包含n个结点的子树的跟上，调用INORDER-TREE-WALK过程所需要的时间。对于一棵空子树，INORDER-TREE-WALK只需要很少的一段常量时间（测试x != NIL）,因而有T(0)=c，c为某一正常数。
定理2：
对一棵高度为h的二叉查找树，动态集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR等的运行时间均为O(h)。
定理3：对高度为h的二叉查找树，动态集合操作INSERT和DELETE的运行时间为O(h)。
定理4：一棵在n个关键字上随机构造的二叉查找树的期望高度为O(lg n)。
有了前面的伏笔，现在正式开始介绍红黑树。
红黑树
什么是红黑树
由二叉查找树的定理2：对一棵高度为h的二叉查找树，动态集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR等的运行时间均为O(h)；这样，当树的高度较低时，这些操作的效率都比较高；但是，当树的高度较高时，这些操作的性能可能不比用链表好。红黑树(red-black-tree)是许多“平衡的”查找树中的一种，它能保证在最坏情况下，基本的动态集合操作的时间为O(lg n)。
红黑树的性质：
红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的路径上各个结点着色的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
树中每个结点包含五个域：color，key，left，right和p。如果某个结点没有一个子结点或父结点，则该结点相应的指针(p)域包含值NIL。我们将把这些NIL视为指向二叉查找树的外结点（叶子）的指针，而把带关键字的结点视为树的内结点。
一颗二叉查找树如果满足下面的红黑性质，则为一棵红黑树：
1）每个结点是红的，或是黑的。
2）根结点是黑的。
3）每个叶结点（NIL）是黑的。
4）如果一个结点是红的，则它的两个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
下面是一个红黑树的例子：
红黑树例子
什么是“黑高度”
从某个结点x出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，用bh(x)表示。根据扫面的性质5），黑高度概念是明确定义的，因为从该结点出发的所有下降路径都有相同的黑结点个数。红黑树的黑高度定义为其根结点的黑高度。
引理1： 一棵有n个内结点的红黑树的高度至多为2 lg(n+1)。
查询时间复杂度：
由这个引理可知，动态集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR可用红黑树在O(lg n)时间内实现。
插入时间复杂度：
向一棵含n个结点的红黑树中插入一个新结点的操作可以在O(lg n)时间内完成。
删除时间复杂度：
和n个结点的红黑树上其他基本操作一样，对一个结点的删除要花O(lg n)时间。与插入操作相比，删除操作只是稍微复杂些。
JDK1.8中HashMap底层源码就是红黑树，想要了解的可以挪步 Java源码阅读之红黑树在HashMap中的应用 - JDK1.8
网友评论