/*
  Qt中qRound的实现，在负数的情况下不同于一般的四舍五入。
  如果负数尾数 <=.5的情况下，则舍弃尾数。（注意，=的情况下也舍弃o）
  如果负数尾数 > 0.5的情况下，则负小数整数部分-1
**/
Q_DECL_CONSTEXPR inline int qRound(double d)
{ return d >= 0.0 ? int(d + 0.5) : int(d - double(int(d-1)) + 0.5) + int(d-1); }

/**
 * Qt中通过模板获取qptrdiff的类型
 * TODO: 知识点：我能力有限，暂时不清楚模板应用底层原理。
 * 通过模板参数直接获取相关类型
 * 似乎与工厂设计模式有些相近（只是个人理解，如有误请留言指正）
 */

template <int> struct QIntegerForSize;
template <>    struct QIntegerForSize<1> { typedef quint8  Unsigned; typedef qint8  Signed; };
template <>    struct QIntegerForSize<2> { typedef quint16 Unsigned; typedef qint16 Signed; };
template <>    struct QIntegerForSize<4> { typedef quint32 Unsigned; typedef qint32 Signed; };
template <>    struct QIntegerForSize<8> { typedef quint64 Unsigned; typedef qint64 Signed; };
template <class T> struct QIntegerForSizeof: QIntegerForSize<sizeof(T)> { };
typedef QIntegerForSizeof<void*>::Unsigned quintptr;
typedef QIntegerForSizeof<void*>::Signed qptrdiff;
typedef qptrdiff qintptr;

/* unused参数的非warnning */
#  define Q_UNUSED(x) (void)x;

/*
 * QGlobalStatic在非线程情况下为一般static实现
 * 在线程情况下使用了QAtomicPointer自动指针，然后用QGlobalStaticDeleter注册其智能指针，在QGlobalStaticDeleter析构后，自动delete掉QGlobalStatic对象。
 * TODO: 具体原因暂时不清
 */

/*
 * 因浮点数不适宜用 == 好直接比较，所以采用了浮点数精度模糊的方法
 */
Q_DECL_CONSTEXPR static inline bool qFuzzyCompare(double p1, double p2)
{  return (qAbs(p1 - p2) <= 0.000000000001 * qMin(qAbs(p1), qAbs(p2)));}

/**
 * Q_FOREACH宏末尾
 * 主要是兼顾Q_FOREACH之后的内容（用{}括起来）
 */
for (variable = *_container_.i;; __extension__ ({--_container_.brk; break;}))
{ ;}


/* 使用模板返回相关的指针，用于private class当中，避免void然后强制类型转换
 */
  template <typename T> static inline T *qGetPtrHelper(T *ptr) { return ptr; }
template <typename Wrapper> static inline typename Wrapper::pointer qGetPtrHelper(const Wrapper &p) { return p.data(); }

/*
 * Q_DECLARE_PRIVATE(Class)等宏通过类中的d_ptr和q_ptr实现private class，以实现二进制兼容
 */

/*
 * TODO: QPrivate 中的enable_if还需要了解，可借助 std::enable_if的说明
 */

一切都很简单清爽，甚至感觉超过了Python（我不会用PYTHON，但看过相关Python实现）。。。。太爽了。。。呵呵。。。

示例1：Json数据解析并在QTreeWidget中直接显示JSON解析后的树

#include "JsonTree.h"
#include <QtCore>

JsonTree::JsonTree(QTreeWidget *widget, const QJsonObject &object)
{
  treeWidget = widget;
  responseObject = object;
  parseObject(responseObject);
}

void JsonTree::parseObject(const QJsonObject &object, QTreeWidgetItem *parent)
{
  QStringList objectKeys = object.keys();
  QTreeWidgetItem *child;
  for (int i = 0; i < objectKeys.size(); i++) {

    if (parent == NULL)
      child = new QTreeWidgetItem(treeWidget);
    else
      child = new QTreeWidgetItem(parent);

    child->setText(0, objectKeys[i]);
    QJsonValue value = object[objectKeys.at(i)];
    parseJsonValue(value, 1, child);
  }
}

void JsonTree::parseJsonValue(const QJsonValue &jsonValue, int column, QTreeWidgetItem *node)
{
  QString valueStr;

  QJsonArray  array;
  switch (jsonValue.type()) {
  case QJsonValue::Bool:
    valueStr = jsonValue.toBool() ? "True" : "False";
    node->setText(column, valueStr);
    break;
  case QJsonValue::String:
    valueStr = jsonValue.toString();
    node->setText(column, valueStr);
    break;
  case QJsonValue::Double:
    valueStr = QString::number(jsonValue.toDouble());
    node->setText(column, valueStr);
    break;
  case QJsonValue::Null:
    valueStr = "NULL";
    node->setText(column, valueStr);
    break;
  case QJsonValue::Undefined:
    qDebug() << "Undefined Json Value, check your request";
    break;
  case QJsonValue::Array:
    // Array used Key(array.at(i)) ：null
    array = jsonValue.toArray();
    for (int i = 0; i < array.size(); i++) {
      parseJsonValue(array[i], 0, new QTreeWidgetItem(node));
    }
    break;
  case QJsonValue::Object:
    parseObject(jsonValue.toObject(), node);
    break;
  default:
    qDebug() << "what's the fucking in parseJsonValue default";
    break;
  }
}

