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

第二次实验报告 红黑树1.红黑树1.1 需求分析本实验要求实现红黑树各种操作如SEARCH ， PREDECESOR ， SUCCESSOR ，MINIMUM，MAXIMUM，INSERT，DELETE 等。红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972 年由Rudolf Bayer 发明的，他称之为对称二叉B 树，它现代的名字是在Leo J. Guibas 和Robert Sedgewick 于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 不是nilT，左旋以x 与y 之间的链为“支轴”进行。它使y 成为该子树新的根，x 成为y 的左孩子，而y 的左孩子成为x 的孩子。右旋与左旋对称。左旋代码如下：void RBLeftRotate(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; else if(x-parent-left =x) x-parent-left = y; else x-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 代码如下：void RBTreeInsertFixup(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 有三种情况：Case 1)：z 的叔叔y 是红色只有在pz和y 都是红色的时候才会执行case 1。既然ppz是黑色的，可以将pz和y 都着黑色，再将ppz着红色保持性质5，然后z=ppz来重复while 循环。Case 2）：z 的叔叔y 是黑色，且z 的为pz的右孩子Case 3）：z 的叔叔y 是黑色，且z 的为pz的左孩子Case 2 与case 3 如上图。Case 2 中z 是pz的右孩子，利用左旋把case 2 转化为case 3，因为z 与pz都是红色的，左旋对结点黑高度和性质5 每影响。在case 3 下可以通过改颜色和旋转的方式到达平衡， 并且不再出现红色警戒，因为无需往上遍历。首先我们将红父变成黑色，祖父变成红色，然后对祖父进行右旋转。这样我们可以看到，整颗树的黑高- 4 -不变，并且这颗树的左右子树也达到平衡。新的树根为黑色。1.3 结果分析根据每次从文件中读的数据，调用RB_Insert()。理论上红黑树结构应为下图，由实验运行结果知，程序是正确的。/* * copyrightnciaebupt 转载请保留此标记 * 所有代码已经在linux g+ 下编译通过，直接拷贝运行即可 如有问题欢迎指正 * 红黑树（red-black tree）是许多“平衡的”查找树中的一种。 * 红黑树的性质: * 、每个结点或是红的，或是黑的。 * 、根结点是黑的。 * 、每个叶结点（NIL）是黑的。 * 、如果一个结点是红的，则它的两个儿子都是黑的。 * 、对每个结点，从该结点到其子孙的所有路径上包含相同数目的黑结点。 * 红黑树的结点比普通的二叉查找树的结点多了一个颜色属性。 */ #include #include using namespace std; /将RED,BLACK颜色值定义成枚举类型 enum RBCOLOR RED,BLACK; /定义红黑树节点的数据结构 struct RBTreeNode int key; RBCOLOR color; RBTreeNode * left; RBTreeNode * right; RBTreeNode * parent; ; /定义红黑树的数据结构 struct RBTree RBTreeNode * root; RBTreeNode * NIL; ; void RBTreeInsertFixup(RBTree * T,RBTreeNode * z); /实现红黑树的左旋操作 void RBLeftRotate(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; else if(x-parent-left =x) x-parent-left = y; else x-parent-right =y; y-left = x; x-parent = y; /实现红黑树的右旋操作 void RBRightRotate(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; else x-parent-right = y; y-right = x; x-parent = y; /红黑树插入 void RBTreeInsert(RBTree * T,RBTreeNode * z) RBTreeNode * y = T-NIL; RBTreeNode * x = T-root; while(x != T-NIL) y = x; if(z-key key) x = x-left; else x = x-right; z-parent = y; if(y = T-NIL) T-root = z; else if(z-key key) y-left = z; else y-right = z; RBTreeInsertFixup(T,z); /红黑树插入对节点重新着色 void RBTreeInsertFixup(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; /中序遍历红黑树 void InorderRBTreeWalk(RBTree * T,RBTreeNode * x) if(x != T-NIL) InorderRBTreeWalk(T,x-left); coutkey; cout colorright); void preorderRBTreeWalk(RBTree * T,RBTreeNode * x) if(x != T-NIL) coutkey; cout colorleft); preorderRBTreeWalk(T,x-right); int main(int argc, char *argv) /15,5,3,12,10,13,6,7,16,20,18,23 RBTree * T = new RBTree; T-NIL = new RBTreeNode; T-NIL-color = BLACK; T-NIL-key = 10000; T-NIL-left = NULL; T-NIL-parent = NU