红黑树是一种自平衡的二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组(C++STL中的map/set)。它是在1972年由RudolfBayer发明的，他称之为"对称二叉B树"，它现代的名字是在LeoJ.Guibas和RobertSedgewick于1978年写的一篇论文中获得的。红黑树虽然很复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目(来源:百度百科)。
算法导论对R-BTree的介绍：
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
由于红黑树也是一颗二叉查找树,因此红黑树也满足二叉查找树的一般性质(关于二叉查找树的一般性质请参考博客:)
但由于普通的二叉查找树不具备自动平衡的功能,因此普通的二叉查找树树很有可能会退化成为一条链表,若二叉树退化成了一棵具有n个结点的线性链后，则插入/删除/查找操作最坏情况运行时间就变为了O（n）。
因此就有了红黑树,他的最终查找、插入、删除的时间复杂度最坏情况下依然为O（logn）,而红黑树之所以这么牛的原因就是它在二叉查找树的基础上增加了着色和相关的性质,这就是红黑规则:
红黑规则
1.每一个节点不是红色的就是黑色的;
2.根总是黑色的;
3.如果节点是红色的,则它的子节点必须是黑色的;
4.从根到叶节点的每条路径,必须包含相同数目的黑色节点(黑高度相同);
5.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的;
根据规则4,新增节点必须为红;
根据规则3,新增节点之父节点必须为黑.
当新节点根据二叉树的规则到达插入点,却未能符合上述红黑规则时,就必须调整颜色并旋转树形;
红黑结点template <typename Type>class RedBlackNode{friend RedBlackTree<Type>;private:RedBlackNode(const Type &_element = Type(),RedBlackNode *_left = NULL,RedBlackNode *_right = NULL,int _color = RedBlackTree<Type>::BLACK): element(_element), left(_left), right(_right), color(_color) {}private://为了在红黑树尚未完成的时候进行测试//故将之作为public, 待红黑树完成之时,//就是将其改为private之时;public:Typeelement; //节点值RedBlackNode *left;RedBlackNode *right;//红黑树的颜色intcolor;};红黑树template <typename Type>class RedBlackTree{public://为结点定义别名typedef RedBlackNode<Type> Node;enum {RED, BLACK};public://此时红黑树所支持的操作尚不完善,//而且函数功能(如析构函数, insert操作)//实现的也并不理想,//但随着红黑树代码的不断演进,//这些代码会不断的完善RedBlackTree(const Type &negInf);~RedBlackTree();void insert(const Type &data);private://为了在红黑树尚未完成的时候进行测试//故将之作为public, 待红黑树完成之时,//就是将其改为private之时;public://指向红黑树的头(伪根节点)//RedBlackNode<Type> *header;Node *header;//空节点Node *nullNode;//在插入过程中需要的指针Node *current; //当前节点Node *parent; //父节点Node *grand; //祖父节点(爷爷)Node *great; //曾祖父节点(爷爷的爸爸)/* 单旋转 *///带着左孩子旋转: 向右旋转void rotateWithLeftChild(Node *& k2) const;//带着有孩子旋转: 向左旋转void rotateWithRightChild(Node *& k1) const;/* 双旋转 *///向右转void doubleRotateWithLeftChild(Node *& k3) const;//向左转void doubleRotateWithRightChild(Node *& k1) const;};
构造与析构
//构造函数template <typename Type>RedBlackTree<Type>::RedBlackTree(const Type &negInf){nullNode = new Node();header = new Node(negInf, nullNode, nullNode);}//这一版的析构函数实现并不完善,在后续的版本我们会继续完善该析构函数template <typename Type>RedBlackTree<Type>::~RedBlackTree(){delete nullNode;delete header;}
一个二叉查找树的insert
//这时的insert其实就是一个普通的//二叉查找树的insert, 完全没要照顾到//二叉树的平衡, 以及红黑规则的实现template <typename Type>void RedBlackTree<Type>::insert(const Type &data){great = grand = parent = current = header;//在此处令nullNode成为data, 以作哨兵nullNode->element = data;while (current->element != data){//让祖父成为曾祖父, 父亲成为祖父, 自己成为父亲//每个人都长了一辈great = grand;grand = parent;parent = current;current = (data < current->element) ? current->left: current->right;}//如果树中包含相同的元素if (current != nullNode)throw DuplicateItemException();current = new Node(data, nullNode, nullNode);if (data < parent->element)parent->left = current;elseparent->right = current;//在后续的版本上,需要加上自动平衡(即实现红黑规则) -> 红黑树}单旋转
注意:内侧孙子节点横向移动(注意下图结点37);
不要哭，你要努力地往前看，你要相信阳光总在风雨后，你最终会看到彩虹的。