示例2：当前各种WebService横行，从B2C/B2B到社交网络，普遍要用到POST方法组装参数更新当前数据，Qt提供了强大但方便可操作的QHttpMultiPart。一切都很简单爽快，没有歧义和乱七八糟的Boundary和各种\r\n让你头晕。

  QHttpMultiPart picPost;

  QHttpPart statusPart;
  statusPart.setHeader(QNetworkRequest::ContentTypeHeader, QVariant("text/plain"));
  statusPart.setHeader(QNetworkRequest::ContentDispositionHeader, QVariant("form-data; name=\"status\""));
  statusPart.setBody("测试QT5-SINA-WEIBO-API, json Formatter");

  QHttpPart imagePart;
  imagePart.setHeader(QNetworkRequest::ContentTypeHeader, QVariant("image/jpeg"));
  imagePart.setHeader(QNetworkRequest::ContentDispositionHeader,
                      QVariant("form-data; name=\"pic\"; filename=\"test.jpg\""));
  QFile *file = new QFile("/home/sd44/test.jpg");
  file->open(QIODevice::ReadOnly);
  imagePart.setBodyDevice(file);

  picPost.append(statusPart);
  picPost.append(imagePart);


  networkAccessManager->post(sinaUploadApiUrl, picPost);

1. 系统需要依次安装如下补丁：
RS505A，OSS646B,gwxlibs-1.3.1Ba,gnutools-5.0.7Kj补丁包
必须是root用户，用scoadmin software安装

2. 在以上补丁包基础上编译安装gcc3.x.x以上版本，gcc3.4.6的math.h那借助下gcc2.9.6的即可编译通过。g++无法编译成功。因此soap工具中的wsdl2h无法编译，需要借助其他平台如WIN/LINUX生成SOAP头文件。
（开发机需要，部署到客户终端的话不需要）

配置环境变量为：

export PATH=/usr/local/gcc-3.4.6/bin:/usr/gnu/bin:/usr/bin:/bin:$HOME/bin
export LD_LIBRARY_PATH=/usr/local/gcc-3.4.6/lib:/usr/gnu/lib:/usr/lib:$HOME/lib

将以上两行添加进用户目录下的.profile文件 ~/.profile或/etc/profile文件

3. Makefile为示例Makefile文件，将其放入所建项目内。

4. 确保SCO可以正常联网，可ping 163.com测试

http://sd44.is-programmer.com/user_files/sd44/File/soap.tgz

webservice SOAP开发gsoap是首选，但在Ubuntu/Chkra Linux上，soap_dom_element处理中文字符串都会出现问题，翻找了网上所有解决文档，如wchar */ UTFSTRING/MBSTRING均不能解决。
具体表现是多字节UTF-8文字，在字符串存储时，第一个文字乱码。
经DEBUG，发现， 第一个文字前多了一个BYTE，十六进制表示为0XC3，第一个文字的第一个BYTE的前4比特也有错误。
其他均正常。


后来总算找到了解决方法。。。。。升级到2.8.11或之后版本就可以了。。-_______-。。。

是stdsoap2.c中soap_peek_element函数的BUG，由官方修正。
 

转自   http://womble.decadent.org.uk/c++/template-faq.html

C++ Templates FAQ

This is not an introduction or a reference manual to templates. It deals with some of the more complex yet still common problems with templates.

Other information

Templates are an essential part of modern C++, and any good recent introduction to C++ should cover them. If you lack such an introductory text, I recommend you read either Koenig & Moo, Accelerated C++ (Addison-Wesley, ISBN 020170353X, US sellers, UK sellers) or Stroustrup, The C++ Programming Language 3rd ed. (Addison Wesley, ISBN 0201700735, US sellers, UK sellers), depending on your prior programming experience.

Some basic questions about templates are answered by Marshall Cline's C++ FAQ Lite.

For in-depth reference, see Vandevoorde & Josuttis, C++ Templates: The Complete Guide (Addison-Wesley, ISBN 0201734842, US sellers, UK sellers).

Acknowledgement

Daveed Vandevoorde kindly reviewed this FAQ for correctness.

Contents

1. Why do I get a syntax error when I use a type that's a member of a template in the definition of another template?
2. My compiler says that a member of a base class template is not defined in a derived class template. Why is it not inherited?
3. Is it possible to specialise a member function of a class template without specialising the whole template?
4. Why doesn't Visual C++ 6 accept my definition of a class template's member function outside of the class definition?
5. Why does every instance of my function template do the same thing under Visual C++ 6?
6. Why do I need to add "template" and "typename" in the bodies of template definitions?
7. What is two-phase name lookup?
8. What are dependent names?
9. What are non-dependent names?
10. Which rules do the various C++ implementations apply for name resolution in templates?
11. Is there a difference between a function template and a template function, or between a class template and a template class?
12. What does the error message "specialization of ... in different namespace" mean?
13. What does the error message "duplicate explicit instanatiation of ..." mean?

1. Q: Why do I get a syntax error when I use a type that's a member of a class template in the definition of another template?

   template<typename T>
   struct first {
       typedef T * pointer;
   };
   
   template<typename T>
   class second {
       first<T>::pointer p; // syntax error
   };

   A: In a template, the name of a member of another class that depends on its template parameter(s) (first<T>::pointer in this example, dependent on the T parameter) is a dependent name that is not looked-up immediately. To tell the compiler that it is meant to refer to a type and not some other sort of member, you must add the keyword typename before it.

2. Q: My compiler says that a member of a base class template is not defined in a derived class template. Why is it not inherited?

   template<typename T>
   class base {
   public:
       void base_func();
   };
   
   template<typename T>
   class derived : public base<T> {
   public:
       void derived_func()
       {
           base_func(); // error: base_func not defined
       }
   };

   A: It is inherited. However, the standard says that unqualified names in a template are generally non-dependent and must be looked up when the template is defined. Since the definition of a dependent base class is not known at that time (there may be specialisations of the base class template that have not yet been seen), unqualified names are never resolved to members of the dependent base class. Where names in the template are supposed to refer to base class members or to indirect base classes, they can either be made dependent by qualifying them or brought into the template's scope with a using-declaration. In the example, this could be achieved by replacing the call to base_func() with this->base_func() or base<T>::base_func(), or by adding the declaration using base<T>::base_func;.

3. Q: Is it possible to specialise a member function of a class template without specialising the whole template?

   A: According to the standard, you can declare a full specialisation of a member function of a class template like this:

   template<typename T>
   class my_class {
   public:
       bool func();
       // other functions
   };
   
   template<>
   bool my_class<int>::func();

   Unfortunately not all compilers support this.

