红黑树区间树实验报告资源-CSDN文库

红黑树

实验报告

需积分: 9 15 浏览量 2010-12-04 17:00:13 上传评论收藏 554KB PDF 举报

资源推荐

资源详情

资源评论

中国科学技术大学

算法第二次实验报告

1. 红黑树 ....................................................................................................................................... - 1 -

1.1 需求分析 ........................................................................................................................ - 1 -

1.2 算法设计 ........................................................................................................................ - 1 -

1.2.1 旋转 ..................................................................................................................... - 1 -

1.2.2 插入 ..................................................................................................................... - 2 -

1.2.3 删除 ..................................................................................................................... - 4 -

1.3 数据结构设计 ............................................................................................................... - 5 -

1.4 运行结果 ....................................................................................................................... - 6 -

1.5 结果分析 ....................................................................................................................... - 7 -

1.6 优化 ............................................................................................................................... - 8 -

1.7 心得体会 ....................................................................................................................... - 8 -

1.8 未来工作 ........................................................................................................................ - 8 -

2. 区间树 ..................................................................................................................................... - 8 -

2.1 需求分析 ....................................................................................................................... - 8 -

2.2 程序设计 ....................................................................................................................... - 9 -

2.3 数据结构设计 ................................................................................................................ - 9 -

2.4 运行结果 ...................................................................................................................... - 10 -

2.5 结果分析 ...................................................................................................................... - 11 -

2.6 心得体会 ..................................................................................................................... - 12 -

2.7 未来工作 ...................................................................................................................... - 12 -

- 1 -

红黑树

1.1

1.1 需求分析

需求分析

本实验要求实现红黑树各种操作如 SEARCH ， PREDECESOR ， SUCCESSOR ，

MINIMUM ， MAXIMUM ， INSERT ， DELETE 等。

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途

是实现关联数组。它是在 1972 年由 Rudolf Bayer 发明的，他称之为 " 对称二叉 B 树 " ，它现

代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于 1978 年写的一篇论文中获得的。它是

复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的 : 它可以在 O(log

n) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强

制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求 :

1. 每个结点或红或黑。

2. 根结点为黑色。

3. 每个叶结点 ( 实际上就是 NULL 指针 ) 都是黑色的。

4. 如果一个结点是红色的 , 那么它的周边 3 个节点都是黑色的。

5. 对于每个结点 , 从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一

样。

这些约束强制了红黑树的关键性质 : 从根到叶子的最长的可能路径不多于最短的可能

路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最

坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都

是高效的，而不同于普通的二叉查找树。

要知道为什么这些特性确保了这个结果，注意到属性 5 导致了路径不能有两个毗连的红

色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点

。

因为根据属性 4 所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何

其他路径的两倍长。

在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据

。

用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们

使用 "nil 叶子 " 或 " 空 (null) 叶子 " 。

1.2

算法设计

操作 SEARCH, ， PREDECESOR ， SUCCESSOR ， MINIMUM ， MAXIMUM 与二查检索

树的对应操作几乎相同。这里只介绍旋转、插入、删除。

1.2.1

1.2.1 旋转

由于插入、删除操作对树作了修改，结果可能违反红黑树的五个性质。为保持这些性质

，

就要改变树中某些结点的颜色以及指针结构。指针结构的修改通过旋转来完成。

剩余12页未读，继续阅读

评论收藏

内容反馈

changbiao1990

粉丝: 5
资源: 9

红黑树 区间树实验报告

红黑树、区间树

区间树（c++实现）

区间树的重叠区间查找算法

相邻区间合并

用C语言实现的区间操作程序

红黑树（根据书上的算法，进而实现）

中科大红黑树插入算法实验报告

红黑树与区间树算法实现

区间树上的重叠区间查找算法源代码和实验报告

R语言区间估计实验报告

R语言区间估计实验报告.rar

红黑树代码

红黑树算法的c实现

红黑树原理详解

红黑树的插入详细图解，直接拿下红黑树

Linux内核红黑树封装的通用红黑树

红黑树-动态演示生成红黑树

红黑树和AVL树的实现

红黑树C++代码实现

红黑树的插入与删除_详细整理资料

算法实现及性能比较与红黑树

红黑树算法C语言实现

红黑树算法试验完全实现（花1天时间写的算法作业）

用c实现的红黑树，经典的红黑树，

算法实验4-红黑树

红黑树-使用C++实现-简单练习

具有双向链表功能的红黑树

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

最新资源

红黑树区间树实验报告

Qt 5实现串口调试助手（源工程文件、0积分下载）