算法设计与分析.ppt

证明引理4：由下图有，在左图上，叶X，Z1，Z2的路长为k+2d，而右图， 叶Y， Z1，Z2的路长为2k+d+1,因为kd-1，所以2k+d+1k+2d 而其他路长不变，由此右图epl优于左图epl，引理得证。 证明引理5：当l=2k时，(k为树高，即为完全满二叉树）结论显见；当l≠2k 时，设叶结点在d层和d-1层，此时，2d-1l2d 也即 ， d-1logld 由此有，d-1= ，最后得，epl=l(d-1)+2(l-2d-1), 也即 epl=l +2( l- )，证毕。 证明定理2：由定义，A(n)=epl/l ≥ ≥ ≈nlog n – 1.443n 因为快速排序、归并排序等复杂度已达到此阶，故比较排序已无太大改进 下面来看建一棵2-3-4树的过程 设输入序列为：ASEARCHINGEXAMPLE 则有 这里应注意4结点的分裂 这就是最后的结果。 容易看出2-3-4树有如下性质： ● 2-3树的每片叶子是一样高的，永远不需担心这种树的平衡性； ● 2-3树的插入过程中，每次遇到4结点就分裂，分裂方法如下图： 图 2 结点下接4 结点和3 结点下接4 结点时的转换方法 ●设T是深度为h的2-3树，则T的顶点个数在2 h+1 –1和(3 h+1-1)/2之间。而叶子 数在2h和3h之间。由此 h= ?(log n)，这里，n 是顶点个数或叶片数或二者 之和。 证明：当T全是2结点时，T的顶点数为2 h+1 –1，当T全是3结点时， T的顶 点数为(3 h+1-1)/2，由此命题得证。 ● 2-3-4树一般对4结点保持在下次插入遇到时再分裂，这有助于提高效率， 不必记住从根开始的所有指针。 ● 2-3-4树的优点是绝对平衡，有哪些信誉好的足球投注网站效率高，缺点是要么引起复杂的数据结构 变化，要么浪费空间。解决这个问题的办法是使用红黑树。 红黑树 有哪些信誉好的足球投注网站的复杂度和树高有关，如何使树高保持在O(log n)阶，关键是使对应有哪些信誉好的足球投注网站树比较平衡且易操作实现。AVL树、B树和2-3树都是为此所做的努力。红黑树亦是如此。 下图双线代表红点,单线代表黑点。 从上页下图容易看出红黑树(下称RB树)的一些性质。 ●红黑树(下称RB树)的性质 RB树的结点包含五个域，color,key,left,right,和p(parent)。并且满足： (1)每个结点的color域必须为red或black。 (2)每个叶结点的指针域为NULL。 (3)若一个结点的color域为red，则其子结点为black结点。 (4)从任一结点出发，到其子树上任一叶结点的简单路径上black结点的 个数相等 。 定义：从一结点x到其子树上任一叶结点的简单路径上black结点的 个数 称为该结点的black高，记为bh(x)。 定理：具有n 个内部结点的RB树的树高h≤2log(n+1)。 证明: (1) 先证对RB树上任一结点x有，以x为根的子树上至少有2 bh(x) -1个内部结点。 对高度为0的结点x(x为叶)有2 bh(x) -1=20-1=0,结论成立。设高≤h-1时 结论成立，现证高=h (h0)时结论成立。 设x1,x2为x的两个儿子，则有： bh(x) x=red bh(x) x=red bh(x1)= bh(x2)= bh(x)-1