算法设计与分析-10红黑树.ppt

算法设计与分析,谭守标安徽大学电子学院2007.9,第九章红黑树,红黑树的概念和性质红黑树的旋转操作（过程及分析）红黑树的插入操作（过程及分析）红黑树的删除操作（过程及分析）程序演示及说明,二叉查找树的概念和性质,二叉查找树：（1）一个结点x的域：key，left，right和p。（2）二叉查找树的性质：设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点，则keyykeyx；如果y是x的右子树中的一个结点，则keyykeyx。,中序遍历算法,因为某子树根的关键字在被印出时是介于其左子树中的关键字和其右子树中的关键字之间，所以称为中序遍历算法.INORDER-TREE-WALK(x)1ifxNIL2thenINORDER-TREE-WALK(leftx)3printkeyx4INORDER-TREE-WALK(rightx),中序遍历算法,见如下的二叉查找树:将根节点指针设为上面程序的参数,则最终的输出结果为有序排列的一组数:235578,二叉查找树的查找算法,查找关键字为k的节点：根据二叉查找树的性质，从根节点开始查找，对碰到的每个节点x，比较k和keyx，若k=keyx，返回x；若kkeyx，继续查找x的左子树；否则继续查找x的右子树.TREE-SEARCH(x,k)1ifx=NILork=keyx2thenreturnx3ifkkeyx4thenreturnTREE-SEARCH(leftx,k)5elsereturnTREE-SEARCH(rightx,k),二叉查找树的查找算法,最小元素：从根节点开始，沿各节点的左指针查找下去，直至遇到NIL为止.TREE-MINIMUM(x)1whileleftxNIL2doxleftx3returnx最大元素(TREE-MAXIMUM)：和上述算法对称。,二叉查找树的查找算法,给定一个二叉查找树中的节点,有时候要求出在中序遍历下的前趋或后继。节点的前趋：如果所有的关键字均不同，某节点x的前趋即具有小于keyx中的关键字中最大者的那个节点。节点的后继：某节点x的后继即具有大于keyx中的关键字中最小者的那个节点。根据二叉树的结构我们可一不用做比较就可以找到某节点的前趋或后继。下面的过程对二叉查找树中的某节点x返回其后继(如果存在的话)，或NIL(如果x有树中最大的关键字的话)。,节点的后继,TREE-SUCCESSOR(x)1ifrightxNIL2thenreturnTREE-MINIMUM(rightx)3ypx4whileyNILandx=righty5doxy6ypy7returny,节点的后继,TREE-SUCCESSOR的代码中包含两种情况.如果节点x的右子树非空,则x的后继即是右子树中的最左点,在第2行中通过调用TREE-MINIMUM(rightx)可以找到这个节点.另一方面,如果节点x的右子树为空且x有后继y.则y是x的最低的一个祖先节点,且y的左儿子也是x的祖先.节点的前趋(TREE-PREDECESSOR)：与上述方式对称,二叉查找树的查找算法,时间性能分析：时间性能?如何改进？,二叉查找树的插入和删除操作,除完成简单的插入或删除操作外，还需要什么操作？后面结合红黑树操作一起介绍。,一、红黑树的概念和性质,红黑树：一种“平衡的”二叉查找树。一个结点的域增加一位存储结点的color，具体可以是RED或BLACK。(1)红黑树的性质：每个结点或是红的，或是黑的；每个叶结点（NIL）是黑的；如果一个结点是红的，则它的两个子女都是黑的；从某一结点到达其子孙叶结点的每一条简单路径上包含相同个数的黑结点。,(2)黑高度：用bh(x)表示。从某一结点x出发（不包括该结点）到达一个叶结点的任意一条路径上的黑结点的个数称为该结点的黑高度。红黑树的黑高度定义为其根结点的黑高度。,(3)一个引理：一个含有n个内结点的红黑树的高度至多为2log2（n+1）。证明：先证明以结点x为根的子树中至少包含2bh（x）-1个内结点。用假设归纳法证明。当x的高度为0时，则x必为一个叶结点（NIL），bh(x)=0，内结点个数为2bh(x)-1=20-1=0，假设成立；当x的高度为正值时，x是一个内结点且有两个子女(?)。每个子女根据自身颜色是红或黑有黑高度bh(x)或bh(x)-1。根据假设，每个子女至少含内结点数为2bh(x)-1-1。则以x为根结点的子树至少含内结点为（2bh（x）-1-1）+（2bh（x）-1-1）+1=2bh（x）-1。假设成立，得证。再根据性质可知，高度为h的红黑树的黑高度至少为h/2，故有n2h/2-1，得h2log2（n+1）。引理证毕。,二、红黑树的旋转操作,对红黑树进行插入和删除操作可能会影响红黑树的性质，为保证改变后的红黑树性质不变，需要引进旋转操作（是一种能保持二叉查找树性质的局部操作）。旋转分为左旋和右旋。1.左旋的过程：将结点x左旋时，假设其右子结点y是非NIL的，旋转以x到y之间的链为“支轴”进行，使y成为该子树的根，x成为y的左子结点，且y的左子树成为x的右子树。右旋的过程与此相反。,具体操作时需要根据情况调整节点颜色。,2.伪代码LEFT-ROTATE分析：假设rightxNIL。,三、红黑树的插入操作,1二叉查找树的插入操作说明：从根节点开始沿树下降，寻找把z插入树中的适当位置。,2.红黑树的插入操作：令红黑树的根结点为黑的（后续循环处理中避免空指针异常），插入的结点x为红色。在调用TREE-INSERT(T,x)将x插入T后只可能违反红黑树的性质，而不会违反其他三条性质。若px也为红色，采用重新着色或左右旋转操作进行恢复。设y指向x的叔父结点（父节点的兄弟节点）。插入x后的红黑树的性质恢复过程分三种情况分析：情况1：px和y同为红色。则使px和y着为黑色，ppx着为红色。再向上检查ppx的父结点和叔父结点，若两者还同为红色，进行迭代；若ppx的父结点为红色，叔父结点为黑色，则转入情况2或情况3；,情况2：px为红色，y为黑色，但x是px的右子结点，对x和px进行一次左旋，得到情况3；情况3：px为红色，y为黑色，但x是px的左子结点，对px和其父结点进行一次右旋，则红黑树性质恢复，处理完毕。,3.伪代码RB-INSERT(T,x)：,是否存在问题？,4.运行时间：调用TREE-INSERT(T,x)要用O(lgn)的时间，情况1的迭代循环可能被执行的总次数为O(lgn)，故总时间为O(lgn)。但因为红黑树是红黑相间的，故该循环的次数不会太多。5.程序演示及说明,四、红-黑树中元素的删除操作,1、二叉查找树中元素的删除说明：将给定节点z从二叉查找树删除的过程以指向z的指针为参数,考虑三种情况.如果z没有子女,则修改其父节点pz,使NIL为其子女;如果节点z只有一个子女,则可通过在其子节点与其父节点间建立一条链来删除z;如果节点z有两个子女,先删除z的后继y(?)，再用y的内容代替z的内容.此过程可用TREE-DELETE(T,Z)实现.,二叉查找树中元素的删除,TREE-DELETE(T,Z)1ifleftz=NILorrightz=NIL2thenyz3elseyTREE-SUCCESSOR(z)4ifleftyNIL5thenxlefty6elsexrighty7ifxNIL8thenpxpy9ifpy=NIL10thenrootTx11elseify=leftpy12thenleftpyx13elserightpyx14ifyz15thenkeyzkeyy16/如果y有其它域,也要对其它域进行复制17ruturny,二叉查找树中元素的删除,在第1-3行中,算法确定要删除的节点y.该节点y或者是输入节点z(如果z至多只有一个子女),或者是z的后继(如果z有两个子女).然后,在第4-6行中x被置为y的非NIL子女,或者当y无子女时被置为NIL.第7-13行中,通过修改py和x中的指针将y删除.同时考虑到边界条件,即x=NIL或y为根节点时对y的删除.第14-16行中如果z的后继就是要被删除的节点,则将y中的内容复制到z中从而覆盖了z中先前的内容.对高度为h的树,该过程的运行时间为O(h).,二叉查找树中元素的删除,2、红-黑树中元素的删除RB-DELETE(T,x)1ifleftz=nil(T)orrightz=nilT2thenyz3elseyTREE-SUCCESSOR(z)4ifleftynilT5thenxlefty6elsexrighty7pxpy8ifpy=nilT9thenrootTx10elseify=leftpy11thenleftpyx12elserightpyx,哨兵,红-黑树中元素的删除,13ifyz14thenkeyzkeyy15/如果还有其它域,也加以复制16ifcolory=BLACK17thenRB-DELETE-FIXUP(T,x)18returny如果被删除的节点y是黑色的则调用RB-DELETE-FIXUP(T,x),如果y是红色的,则当y被删除后,红-黑性质没有改变（因为树的各节点的黑高度都没变化,也不存在在两个相邻的红色节点）。在y被删除前,如果y有个非NIL孩子,则传给RB-DELETE-FIXUP(T,x)的节点必为y唯一的孩子.如果y没有孩子则x必为哨兵nilT.,红-黑树中元素的删除,下面是通过RB-DELETE-FIXUP(T,x)来恢复红-黑树的性质:RB-DELETE-FIXUP(T,x)1whilexrootTandcolorx=BLACK2doifx=leftpx3thenwrightpx4ifcolorw=red5thencolorwBLACK6colorpxRED7LEFT-ROTATE()T,px8wrightpx9ifcolorleftw=BLACKandcolorrightw=BLACK10thencolorwRED11xpx,红-黑树中元素的删除,12elseifcolorrightw=BALCK13thencolorleftwBLACK14colorwRED15RIGHT-ROTATE(T,w)16wrightpx17colorwcolorpx18colorpxBLACK19colorrightwBLACK20LEFT-ROTATE()T,px21xrootT22else(同then子句,只是互换right和left)23colorxBLACK,红-黑树中元素的删除,在RB-DELETE中,如果被删除的节点y是黑色的,则所有原来包含y的路径在y被删除以后都少了一个黑节点.这样,性质4就被破坏了.补救的方法就是把x视作还有一层黑色,即如果我们将任意包含节点x的路径上的黑节点的个数增加1,则在这种情况下性质4就成立了.当我们将黑节点y删除时,我们将其黑色下推至其子节点.仅有的一个问题是现在的节点x可能是双重黑色了,因而破坏了性质1.(x为红色时,直接将x染成黑色即可)RB-DELETE-FIXUP过程试图恢复性质1.第1-22行中while循环的目标是将额外的黑色沿树上移直到(1)x指向一个红节点,在这种情况下我们在第23行里将该点改为黑;(2)x指向根这时可消除那个额外的黑色,(因为在x以下的子树的黑高度不受影响,而x为根即表示所有的子树都不受影响)(3)做必要的颜色修改和旋转.,上移时需要注意的问题？,红-黑树中元素的删除,While循环的四种情况(当x为黑色(即双重黑色)且不为根时,x为其父节点的左孩子(右孩子时对称),设w为其兄弟)情况1.当w为RED时,将w染成BLACK其父节点染成RED并对其父节点进行左旋转,把旋转后的x的父节点的右孩子给w.（转换为情况2、3或4）情况2.当w为黑色时且其两个子女都为黑色,则把w换成RED,把x的父节点作为新的x.（情况1过来时则循环会中止）情况3.当w为黑色时且其左孩子为RED右孩子为BLACK,则把w的左孩子染成BLACK,把w染成RED对w进行右旋转.并把x的父节点的右孩子作为新的w.（转换为情况4）情况4.当w为黑色时且其右孩子为红色,左节点可能为红或者黑色.则把x的父节点的颜色和w交换,且使w的右孩子为BLACK.以x的父节点为参数左旋，并使x为rootT（终止循环）.,红-黑树中元素的删除,红-黑树中元素的删除,