4. Q: Why doesn't Visual C++ 6 accept my definition of a member function template outside of the class definition?

   class my_class {
   public:
       template<typename T> void func();
   };
   
   template<typename T>
   void my_class::func()
   {
       // implementation
   }

   A: This is a limitation of Visual C++ 6 which was fixed in version 7.

5. Q: Why does every instance of my function template do the same thing under Visual C++ 6?

   template<typename T>
   std::size_t my_sizeof()
   {
       return sizeof(T);
   }

   A: This is a bug in Visual C++ 6 which was fixed in version 7. It distinguishes function template instances only by their function parameter types, not by their template arguments, so unless all template parameters are used in the declaration of the function parameter types it is possible for some instances of the template to be discarded and other instances used instead. As a workaround, you can use the template parameters to define optional function parameters that are never used:

   template<typename T>
   std::size_t my_sizeof(T * = 0)
   {
       return sizeof(T);
   }

6. Q: Why do I need to add "template" and "typename" in the bodies of template definitions?

   A: The meaning of a name used in a template definition may depend upon the template parameters, in which case it cannot automatically be determined when the template is defined. Early implementations of templates postponed resolution of all names used in a template to the time of instantiation, but this was found to be error-prone. It made it impossible to parse template definitions completely because many C++ syntax rules depend on distinguishing between names that refer to objects or functions, names that refer to types, and names that refer to templates.

   Later implementations parse templates as soon as they are defined. They require the programmer to specify which dependent names refer to types or templates, so that they can parse the templates without ambiguity. Where a dependent name is intended to refer to a type, it must generally be prefixed by the keyword typename. (This is not necessary when it is used in the list of base classes of a class template, since only type names can be used there.) Where a dependent qualified name or a prefix of such a name is intended to refer to a template, the last component of it must be prefixed by the keyword template. Note that some implementations may consider names to be dependent where the standard says they are non-dependent, and may therefore require additional uses of typename and template.

   template<typename Alloc>
   class container_helper
   {
       typedef Alloc::value_type value_type;
           // ill-formed: Alloc::value_type is assumed to be an object or function
       typedef typename Alloc::value_type value_type;
           // OK: Alloc::pointer is properly disambiguated
       typedef Alloc::typename value_type value_type;
           // ill-formed: "typename" must precede the whole qualified name
       typedef std::pair<value_type, value_type> element_type;
           // OK: value_type is resolved in the immediate scope
       typedef typename Alloc::rebind<element_type>::other element_allocator;
           // ill-formed: Alloc::rebind is assumed to be an object or function
       typedef typename template Alloc::rebind<element_type>::other element_allocator;
           // ill-formed: "template" must precede the last component of the
           // template name
       typedef typename Alloc::template rebind<element_type>::other element_allocator;
           // OK: rebind is properly disambiguated
   };
   
   template<typename T, typename Alloc = std::allocator<T> >
   class my_container : private container_helper<Alloc>::element_allocator
           // OK: container_helper<Alloc>::element_allocator cannot be resolved
           // but base names are assumed to be type names
   {
   };

7. Q: What is two-phase name lookup?

   A: This is the process specified by the standard for looking up names in templates. It is called "two-phase name lookup" because it divides names used in a template into two categories (dependent and non-dependent) that are resolved at different times. It was introduced into the draft standard some time in 1993 or 1994 but unfortunately has not been implemented by many vendors until quite recently. It makes name resolution more reliable, but is incompatible with a lot of older template code.

   The rules specifying exactly which names are considered dependent and which non-dependent are mostly intuitive, but with some corner cases. They can be found in section 14.6 of the standard.

8. Q: What are dependent names?

   A: Dependent names are names whose definitions are considered to depend upon the template parameters and for which there is no declaration within the template definition. They are resolved only when the template is instantiated. Those that are intended to refer to types or templates may require disambiguation.

   If the resolution of a dependent function name uses argument-dependent lookup, declarations in the arguments' namespaces that are visible at the point of instantiation will be considered as well as declarations visible at the point of definition. (The former is normally a superset of the latter, but may not be.)

9. Q: What are non-dependent names?

   A: Non-dependent names are those names that are considered not to depend upon the template parameters, plus the name of the template itself and names declared within it (members, friends and local variables). They are resolved when the template is defined, in the normal way, and do not require disambiguation.

10. Q: Which rules do the various C++ implementations apply for name resolution in templates?

    A: I have divided implementations into three categories: CFront, those that resolve all names at the point of instantiation, like CFront did; intermediate, those that parse templates more fully, resolving some names at the point of definition and requiring disambiguation of others; and standard, those that use the standard rules. Note that there is a lot of variation among the "intermediate" implementations.

    Implementation	Versions and options	Name lookup rules
    Comeau C++	4.x, CFront mode	CFront
    	4.x, relaxed mode; 4.0-4.2.43, strict mode	intermediate
    	4.2.44-4.3.3, strict mode	standard
    GNU C++ (g++)	2.8-3.3	intermediate
    	3.4-4.1	standard
    Metrowerks CodeWarrior	8-9, default	intermediate (?)
    	8-9, -iso-templates	standard
    Microsoft Visual C++	6.0	CFront
    	7.0-8.0 (VS.NET 2002-2005)	intermediate

    (This table is acknowledged to be incomplete and possibly incorrect in some details. Let me know if you have more information.)

11. Q: Is there a difference between a function template and a template function, or between a class template and a template class?

    A: The term "function template" refers to a kind of template. The term "template function" is sometimes used to mean the same thing, and sometimes to mean a function instantiated from a function template. This ambiguity is best avoided by using "function template" for the former and something like "function template instance" or "instance of a function template" for the latter. Note that a function template is not a function. The same distinction applies to "class template" versus "template class".

    Note that the 1998 C++ standard used the terms "template class" and "template function" in some places, but this was corrected in the 2003 version.

