精选优质文档-倾情为你奉上第13章 红黑树第12章我们讨论了在高度为h的二叉查找树能够在O(h)时间完成任何动态集操作，比如查找（SEARCH）,前躯（PREDECESSOR）,后继(SUCCESSOR),最小值（MINIMUM），最大值（MAXIMUM）,插入（INSERT）和删除（DELETE）操作。因此，如果树高矮的时候这些动态集的操作是很快的。如果树高很高的话，那么这些动态集的操作就没有链表快了。红黑树是众多“均衡”查找树中的一种，它可以保证基本的动态集操作在最坏的情况下运行时间为O(lg n)。13.1 红黑树的性质红黑树是一棵二叉查找树，并且每个结点都附加一个额外的存储位：结点颜色，它的值可以是红色或者黑色。通过对根到叶子路径上结点图色的限制，红色黑保证没有哪一条路径是其它路径的二倍长，所以这棵树大致上是平衡的。现在每个结点都包含属性color,key,left,right和p。如果结点没有孩子或者双亲结点不存在（译者著：根结点没有双亲结点，普通的叶子结点没有孩子），那么该结点的这些属性（译者著：孩子或者双亲指针）值是NIL。我们把这些NIL
