中国科技大学算法导论_第二次实验报告

第二次实验报告红黑树1.红黑树1.1需求分析本实验要求实现红黑树各种操作如SEARCH，PREDECESOR，SUCCESSOR，MINIMUM，MAXIMUM，INSERT，DELETE等。红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由RudolfBayer发明的，他称之为对称二叉B树，它现代的名字是在LeoJ.Guibas和RobertSedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的:它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:1.每个结点或红或黑。2.根结点为黑色。3.每个叶结点(实际上就是NULL指针)都是黑色的。4.如果一个结点是红色的,那么它的周边3个节点都是黑色的。5.对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样。这些约束强制了红黑树的关键性质:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。要知道为什么这些特性确保了这个结果，注意到属性5导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据属性4所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用nil叶子或空(null)叶子。1.2算法设计操作SEARCH,，PREDECESOR，SUCCESSOR，MINIMUM，MAXIMUM与二查检索树的对应操作几乎相同。这里只介绍旋转、插入、删除。1.2.1旋转由于插入、删除操作对树作了修改，结果可能违反红黑树的五个性质。为保持这些性质，就要改变树中某些结点的颜色以及指针结构。指针结构的修改通过旋转来完成。当在某个结点x上做左旋时，假设它的有孩子y不是nil[T]，左旋以x与y之间的链为“支轴”进行。它使y成为该子树新的根，x成为y的左孩子，而y的左孩子成为x的孩子。右旋与左旋对称。左旋代码如下：voidRBLeftRotate(RBTree*T,RBTreeNode*x){RBTreeNode*y=x-right;x-right=y-left;if(y-left!=T-NIL)y-left-parent=x;y-parent=x-parent;if(x-parent==T-NIL)T-root=y;elseif(x-parent-left==x)x-parent-left=y;elsex-parent-right=y;y-left=x;x-parent=y;}1.2.2插入向一颗含n个结点的红黑树插入一个结点z的操作可在O(lgn)时间完成。利用二叉查找树的Tree_Insert过程，将z插入树内，并将其着红色。为保证红黑树的性质，调用RB_INSERTT_FIXUP来对结点重新着色并旋转。RB_INSERTT_FIXUP代码如下：voidRBTreeInsertFixup(RBTree*T,RBTreeNode*z){RBTreeNode*y;if(z-parent==T-NIL)//z是根节点{z-color=BLACK;return;}if(z-parent-color==BLACK)//这种情况下是平衡的{return;}//一直循环，直到z的父节点的颜色为黑色while(z-parent-color==RED){if(z-parent==z-parent-parent-left)//当z的父节点是z祖父节点的左孩子时{y=z-parent-parent-right;//y是z的叔叔//case1:z的叔叔y的颜色为红色if(y-color==RED){z-parent-color=BLACK;y-color=BLACK;z-parent-parent-color=RED;z=z-parent-parent;}else{if(z==z-parent-right)//case2:z的叔叔y的颜色为黑色并且z是它父节点的右孩子{z=z-parent;RBLeftRotate(T,z);}//case3:z的叔叔y的颜色为黑色并且z是它父节点的左孩子z-parent-color=BLACK;z-parent-parent-color=RED;RBRightRotate(T,z-parent-parent);}}//当z的父节点是z祖父节点的右孩子时else//如果z的父节点是其祖父节点的右孩子{y=z-parent-parent-left;//y是z的叔叔节点if(y-color==RED)//case1：z的叔叔节点为红色，则z的父节点BLACK，祖父节点RED，叔叔节点BLACK均变色{z-parent-color=BLACK;y-color=BLACK;z-parent-parent-color=RED;z=z-parent-parent;}else{if(z==z-parent-left)//case2:z的叔叔y的颜色为黑色并且z是它父节点的左孩子{z=z-parent;RBRightRotate(T,z);}//case3:z的叔叔y的颜色为黑色并且z是它父节点的右孩子z-parent-color=BLACK;z-parent-parent-color=RED;RBLeftRotate(T,z-parent-parent);}}}T-root-color=BLACK;}当调用RB_INSERTT_FIXUP(T，z)时，while有三种情况：Case1)：z的叔叔y是红色只有在p[z]和y都是红色的时候才会执行case1。既然p[p[z]]是黑色的，可以将p[z]和y都着黑色，再将p[p[z]]着红色保持性质5，然后z=p[p[z]]来重复while循环。Case2）：z的叔叔y是黑色，且z的为p[z]的右孩子Case3）：z的叔叔y是黑色，且z的为p[z]的左孩子Case2与case3如上图。Case2中z是p[z]的右孩子，利用左旋把case2转化为case3，因为z与p[z]都是红色的，左旋对结点黑高度和性质5每影响。在case3下可以通过改颜色和旋转的方式到达平衡，并且不再出现红色警戒，因为无需往上遍历。首先我们将红父变成黑色，祖父变成红色，然后对祖父进行右旋转。这样我们可以看到，整颗树的黑高-4-不变，并且这颗树的左右子树也达到平衡。新的树根为黑色。1.3结果分析根据每次从文件中读的数据，调用RB_Insert()。理论上红黑树结构应为下图，由实验运行结果知，程序是正确的。/**copyright@nciaebupt转载请保留此标记*所有代码已经在linuxg++下编译通过，直接拷贝运行即可如有问题欢迎指正*红黑树（red-blacktree）是许多“平衡的”查找树中的一种。*红黑树的性质:*１、每个结点或是红的，或是黑的。*２、根结点是黑的。*３、每个叶结点（NIL）是黑的。*４、如果一个结点是红的，则它的两个儿子都是黑的。*５、对每个结点，从该结点到其子孙的所有路径上包含相同数目的黑结点。*红黑树的结点比普通的二叉查找树的结点多了一个颜色属性。*/#includeiostream#includevectorusingnamespacestd;//将RED,BLACK颜色值定义成枚举类型enumRBCOLOR{RED,BLACK};//定义红黑树节点的数据结构structRBTreeNode{intkey;RBCOLORcolor;RBTreeNode*left;RBTreeNode*right;RBTreeNode*parent;};//定义红黑树的数据结构structRBTree{RBTreeNode*root;RBTreeNode*NIL;};voidRBTreeInsertFixup(RBTree*T,RBTreeNode*z);//实现红黑树的左旋操作voidRBLeftRotate(RBTree*T,RBTreeNode*x){RBTreeNode*y=x-right;x-right=y-left;if(y-left!=T-NIL)y-left-parent=x;y-parent=x-parent;if(x-parent==T-NIL)T-root=y;elseif(x-parent-left==x)x-parent-left=y;elsex-parent-right=y;y-left=x;x-parent=y;}//实现红黑树的右旋操作voidRBRightRotate(RBTree*T,RBTreeNode*x){RBTreeNode*y=x-left;if(x-left==T-NIL)return;x-left=y-right;if(y-right!=T-NIL){y-right-parent=x;}y-parent=x-parent;if(x-parent==T-NIL)T-root=y;else{if(x-parent-left==x)x-parent-left=y;elsex-parent-right=y;}y-right=x;x-parent=y;}//红黑树插入voidRBTreeInsert(RBTree*T,RBTreeNode*z){RBTreeNode*y=T-NIL;RBTreeNode*x=T-root;while(x!=T-NIL){y=x;if(z-key=x-key)x=x-left;elsex=x-right;}z-parent=y;if(y==T-NIL)T-root=z;else{if(z-key=y-key){y-left=z;}else{y-right=z;}}RBTreeInsertFixup(T,z);}//红黑树插入对节点重新着色voidRBTreeInsertFixup(RBTree*T,RBTreeNode*z){RBTreeNode*y;if(z-parent==T-NIL)//z是根节点{z-color=BLACK;return;}if(z-parent-color==BLACK)//这种情况下是平衡的{return;}//一直循环，直到z的父节点的颜色为黑色while(z-parent-color==RED){if(z-parent==z-parent-parent-left)//当z的父节点是z祖父节点的左孩子时{y=z-parent-parent-right;//y是z的叔叔//case1:z的叔叔y的颜色为红色if(y-color==RED){z-parent-color=BLACK;y-color=BLACK;z-parent-parent-color=RED;z=z-parent-parent;}else{if(z==z-parent-right)//case2:z的叔叔y的颜色为黑色并且z是它父节点的右孩子{z=z-parent;RBLeftRotate(T,z);}//case3:z的叔叔y的颜色