12. Q: What does the error message "specialization of ... in different namespace" mean?

    A: This means that the code appears to be defining a template specialisation, but it names a template that was defined in a different namespace. This is not valid, though some older versions of g++ accept it. Every declaration for a template must be placed in the same namespace, just like repeated declarations of any other named entity.

13. Q: What does the error message "duplicate explicit instantiation of ..." mean?

    A: An explicit instantiation of a function or class template is a definition of a function or class. It is an error to define either of those more than once in a translation unit, whether or not they are instantiated from a template. It is also an error to define a function more than once in an entire program unless it is defined as inline.

Last modified: Mon Dec 13 13:34:12 GMT 2010

只列出与doxygen -g DoxyFile不一样的地方

EXTRACT_ALL            = YES
EXTRACT_PRIVATE        = YES
EXTRACT_STATIC         = YES
RECURSIVE              = YES
GENERATE_LATEX         = NO

# If you set the HAVE_DOT tag to YES then doxygen will assume the dot tool is
# available from the path. This tool is part of Graphviz, a graph visualization
# toolkit from AT&T and Lucent Bell Labs. The other options in this section
# have no effect if this option is set to NO (the default)
HAVE_DOT               = YES

# If the UML_LOOK tag is set to YES doxygen will generate inheritance and
# collaboration diagrams in a style similar to the OMG's Unified Modeling
# Language.
UML_LOOK               = YES

# If the CALL_GRAPH and HAVE_DOT options are set to YES then
# doxygen will generate a call dependency graph for every global function
# or class method. Note that enabling this option will significantly increase
# the time of a run. So in most cases it will be better to enable call graphs
# for selected functions only using the \callgraph command.
CALL_GRAPH             = YES

# If the CALLER_GRAPH and HAVE_DOT tags are set to YES then
# doxygen will generate a caller dependency graph for every global function
# or class method. Note that enabling this option will significantly increase
# the time of a run. So in most cases it will be better to enable caller
# graphs for selected functions only using the \callergraph command.
CALLER_GRAPH           = YES

 *
 *    Description:  算法导论 第14章 动态顺序统计树练习题解答（伪代码）
 *
 *        Version:  1.0
 *        Created:  2012年11月19日 22时59分16秒
 *         Author:  sd44
 *   Organization:  
 *
 * =====================================================================================
 */

// 14.1-3 OS-SELECT的非递归

OS-SELECT(ptr x, int i) {
  if (i > x->size)
    return NULL;
  int r;
  ptr tmp = x;
  while (1) {
    r = tmp->left->size + 1;
    if (i < r) {
      tmp = tmp->left;
    } else if (i > r) {
      i = i - r;
      tmp = tmp->right;
    }
    else
      return r;
  }
}

// 14.1-4 OS-KEY-RANK(T, k) 较为简单，稍微修改树的find(元素）操作即可，
// 题目要求为递归形式，我实现的是非递归形式。
// 解答：
//
 r为动态集合中k的秩。。

 r初始化为0.
 如果k比当前节点的元素值大，则向右子节点移动，并记录当前节点左子结点的size且
 +1。r += currentNode->left->size + 1;
 如果k比当前节点的元素值小，则向左子结点移动，不对r进行加减操作。
 如果k等于当前节点的元素时，r += currentNode->left->size + 1;


//14.1-5 如何在O(lg N)的时间内，确定x在树的线性序中第i个后继。
//解答：
//
首先，find找到x在顺序统计树中的节点node。
如果node右节点的size大于i，则进入右结点，node = node->right,递归找第i个后继

如果node右结点的size小于i，则i = i - node->right->size，此时分两种情况：
1, 如果node为其父的右结点，则上移，node = node->parent

