首页 > 程序开发 > 软件开发 > C语言 >

红黑树与C实现算法

2010-11-16

本文全部内容摘自互联网,作者根据需要做了修改和补充,最主要的是提供了对set的支持,并且给出完整的测试用例。 红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由Rudo

本文全部内容摘自互联网,作者根据需要做了修改和补充,最主要的是提供了对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):

/******************************************************************************
* red_black_tree.h *
* Download From: *
* http://www.cs.tau.ac.il/~efif/courses/Software1_Summer_03/code/rbtree/ *
* Last Edited by: *
* cheungmine *
* 2010-8 *
* Container class for a red-black tree: A binary tree that satisfies the *
* following properties: *
* 1. Each node has a color, which is either red or black. *
* 2. A red node cannot have a red parent. *
* 3. The number of black nodes from every path from the tree root to a leaf *
* is the same for all tree leaves (it is called the black depth of the *
* tree). *
* Due to propeties 2-3, the depth of a red-black tree containing n nodes *
* is bounded by 2*log_2(n). *
* *
* The red_black_tree_t template requires two template parmeters: *
* - The contained TYPE class represents the objects stored in the tree. *
* It has to support the copy constructor and the assignment operator *
* (operator=). *
* *
* - pfcbRBTreeCompFunc is a functor used to define the order of objects of *
* class TYPE: *
* This class has to support an operator() that recieves two objects from *
* the TYPE class and returns a negative, zero or a positive integer, *
* depending on the comparison result. &

相关文章
最新文章
热点推荐