王皖南红黑树算法实现和改进副本

《王皖南红黑树算法实现和改进副本》由会员分享，可在线阅读，更多相关《王皖南红黑树算法实现和改进副本（61页珍藏版）》请在金锄头文库上搜索。

1、本科生毕业设计 姓 名： 王皖南王皖南 学 号： 0809308093458458 学 院： 计算机科学计算机科学与技术学院与技术学院 专 业： 计算机科学计算机科学与技术与技术 论文题目： 红黑树的实红黑树的实现和算法改现和算法改进进 指导教师： 雷小锋雷小锋 职 称： 副教授副教授 2013 年6 月徐州 中国矿业大学毕业设计任务书 学院 计算机学院 专业年级 计算机科学技术 09 级学生姓名王皖南 任务下达日任务下达日期：期：2013 年年 1 月月 10 日日 设计（论文）日期：设计（论文）日期： 2013 年年 1 月月 18 日日至至 2013年年 5 月月 27日日 设计（论文）

2、题目：红黑树实现设计（论文）题目：红黑树实现与算法改进与算法改进 设计（论文）专题题目：设计（论文）专题题目： 设计（论文）主要内容和设计（论文）主要内容和要求：要求： （1（ 了解并掌握红黑树的概念和性质 （2（ 可以编程构造红黑树，并实现相关的查找，插入，修改，删除操作 （3（ 分析比较现有的红黑树算法，计算复杂度，尽力发掘可以改进之处 （4（ 实现改进算法的可视化演示 （5（ 总结 院长签字： 指导教师签字： 中国矿业大学毕业设计指导教师评阅书 指导教师评语（基础理论及基本技能的掌握；独立解决实际问题的能力； 研究内容的理论依据和技术方法；取得的主要成果及创新点；工作态度及工作量； 总体

3、评价及建议成绩；存在问题；是否同意答辩等）： 成 绩： 指导教师签字： 年 月 日 中国矿业大学毕业设计评阅教师评阅书 评阅教师评语（选题的意义；基础理论及基本技能的掌握；综合运用所学 知识解决实际问题的能力；工作量的大小；取得的主要成果及创新点；写作的规 范程度；总体评价及建议成绩；存在问题；是否同意答辩等）： 成 绩： 评阅教师签字： 年 月 日 中国矿业大学毕业设计答辩及综合成绩 答 辩 情 况 回 答 问 题 提 出 问 题 正 确 基本 正确 有一 般性 错误 有原 则性 错误 没有 回答 答辩委员会评语及建议成绩： 答辩委员会主任签字： 年 月 日 学院领导小组综合评定成绩： 学院

4、领导小组负责人： 年 月 日 摘 要 红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，有着良 好的最坏情况运行时间。 红黑树是 2-3-4 树的演化数据结构。它同 2-3-4 树一样遵循二叉搜索树（BST）的中 序递增性，与具有类此性质的二叉平衡树（AVL）相比，红黑树降低了平衡参数的要求。 因此，红黑树也可以看成平衡度稍逊于二叉平衡树（AVL）的数据结构。因为红黑树与 2-3-4 树 /结点颜色 black/ red KEY key; /结点的键值 中国矿业大学 2013届本科生毕业设计（论文） 第 4 页 2.2 红黑树算法基础 从 2.1 中红黑树的性质可以得出红黑树的

5、树高受到了性质 4 和性质 5 的限制，即： 每个红色节每个红色节点的子节点点的子节点必须是黑色必须是黑色节点（从叶节点回节点（从叶节点回溯到根节点溯到根节点的路径中不的路径中不允许出现连允许出现连 续的红色节续的红色节点）以及性质点）以及性质 5 5从任意节点从任意节点到叶子节点到叶子节点的任何路径的任何路径中所包含的中所包含的黑色节点个黑色节点个数必数必 须相等须相等。 2.2.1 红黑树最长路径推算 利用性质 4和性质 5 可以设定红黑树路径的极限情况即最短路径上的结点全是黑色的， 最长路径上的结点是红黑相间的。又因为红黑树的结构是具有递归性质，综上就可以推 断出：红黑树最长红黑树最长路

