本文全部內容摘自互聯網，作者根據需要做了修改和補充，最主要的是提供了對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. &
