红黑树与C实现算法
cheungmine
本文全部内容摘自互联网,作者根据需要做了修改和补充,最主要的是提供了对set的支持,并且给出完整的测试用例。
红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由Rudolf
Bayer发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick
于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log
n)时间内做查找,插入和删除,这里的n 是树中元素的数目。
红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。
红黑树的实现代码如下(red_black_tree.h,red_black_tree.c和测试文件rbtree_test.c):
任何人使用此代码必须遵守原作者的协议。
分享到:
相关推荐
红黑树的源代码,c语言版本。非常的详细。
红黑树C语言代码,qt工程,红黑树在linux C++:STL中应用广泛,而且很多面试时喜欢问。
这一版代码个人认为99.99%正确,本人使用些结构及算法用于实现嵌入式迅雷Server的任务管理。此代码经本人学习研究之后从C语言版BT源代码中的宏定义式代码中分离出来,并做成一个测试版。你也可以做一些微小的...
红黑树的C语言实现
红黑树(Red Black Tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉树的...
红黑树C语言代码: #include "redblack.h" #include <stdlib.h> #include "fatal.h" 头文件: #include <stdlib.h> #include "fatal.h" typedef int ElementType; #define NegInfinity (-10000) #ifndef _Red...
红黑树的发明者关于红黑树的演化过程的介绍,是最好的理解红黑树的资料。
实验1:实现红黑树的基本算法, 对n的取值分别为 12、24、36、48、60,随机生成n 个互异的正整数(K1, K2, K3, ……, Kn)作为节点的关键字,向一棵初始空的红黑树中依次插入这n 个节点,统计算法运行所需时间 ,画...
此工程主要包含红黑树的插入和删除,采用C++编写,有单独的.h和.cpp文件,方便移植
红黑树的C语言实现 算法导论的红黑树C实现
:Christmas_tree: let tree = RedBlackTree . from ( increasing , range ( 100000 ) ) ; JavaScript的红黑树库。 请参阅。 父母是 。
C#,红黑树(Red-Black Tree)的构造,插入、删除及修复、查找的算法与源代码 1 红黑树(Red-Black Tree) 如果二叉搜索树满足以下红黑属性,则它是红黑树: 每个节点不是红色就是黑色。 根是黑色的。 每片叶子(无...
AVL 红黑树 SBT-2020.12.11
关于红黑树(Red-Black Tree)英文论文,全英文写作,分析全面,到位,结合当前新技术进展总结而成。
红黑树简介-树一箩筐.ppt
红黑树(Red-Black Tree)是二叉搜索树(Binary Search Tree)的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。而红黑树在每一次插入或删除节点 之后...
红黑树 红黑树_基于C语言实现的红黑树数据结构
介绍AVL树与红黑树,按照例子一步一图,可以对照我的博客进行理解。不明白的email durant2019@sina.com