6、径长度路径长度Pa-Lf_ch) /如果新结点的父节点是右儿子 If(new_node-Pa-keynew_node-Pa-Pa-key) /开辟一个指向新结点父结点的指针 B Y - D K V 8 8- T 2 T M H - G 7 B H P A Y - D K V 8 8 - T 2 T M H - G 7 B H P C Y - D K V 8 8 - T 2 T M H - G 7 B H P 中国矿业大学 2013届本科生毕业设计（论文） 第 11 页 RB_node *temp=(* RB_node)malloc(sizeof(RB_node); /父结点染成黑色 Temp-

7、color=BLACK; /新插入结点的父节点连到新结点的右儿子上 new_node-Rt_ch=new_node-Pa; /新右儿子染成红色 New_node-Rt_ch-color=RED; / /把祖父结点连到新结点的左儿子上 new_node-Lf_ch=New_pa-pa; / /新的左儿子染成红色 New_node-Lf_ch-color=RED; /把新结点的曾祖父结点作为新结点的父结点 new_node-Pa=temp-Pa-Pa / /新结点作为其曾祖父的父结点 temp-Pa-Pa=new_node; /作为其父结点的父结点 temp-Pa=new_node; /释放开辟的

8、内存 free(temp); /如果父结点是左儿子 else /开辟一个指向新结点祖父结点的指针 RB_node *temp=(*RB_node)malloc(sizeof(RB_node); temp=new_node-Pa-Pa; /父结点染成黑色 new_node-Pa-color=BLACK; /祖父结点作为父结点的右儿子 new_node-Pa-Rt_ch=new_node-Pa-Pa; 中国矿业大学 2013届本科生毕业设计（论文） 第 12 页 /父结点的右儿子染成红色 new_node-Pa-Rt_ch-color=RED; /新结点的曾祖父结点作为父结点的父结点 new_no

9、de-Pa-Pa=temp-Pa; /新结点的父结点作为祖父结点的父结点 temp-Pa=new_node-Pa; /父结点的左二子染成红色 new_node-Pa-Lf_ch-color=RED; /如果新结点是右儿子，同样要分两种情况讨论，代码基本和第一种情况类似 if(new_node-Pa=new_node-Pa-Rt_ch) if(new_node-Pa-keyPa-Pa-key) /和前文对应的处理基本相同，不在赘述 else /和前文对应的处理基本相同，不在赘述 中国矿业大学 2013届本科生毕业设计（论文） 第 13 页 2.3.5 改改进进后算后算法的分析和法的分析和比比较较

10、 从中序旋转的操作可以看出，算法包含了一般情况下插入的处理方法，也就是说涵 盖了左旋和右旋的操作，只是没有调用旋转函数罢了。如果可以在上述算法中小 else里 调用左旋和右旋函数，那么插入情景三的 Situ1 和 Situ3 只用中序旋转就可以完成了。适 当的安排情景 Situ1，Situ2，情形 1 情形2 的顺序可以大大节约判断时间，并且兼容传统 算法，使得插入的调整该算法具有很高的耦合性。综上中旋转法的主要改进之处就是减 少了调整算法中的循环次数，节省了时间。 2.3.6 插入算法插入算法复复杂杂度分析度分析 从前文可以得出，插入主要分成两个大的步骤：第一，确定待插入元素的位置 第二，调

11、整 先看第一个大步骤，确定待插入元素的位置需要用到二叉搜索算法。这个算法是基于二 叉搜索树建立的。其基本思想如下： 1.比较新元素键值与根的键值大小 2.若大于根元素的键值继续和根的右儿子比较 3 若小于很元素的键值继续和根的左儿子比较 4 将 1 中的根换成将要作比较的元素，从第一步循环下去，直到有一个比较结点的左或者 右儿子为空 第 4 步中的空位置就是新元素的位置 因为二叉搜索算法是基于分治的，所以在理想情况下，他的复杂度是 O(log2N)，由 于红黑树是不标准的平衡二叉树，在最坏情况下，我们取它的最大树高2log2（N+1） +1.可见它的复杂度依然是O(log2N)。 接下来对第二

12、个步骤分析，在调整算法里主要分为3 个大情景，在第 3 个大情景里又 细分了 3 个小情景 Situ1，Situ2，Situ3。从前面的算法介绍可以得出因为其祖父结点在旋 转染色后是黑色的，Situ1和 Situ3 只需要一次就可以保证红黑树结构的完整性。 中国矿业大学 2013届本科生毕业设计（论文） 第 14 页 但 Situ3 在完成第一调整后祖父结点被染成红色，还需要把祖父结点作为新结点继续进行 调整函数的调用。从下图 2.3.8 可以看出，祖父结点的两个孩子分支都需要参与到变换中， 而且也要自下而上递归上去。因此这一情景下的算法复杂度与二叉树的高度密切相关。 因为每次向上回溯 2 层

13、，所以最坏情况下，最复杂度是log2（N+1）+1。 图 2.10 2.3.7 该该算法的算法的优优缺点缺点 从插入的整个过程看，该算法的可信度很高，它的复杂度建立在红黑树高上面，并 且复杂度不会随红黑树的规模增加成几何性的增长，可以是操作在可预估的时间内完成。 从设计算法的角度讲，我觉得它已经做到了尽善尽美了。考虑到了每一种情况，并且 每一种处理方式都非常精简了。如果再想对它做较大的改进，只能修改红黑树的基本构 成元素了。 从阅读理解代码的角度看，它的可读性难度比较大。一开始了解红黑树时，阅读这部 分的代码，很容易被各式各样的指针扰乱思维。当然这是对我这种初学者来说的。 中国矿业大学 201

14、3届本科生毕业设计（论文） 第 15 页 3 查找算法分析 3.1 基于红黑树中序遍历的定义和改进 传统的中序遍历方式是建立在递归思想上的。但是递归也有它的不足之处，递归算 法必须以 cpu高速的计算速度为前提，当递归深度较高时，递归会占据很大的空间。所以 当红黑树的规模较大时，仅仅是对红黑树的遍历就要消耗相当大的资源了，所以在此希 望了引入一种非递归的搜索算法，来克服这方面的不足。 3.2 二叉链表局部搜索思想引入 通过对红黑树的构造元素 分析可以发现，红黑树实质上就是一条二叉双链表罢了。 从二叉双链表的遍历角度看，它的任意两个结点之间都是四通八达的，可以利用迭代或 者循环设置哨兵的方法来完

15、成查找。 采用二叉双链表的遍历方法，有一点限制，就是必须从链表的头或者开始搜索，尽 管链表中的任意结点都是连通的，但如果要求对整棵树进行遍历，必须从头或者链尾进 行，很容易迷路。所以这种算法不能用来对整棵树进行大规模的查找。 基于链表的搜索思想虽然有许多不足，但逆向考虑的话，可以发现它适合局部分支 的搜索。比如查找侄子结点，叔叔结点，兄弟结点等。 比如：查找兄弟结点，定义它为 RB_node *find_Brother(RB_node *node) 函数体如下： RB_node *find_Brother(RB_node *node) If(NULL=node) Return NULL; else If(node=node-Pa-Rt_ch) return (node-Pa-Lf_ch); /如果它是右孩子就返回父结点的左孩 子 else return (node-Pa-Rt_ch); /否则返回左孩子结点 这种类似小搜搜算法，在删除和查找的调整算法中会被经常调用，可以增强代码的可读 性。 3.3 红黑树基于迭代的二叉搜索算法 中国矿业大学 2013届本科生毕业设计（论文） 第 16 页 红黑树的是在二叉搜索树的基础上发展而来的，所以在不改变红黑树结点的前提 下，二叉搜索算法同样适合红黑树。前文已经说明递归算法不适合对大课的红黑树进行 遍历，所以