红黑树与C实现算法

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

补充：软件开发 , C语言 ,

上一个：C语言头文件、库文件的查找路径
下一个：用C语言操作MySQL数据库，进行连接、插入、修改、删除等操作