2, 如果node为其父的左节点，则上移，node = node->parent，i = i - 1。如果i == 1,返回此时的node(为原来node的parent）。
 否则递归找第i个后继

struct treap {
   type element;
   int priority ;

}

treap array[n]; //由用户构建一个带有元素与互异优先级的数组。

for (int i = 0; i < n; i++) {
   treePtr = treapTreeInsert(array[i].elemnt)  //执行普通的二叉树插入,保存插入后的节点
   while (treePtr != treepHeader && treePtr->priority < treePtr->parent->priority) {
     // treePtr不为树根，且优先级比其父节点小。
      if (treePtr = treePtr->parent->left)
        rightRorate(treePtr->parent);
      else
        leftRorate(treePtr->parent);

未经验证，有过有错，请指正评论或给我发EMAIL

代码结构参照了Mark Allen Weiss的《数据结构与算法分析 C++语言描述》中的模板结构。

代码根据《算法导论》中的伪代码而来。

在gtalk群与FXY兄说起红黑树，他介绍了一个非常牛B的算法网址--结构之法：

http://blog.csdn.net/v_july_v/article/details/6543438

http://blog.csdn.net/v_JULY_v/article/details/6284050

根据以上网址的图解，验证并DEBUG了自己的代码（早期代码有错误的地方）

DeleteFixup和InsertFixup中的颜色修改，维持红黑树性质的代码不是很清晰。。。。

/*
 * =====================================================================================
 *
 *       Filename:  redblacktree.h
 *
 *    Description:  红黑树的实现：
 *    红黑树确保没有一条路径会比其他路径长出两倍，接近平衡。
 *
 *    红黑树的5个基本性质：
 *    1,每个节点为红或黑
 *    2,根节点为黑
 *    3,每个叶结点(nullNode)为黑
 *    4,如果一个节点是红的，那他的两个儿子都是黑的
 *    5,对每个节点，从该结点到其子孙节点的所有路径上包含相同数目的黑节点
 *
 *        Version:  1.0
 *        Created:  2012年11月16日 17时47分03秒
 *         Author:  sd44 (sd44sd44@yeah.net), 
 *
 * =====================================================================================
 */

#ifndef  redblacktree_INC
#define  redblacktree_INC

#include <iostream>

template <typename Comparable>
class RedBlackTree
{
  // 调用以下返回RedBlackNode *类型的函数时，注意要检查值是不是nullNode，再进行操作。
 public:
  enum TreeColor {RED, BLACK};
  struct RedBlackNode {
    Comparable element;
    RedBlackNode *parent;
    RedBlackNode *left;
    RedBlackNode *right;
    TreeColor color;
    RedBlackNode( const Comparable & theElement = Comparable( ), RedBlackNode *par = NULL,
                  RedBlackNode *lt = NULL, RedBlackNode *rt = NULL,
                  TreeColor defaultColor = RED )
      : element( theElement ), parent(par), left( lt ), right( rt ), color(defaultColor)
    { }
  };

  // 显示构造函数，传入一个可以< >比较的元素
  explicit RedBlackTree() {
    nullNode = new RedBlackNode;
    // nullNode的初始化未必有必要吧？
    nullNode->parent = nullNode->left = nullNode->right = nullNode;
    nullNode->color = BLACK;
    header = nullNode;
  }

  ~RedBlackTree() {
    makeEmpty();
    delete nullNode;
  }

  const Comparable &findMin() {
    return findMinPos(header)->element;
  }
  const Comparable &findMax() {
    return findMaxPos(header)->element;
  }

  RedBlackNode *treeHeader() { return header; }
  RedBlackNode *treeNullNode() { return nullNode; }

  RedBlackNode *find(RedBlackNode *pos, const Comparable &element) const;
  RedBlackNode *findSuccessor(RedBlackNode *pos);
  bool isEmpty() const;
  void printTree() const { printTree(header); }
  void printTree(RedBlackNode *pos) const;
  void makeEmpty();
  void rbInsert(const Comparable &x);
  void rbDelete(const Comparable &x);
  RedBlackNode *rbDelete(RedBlackNode *node);

  void leftChildDeleteFixup(RedBlackTree::RedBlackNode * &node);
  void rightChildDeleteFixup(RedBlackTree::RedBlackNode * &node);
private:

  RedBlackNode *findMinPos(RedBlackNode *pos) const;
  RedBlackNode *findMaxPos(RedBlackNode *pos) const;
  void rbInsertFixup(RedBlackNode *node);
  void rbDeleteFixup(RedBlackNode *node);
  void leftRotate(RedBlackNode *x);
  void rightRotate(RedBlackNode *x);
  void emptySubTree(RedBlackNode *pos);

  RedBlackNode *header;
  RedBlackNode *nullNode;

};
#endif   /* ----- #ifndef redblacktree_INC  ----- */

#include "redblacktree.h"
#include <cstdlib>
#include <ctime>

template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode *RedBlackTree<Comparable>::findMinPos(RedBlackNode *pos) const
{
  if (pos == nullNode)
    return pos;
  while (pos->left != nullNode)
    pos = pos->left;
  return pos;
}

template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode
*RedBlackTree<Comparable>::findMaxPos(RedBlackNode *pos) const
{
  if (pos == NULL)
    return pos;
  // 此处用的是nullNode,而非NULL,也是红黑树与普通二叉树的NULL区别.
  while (pos->left != nullNode)
    pos = pos->left;
  return pos;
}

template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode
*RedBlackTree<Comparable>::find(
    RedBlackTree<Comparable>::RedBlackNode *pos, const Comparable &element) const
{
  if (pos == NULL)
    return pos;
  while (pos != nullNode && pos->element != element) {
      if (pos->element < element)
        pos = pos->right;
      else if (pos ->element > element)
        pos = pos->left;
    }
  return pos;
}

template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode
*RedBlackTree<Comparable>::findSuccessor(RedBlackTree::RedBlackNode *pos)
{
  if (pos->right != nullNode)
    return findMinPos(pos->right);
  RedBlackNode *successor = pos->parent;
  while (successor != nullNode && pos == successor->right) {
      pos = successor;
      successor = pos->parent;
    }
  return successor;
}

template <typename Comparable>
bool RedBlackTree<Comparable>::isEmpty() const
{
  return treeHeader() == nullNode;
}

template <typename Comparable>
void RedBlackTree<Comparable>::printTree(RedBlackNode *pos) const
{
  if (pos == NULL || pos == nullNode)
    return;
  if (pos->left != nullNode)
    printTree(pos->left);
  //WARNING: 此处cout只适用于可以打印的元素,请参照自己的数据结构实现
  std::cout << pos->element;
  if (pos->color == BLACK)
    std::cout << ":BLACK";
  else
    std::cout << ":RED";
  std::cout << "\t";
  if (pos->right != nullNode)
    printTree(pos->right);
}

template <typename Comparable>
void RedBlackTree<Comparable>::makeEmpty()
{
  emptySubTree(header);
  header = nullNode;
}

template <typename Comparable>
void RedBlackTree<Comparable>::emptySubTree(RedBlackNode *pos) {
  if (pos == nullNode)
    return;
  emptySubTree(pos->left);
  emptySubTree(pos->right);
  delete pos;
}

template <typename Comparable>
void RedBlackTree<Comparable>::rbInsert(const Comparable &x)
{
  RedBlackNode *preFindPos = nullNode;
  RedBlackNode *findPos = header;

  while (findPos != nullNode) {
      preFindPos = findPos;
      if (findPos->element > x)
        findPos = findPos->left;
      else
        findPos = findPos->right;
    }

  // 新节点元素为x，默认为红色，父节点为preFindPos，其他为nullNode。
  RedBlackNode *newNode = new RedBlackNode(x, preFindPos, nullNode, nullNode, RED);
  newNode->element = x;
  newNode->parent = preFindPos;
  if (preFindPos == nullNode)
    header = newNode;
  else if (x < preFindPos->element)
    preFindPos->left = newNode;
  else
    preFindPos->right = newNode;

  rbInsertFixup(newNode);
}

template <typename Comparable>
void RedBlackTree<Comparable>::rbInsertFixup(RedBlackTree::RedBlackNode *node)
{
  RedBlackNode *uncle;
  while (node->parent->color == RED) {
      //以下六种情况前提均是，父节点为红，爷结点为黑

      // 如果新插入结点node，执行以下操作：
      // 因为根节点为黑色，根节点的子节点不执行此条语句，所以node的爷爷结点肯定不是nullNode。
      // 访问不会越界。
      if (node->parent == node->parent->parent->left) {
          uncle = node->parent->parent->right;
          if (uncle->color == RED) { // 第一种情况：node与其父结点，叔父结点均为RED
              // 此时违反性质4：红节点的两个子节点均为黑，于是：
              // 将 父、叔结点改为黑，
              // 爷爷结点改为红，以维持性质五：黑高度相同。
              node->parent->color = BLACK;
              uncle->color = BLACK;
              node->parent->parent->color = RED;
              // node上移两层，迭代考察前爷爷结点为红是否违反性质4
              node = node->parent->parent;
            } else  {  // 叔父结点为黑色，父节点为红的情况。
              if (node == node->parent->right) {
                  //第二种情况：node父节点为左节点，node为右结点
                  node = node->parent;
                  // 左旋，将情况改为第三种情况
                  leftRotate(node);
                }
              // 第三种情况：node父节点为左节点，node为左节点。
              node->parent->color = BLACK; //uncle为黑，node为左红节点时的情况
              node->parent->parent->color = RED;
              rightRotate(node->parent->parent);
            }
        } else {
          //else 语句执行 node的父节点为右节点时的情况。
          uncle = node->parent->parent->left;
          if (uncle->color == RED) { // 第四种情况：父节点为右结点，node与其父，叔父结点均为RED
              // 此时违反性质4：红节点的两个子节点均为黑，于是：
              // 将 父、叔结点改为黑，
              // 爷爷结点改为红，以维持性质五：黑高度相同。
              node->parent->color = BLACK;
              uncle->color = BLACK;
              node->parent->parent->color = RED;
              // node上移两层，迭代考察前爷爷结点为红是否违反性质4
              node = node->parent->parent;
            } else  {  // 父节点为红，叔结点为黑色的情况。
              if (node == node->parent->left) {
                  // 第五种情况 父节点为右结点，node为左节点，叔结点为黑。
                  node = node->parent;
                  // 右旋，将情况改为
                  rightRotate(node);
                }
              // 第六种情况 父节点为右结点，node为右节点，叔结点为黑。
              node->parent->color = BLACK; //uncle为黑，node为左红节点时的情况
              node->parent->parent->color = RED;
              leftRotate(node->parent->parent);
            }
        }
    }
  header->color = BLACK;
}

template <typename Comparable>
void RedBlackTree<Comparable>::rbDelete(const Comparable &x)
{
  RedBlackNode *ptr = find(header, x);
  if (ptr != nullNode){
    RedBlackNode *delNode = rbDelete(ptr);
    if (delNode != nullNode)
      delete delNode;
  }
}

template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode *
RedBlackTree<Comparable>::rbDelete(RedBlackTree::RedBlackNode *node)
{
  RedBlackNode *delNode;
  if (node->left == nullNode || node->right == nullNode)
    delNode = node;
  else
    delNode = findSuccessor(node);

  RedBlackNode *delNodeChild;
  // 以下if...else...语句要结合上边来看
  // 如果node左右子女有一个为nullNode，则下面语句找到要提升的delNodeChild。
  // 如果某节点有两个子女，则其后继没有左子女。此时如果delNode = findSuccessor的话，
  // delNode->left一定等于nullNode，肯定会执行delNodeChild = delNode->right。

  if (delNode->left != nullNode)
    delNodeChild = delNode->left;
  else
    delNodeChild = delNode->right;

  delNodeChild->parent = delNode->parent;
  if (delNode->parent == nullNode)
    header = delNodeChild;
  else if (delNode == delNode->parent->left)
    delNode->parent->left = delNodeChild;
  else
    delNode->parent->right = delNodeChild;

  if (delNode != node)
    node->element = delNode->element;

  // 如果delNode->color为红的话，则红黑性质得以保持。
  // 因为此时delNode肯定不为根，根节点仍为黑
  // delNode的父节点肯定为黑，被提升的delNodeChild不会与之违反性质：红节点的子节点不能有红
  // 黑高度没有变化

  if (delNode->color == BLACK)
    rbDeleteFixup(delNodeChild);

  // WARNNING:此处没有delete delNode，用户需要接收此函数返回值然后delete
  // 或者在此处delete，且将函数返回类型设置为void。
  return delNode;
}

template <typename Comparable>
void RedBlackTree<Comparable>::rbDeleteFixup(RedBlackTree::RedBlackNode *node)
{
  // 此时node->color因为父亲黑节点的删除，将其视为具有双重颜色特性，为黑黑或者红黑，要调整
  while (node != header && node->color == BLACK) {
      // while循环处理node->color为黑且不为header的情况,此时node为黑黑的双重黑特性。
      if (node == node->parent->left)
        leftChildDeleteFixup(node);
      else
        rightChildDeleteFixup(node);
    }

  // 如果node->color为红或者为header的话，此时只需简单的将其设置为BLACK即可，见此:
  node->color =BLACK;
}

template <typename Comparable>
void RedBlackTree<Comparable>::leftChildDeleteFixup(RedBlackTree::RedBlackNode * &node)
{
  //node为双重黑特性。
  RedBlackNode *rightNode = node->parent->right;
  // case 1: rightNode为红，两个子节点为黑,将其转换为以下case
  if (rightNode->color == RED) {
      rightNode->color = BLACK;
      node->parent->color = RED;
      leftRotate(node->parent);
      // node的右子节点为旋转之前rightNode的左黑孩子，继续进入下面的case以维持红黑树性质
      rightNode = node->parent->right;
    }

  // case 2: rightNode与其两个子节点均为黑。
  if (rightNode->left->color == BLACK && rightNode->right->color == BLACK) {
      rightNode->color = RED;
      //简单将rightNode改为黑即可维持黑高度特性，node的双重特性取消，为单色。
      // 此时将node设为其父，考察其父的红黑性质。
      node = node->parent;
    } else {
      // case 3:rightNode与其右孩子为黑，左孩子为红，将其旋转后进入case 4
      if (rightNode->right->color== BLACK) {
          rightNode->left->color = BLACK;
          rightNode->color = RED;
          rightRotate(rightNode);
          rightNode = node->parent->right;
        }
      // case 4:rightnode为黑，其右孩子为红

      //rightNode颜色为其父颜色，旋转后以维持原来的黑高度
      rightNode->color = node->parent->color;

      // TODO:此时意义不明。。。node->parent此时一定为红色吗？
      node->parent->color= BLACK;
      rightNode->right->color = BLACK;
      leftRotate(node->parent);
      node = header;
    }
}

template <typename Comparable>
void RedBlackTree<Comparable>::rightChildDeleteFixup(RedBlackTree::RedBlackNode *&node)
{
  //node为双重黑特性。
  RedBlackNode *leftNode = node->parent->left;
  // case 1: rightNode为红，两个子节点为黑,将其转换为以下case
  if (leftNode->color == RED) {
      leftNode->color = BLACK;
      node->parent->color = RED;
      rightRotate(node->parent);
      // node的左子节点为旋转之前leftNode的右黑孩子，继续进入下面的case以维持红黑树性质
      leftNode = node->parent->left;
    }

  // case 2: lefttNode与其两个子节点均为黑。
  if (leftNode->left->color == BLACK && leftNode->right->color == BLACK) {
      leftNode->color = RED;
      //简单将lefttNode改为黑即可维持黑高度特性，node的双重特性取消，为单色。
      // 此时将node设为其父，考察其父的红黑性质。
      node = node->parent;
    } else {
      // case 3:leftNode与其左孩子为黑，右孩子为红，将其旋转后进入case 4
      if (leftNode->left->color== BLACK) {
          leftNode->right->color = BLACK;
          leftNode->color = RED;
          leftRotate(leftNode);
          leftNode = node->parent->left;
        }
      // case 4:leftNode为黑，其左孩子为红

      //leftNode颜色为其父颜色，旋转后以维持原来的黑高度
      leftNode->color = node->parent->color;

      // TODO:此时意义不明。。。node->parent此时一定为红色吗？
      node->parent->color= BLACK;
      leftNode->left->color = BLACK;
      rightRotate(node->parent);
      node = header;
    }
}

// 当在结点X上做左旋时，我们假设他的右孩子不是nullNode，
// x可以为任意右孩子不是nullNode的结点。

//左旋时，所影响到的结点，只有x，x的右孩子，与x右孩子的左节点。
template <typename Comparable>
void RedBlackTree<Comparable>::leftRotate(RedBlackTree::RedBlackNode *x)
{
  RedBlackNode *y = x->right;
  x->right = y->left;  // 旋转中，x的右结点设为y的左结点
  if (y->left != nullNode)
    y->left->parent = x;
  y->parent= x->parent;
  if (x->parent == nullNode) {
      header = y;
    } else if (x == x->parent->left)
    x->parent->left = y;
  else
    x->parent->right = y;
  y->left = x;
  x->parent = y;
}

//左旋时，所影响到的结点，只有x，x的左孩子，与x左孩子的右节点。
template <typename Comparable>
void RedBlackTree<Comparable>::rightRotate(RedBlackTree::RedBlackNode *x)
{
  RedBlackNode *y = x->left;
  x->left = y->right;
  if (y->right != nullNode)
    y->right->parent = x;
  y->parent = x->parent;
  if (x->parent == nullNode)
    header = y;
  else if ( x == x->parent->left)
    x->parent->left = y;
  else
    x->parent->right = y;
  y->right = x;
  x->parent = y;
}

int main(int argc, char *argv[])
{
  RedBlackTree<int> tmp;
  srand(unsigned(time(NULL)));
  for (int i = 0; i < 20; i++)
    tmp.rbInsert(rand() % 10000);

  tmp.printTree();
  std::cout << std::endl;
  std::cout << std::endl;

  tmp.makeEmpty();
  tmp.rbInsert(12);
  tmp.rbInsert(1);
  tmp.rbInsert(9);
  tmp.rbInsert(2);
  tmp.rbInsert(0);
  tmp.rbInsert(11);
  tmp.rbInsert(7);
  tmp.rbInsert(19);
  tmp.rbInsert(4);
  tmp.rbInsert(15);
  tmp.rbInsert(18);
  tmp.rbInsert(5);
  tmp.rbInsert(14);
  tmp.rbInsert(13);
  tmp.rbInsert(10);
  tmp.rbInsert(16);
  tmp.rbInsert(6);
  tmp.rbInsert(3);
  tmp.rbInsert(8);
  tmp.rbInsert(17);
  tmp.printTree();

  std::cout << std::endl << std::endl;
  tmp.rbDelete(12);
  tmp.rbDelete(1);
  tmp.rbDelete(9);
  tmp.rbDelete(2);
  tmp.rbDelete(0);
  tmp.printTree();

  return 0;
}

Mark Alen Weiss:
http://users.cis.fiu.edu/~weiss/#dsaac++3
《数据结构与算法分析 C++语言描述》

提供了较好的C++样式和代码风格，用到了模板，重载和指针引用，值得学习。。

但在效率上稍差一点，另外没有parent节点。

MicroGoogle:

http://www.cnblogs.com/shuaiwhu/archive/2011/04/20/2065055.html

非递归遍历用栈版本和不用栈版本。

我这里只参照micogoogle的实现了栈版本中序递归（基本全是照抄），非递归版本暂不考虑。

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

// #include "dsexceptions.h"
#include <iostream>    // For NULL
#include <vector>
using namespace std;

// BinarySearchTree class
//
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted

template <typename Comparable>
class BinarySearchTree
{
public:
  BinarySearchTree( ) : root( NULL ) {
  }

  BinarySearchTree( const BinarySearchTree & rhs ) : root( NULL ) {
    *this = rhs;
  }

  /**
   * Destructor for the tree
   */
  ~BinarySearchTree( ) {
    makeEmpty( );
  }

  /**
   * Find the smallest item in the tree.
   * Throw UnderflowException if empty.
   */
  const Comparable & findMin( ) const {
    if ( isEmpty( ) ) {
      //      throw UnderflowException( );
      ;
    }
    return findMin( root )->element;
  }

  /**
   * Find the largest item in the tree.
   * Throw UnderflowException if empty.
   */
  const Comparable & findMax( ) const {
    if ( isEmpty( ) ) {
      //      throw UnderflowException( );
      ;
    }
    return findMax( root )->element;
  }

  /**
   * Returns true if x is found in the tree.
   */
  bool contains( const Comparable & x ) const {
    return contains( x, root );
  }

  /**
   * Test if the tree is logically empty.
   * Return true if empty, false otherwise.
   */
  bool isEmpty( ) const {
    return root == NULL;
  }

  /**
   * Print the tree contents in sorted order.
   */
  void printTree( ostream & out = cout ) const {
    if ( isEmpty( ) ) {
      out << "Empty tree" << endl;
    } else {
      printTree( root, out );
    }
  }

  /**
   * Make the tree logically empty.
   */
  void makeEmpty( ) {
    makeEmpty( root );
  }

  /**
   * Insert x into the tree; duplicates are ignored.
   */
  void insert( const Comparable & x ) {
    insert( x, root );
  }

  /**
   * Remove x from the tree. Nothing is done if x is not found.
   */
  void remove( const Comparable & x ) {
    remove( x, root );
  }

  /**
   * Deep copy.
   */
  const BinarySearchTree & operator=( const BinarySearchTree & rhs ) {
    if ( this != &rhs ) {
      makeEmpty( );
      root = clone( rhs.root );
    }
    return *this;
  }

private:
  struct BinaryNode {
    Comparable element;
    BinaryNode *left;
    BinaryNode *right;

    BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
      : element( theElement ), left( lt ), right( rt ) { }
  };

  BinaryNode *root;


  /**
   * Internal method to insert into a subtree.
   * x is the item to insert.
   * t is the node that roots the subtree.
   * Set the new root of the subtree.
   */
  void insert( const Comparable & x, BinaryNode * & t ) {
    if ( t == NULL ) {
      t = new BinaryNode( x, NULL, NULL );
    } else if ( x < t->element ) {
      insert( x, t->left );
    } else if ( t->element < x ) {
      insert( x, t->right );
    } else {
//      ;  // Duplicate; do nothing
    }
  }

  /**
   * Internal method to remove from a subtree.
   * x is the item to remove.
   * t is the node that roots the subtree.
   * Set the new root of the subtree.
   */
  void remove( const Comparable & x, BinaryNode * & t ) {
    if ( t == NULL ) {
      return;  // Item not found; do nothing
    }
    if ( x < t->element ) {
      remove( x, t->left );
    } else if ( t->element < x ) {
      remove( x, t->right );
    } else if ( t->left != NULL && t->right != NULL ) { // Two children
      t->element = findMin( t->right )->element;
      remove( t->element, t->right );
    } else {
      BinaryNode *oldNode = t;
      t = ( t->left != NULL ) ? t->left : t->right;
      delete oldNode;
    }
  }

  /**
   * Internal method to find the smallest item in a subtree t.
   * Return node containing the smallest item.
   */
  BinaryNode * findMin( BinaryNode *t ) const {
    if ( t == NULL ) {
      return NULL;
    }
    if ( t->left == NULL ) {
      return t;
    }
    return findMin( t->left );
  }

  /**
   * Internal method to find the largest item in a subtree t.
   * Return node containing the largest item.
   */
  BinaryNode * findMax( BinaryNode *t ) const {

    if ( t != NULL )
      while ( t->right != NULL ) {
        t = t->right;
      }
    return t;
  }


  /**
   * Internal method to test if an item is in a subtree.
   * x is item to search for.
   * t is the node that roots the subtree.
   */
  bool contains( const Comparable & x, BinaryNode *t ) const {
    if ( t == NULL ) {
      return false;
    } else if ( x < t->element ) {
      return contains( x, t->left );
    } else if ( t->element < x ) {
      return contains( x, t->right );
    } else {
      return true;  // Match
    }
  }
  /****** NONRECURSIVE VERSION*************************
    bool contains( const Comparable & x, BinaryNode *t ) const
    {
    while( t != NULL )
    if( x < t->element )
    t = t->left;
    else if( t->element < x )
    t = t->right;
    else
    return true;    // Match

    return false;   // No match
    }
   *****************************************************/

  /**
   * Internal method to make subtree empty.
   */
  void makeEmpty( BinaryNode * & t ) {
    if ( t != NULL ) {
      makeEmpty( t->left );
      makeEmpty( t->right );
      delete t;
    }
    t = NULL;
  }

  //
  //  void printTree( BinaryNode *t, ostream & out ) const {
  //    if ( t != NULL ) {
  //      printTree( t->left, out );
  //      out << t->element << endl;
  //      printTree( t->right, out );
  //    }
  //  }

  void printTree( BinaryNode *t, ostream &out) const {
//  将vector当作栈来实现，push_back,pop_back,back
    vector<BinaryNode *> stackList;
    while (t != NULL || !stackList.empty()) {
      while (t != NULL) {
        stackList.push_back(t);
        t = t->left;
      }
      t = stackList.back();
      stackList.pop_back();
      out << t->element << "\t";
      t = t->right;
    }
  }

    /**
     * Internal method to clone subtree.
     */
    BinaryNode * clone( BinaryNode *t ) const {
      if ( t == NUL
          return NULL;
          } else {
          return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );
          }
          }
          };

#endif