张非凡组红黑树报告张非凡组.doc

《张非凡组红黑树报告张非凡组.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、东北大学信息科学与工程学院数据结构课程设计课题报告题目红黑平衡二叉树及其应用课题组组长张非凡课题组成员田秋欧阳龚轩专业名称物联网班级1201指导教师孟凡荣2014年7月17日课程设计任务书题目：红黑平衡二叉树及其应用问题描述：一棵红黑树本身就是一棵二叉排序树。红黑树中的结点颜色是黑色或红色。从红黑树的根结点到叶子结点的路径上的黑色结点数目相同，最短的路径就是所有结点都是黑色。根据红黑树的性质，红黑树在平衡类二叉排序树中有许多应用。设计要求：设计红黑平衡二叉树实现动态查找表及其应用。（1）实现动态查找表的三种基本功能：查找、插入、删除。（2）实现红黑平衡二叉树的简单

2、应用。（3）尝试实现图形演示的可视化界面。　　　　　　　　　　　　指导教师签字：2014年1月10日目录1课题背景51.1课题来源51.2课题任务51.3课题原理51.4相关知识162需求分析162.1课题调研162.2用户需求162.3功能需求173方案设计173.1总体功能设计173.2数据结构设计183.3函数原型设计183.4主算法设计193.5界面设计214方案实现254.1开发环境与编程工具254.2程序设计关键技术254.3个人设计实现254.3.1张非凡设计实现254.3.2田秋设计实现474.3.3欧阳龚轩设计实现715测试与运行835.1个人测

3、试（按组员分小节）835.1.1张非凡测试835.1.2田秋测试835.13欧阳龚轩测试845.2组装测试875.3系统测试885.4系统运行886课题总结906.1课题性能分析906.2课题评价与与团队协作906.3个人设计小结（按组员分小节）906.3.1张非凡设计小结916.3.2田秋设计小结916.3.3欧阳龚轩设计小结927附录A课题任务分工94A-1课题程序设计分工94A-2课题报告分工951.课题背景1.1课题来源本课题有指导老师提供。1.2课题任务【问题描述】一棵红黑树本身就是一棵二叉排序树。红黑树中的结点颜色是黑色或红色。从红黑树的根结点到叶子结

4、点的路径上的黑色结点数目相同，最短的路径就是所有结点都是黑色。根据红黑树的性质，红黑树在平衡类二叉排序树中有许多应用。【设计要求】设计红黑平衡二叉树实现动态查找表及其应用。（1）实现动态查找表的三种基本功能：查找、插入、删除。（2）实现红黑平衡二叉树的简单应用。（3）尝试实现图形演示的可视化界面。1.3课题原理红黑树（RBT）的定义：它或者是一颗空树，或者是具有一下性质的二叉查找树：1.节点非红即黑。2.根节点是黑色。3.所有NULL结点称为叶子节点，且认为颜色为黑。4.所有红节点的子节点都为黑色。5.从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。看完

5、红黑树的定义是不是可晕？怎么这么多要求！！这怎么约束啊？我刚看到这5条约束，直接无语了，1-3、4还好说，第5点是怎么回事啊？怎么约束？整这么复杂的条件好干啥啊？我来简单说说呵：第3条，显然这里的叶子节点不是平常我们所说的叶子节点，如图标有NIL的为叶子节点，为什么不按常规出牌，因为按一般的叶子节点也行，但会使算法更复杂；第4条，即该树上决不允许存在两个连续的红节点；第5条，比如图中红8到1左边的叶子节点的路径包含2个黑节点，到6下的叶子节点的路径也包含2个黑节点。所有性质1-5合起来约束了该树的平衡性能--即该树上的最长路径不可能会大于2倍最短路径。为什么？因为

6、第1条该树上的节点非红即黑，由于第4条该树上不允许存在两个连续的红节点，那么对于从一个节点到其叶子节点的一条最长的路径一定是红黑交错的，那么最短路径一定是纯黑色的节点；而又第5条从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点，这么来说最长路径上的黑节点的数目和最短路径上的黑节点的数目相等！而又第2条根结点为黑、第3条叶子节点是黑，那么可知：最长路径<=2*最短路径。一颗二叉树的平衡性能越好，那么它的效率越高！显然红黑树的平衡性能比AVL的略差些，但是经过大量试验证明，实际上红黑树的效率还是很不错了，仍能达到O(logN)，这个我不知道，我现在不可能做过大

7、量试验，只是听人家这样说，O(∩_∩)O哈哈~但你至少知道他的时间复杂度一定小于2O(logN)!上边的性质看个10遍，看懂看透彻再看操作！插入操作由于性质的约束：插入点不能为黑节点，应插入红节点。因为你插入黑节点将破坏性质5，所以每次插入的点都是红结点，但是若他的父节点也为红，那岂不是破坏了性质4？对啊，所以要做一些“旋转”和一些节点的变色！另为叙述方便我们给要插入的节点标为N（红色），父节点为P，祖父节点为G，叔节点为U。下边将一一列出所有插入时遇到的情况：情形1：该树为空树，直接插入根结点的位置，违反性质1，把节点颜色有红改为黑即可。情形2：插入节点N的父节

8、点P为黑色