之前博客实现了AVL树，但是AVL树的频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种 折中，插入最多两次旋转，删除最多三次旋转。所以红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。 红黑树也是一种二叉平衡树，它不使用平衡因子来维护树的形状，而是使用红黑节点来决定，使得最长节点的长度不会超过最短节点的长度的两倍，让红黑树的插入和删除大大减少了树的旋转操作，虽然这么做是有代价的，AVL树的时间复杂度为O(logn),而红黑树的时间复杂度为O(nlogn),但是因为日新月异的计算机运算能力的发展，这点损失是可以接受的。
首先来看红黑树的组成规则
每个节点不是红节点就是黑节点(废话中的废话)每个红节点的两个孩子节点必须是黑节点(没有连续的红节点)根节点是黑节点对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(决定最长节点的长度不会超过最短节点的长度的两倍)每个叶子结点都是黑色的(此处的叶子结点指的是空结点不是有有效值的节点）只要我们保证上面的规则，就能决定最长节点的长度不会超过最短节点的长度的两倍，可以从下图看出。 在每条路径的黑节点个数相同的情况下
最短路径：全部为黑节点最长路径：在规则允许的情况下尽量插入红节点，最终为红黑相间。ps：为什么红黑树叫做红黑树，而不叫黑白树，蓝紫树？ 答案：因为红黑树的作者就是这么规定的:D.
上面的知识是为了用红色和黑色控制树的形状的，从上面的规则可以知道，每棵树的根节点都是黑色的，但是当我们插入一个新的节点，这个新的节点是红色还是黑色？ 假如插入的节点为黑色，一定会影响第四条规定，需要将所有路径上的节点重新调整。 假如插入的节点为红色，可能违反第二条规定，如果插入节点的父亲节点为黑色，则无影响，直接结束，否则进行旋转处理。 所以我们插入的新的的节点的颜色为红色，判断父亲节点的颜色，确定是否进行左右旋转，为了方便下面用不同的标识来显示节点。
_Proot: 根节点_root ：插入节点pnode： 插入节点的父亲grandfather： 插入节点的父亲的父亲uncle： 插入节点的父亲的兄弟节点下图是我们遇到的最简单的情况，当父节点为黑色时，插入一个红节点不会破坏原来路径的黑节点的个数，而且没有违反规则，插入后，直接退出。
也是比较简单的一种情况，将父节点和父节点的兄弟节点颜色变为黑色，祖父节点的颜色变为红色。 但是上面只是一棵树的一部分，改变完成后，还要往上进行调整。 修改为后，判断是否有两个连续的红色节点，如果没有，将_root pnode gardfather向上移动，直到根节点。
下图为我们遇到的第三种情况，也就是上图调整后的情况，pnode为红，uncle为黑。 **注意:**这种情况一定是在我们进行的第二种情况调整了红黑节点的颜色产生的，_root绝对不可能是新插入的节点，因为在插入之前这棵树已经不满足红黑树的定义了，所以_root之前是黑色，之后被调整为了红色。 遇到这种情况的步骤为
将pnode的右孩子成为grandfather的左孩子将pnode的右孩子的父亲指针指向grandfather将pnode的父亲指针指向grandfather的父节点，如果grandfather为根节点，则将pnode设为根节点。将grandfather的父亲指针指向pnode.将pnode的右孩子指向grandfather将pnode的颜色变为黑色，grandfather的颜色变为红色 下面是对应的代码，可以对照的理解 void _RotateR(Node* pnode) { Node* ppnode = pnode->_Parents; Node* Lnode = pnode->_Left; pnode->_Left = Lnode->_Right; if (Lnode->_Right) { Lnode->_Right->_Parents = pnode; } Lnode->_Right = pnode; if (ppnode == nullptr) { _Proot = Lnode; _Proot->_Parents = nullptr; } else { Lnode->_Parents = ppnode; if (ppnode->_Left == pnode) { ppnode->_Left = Lnode; } else if (ppnode->_Right == pnode) { ppnode->_Right = Lnode; } } pnode->_Parents = Lnode; }和第三种情况一样，只不过要进行两次旋转达到目的。 这种情况下先对parents为轴进行右旋，再以grandfather为轴进行左旋，最后将grandfather和_root的颜色进行改变。 即使是更复杂的树也是这种改变顺序。 以上就是修改红黑树遇到的旋转情况，这里拿右单旋和右左单旋为例，左单旋和左右单旋方向想法，思路相同。
红黑树的删除有一定的难度，这里我们就不详细介绍了，其实它跟二叉搜索树的删除很类似就是寻找一个替换节点然后删掉它的替换节点，如果有兴趣的读者可以查看算法导论的相关章节。
红黑树的验证是一个难点，并不像AVL树，红黑树不保证一定是一颗平衡二叉树，所以我们可以从下面的规则入手
根节点是黑色对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点每个红节点的两个孩子节点必须是黑节点 bool ISRBtree() { if (_Proot->_color == RED)//判断根节点是否为黑色 return false; Node* root = _Proot; int m, n; m = n = 0; while (root) { if (root->_color == BLACK) n++;//记录一条路径的黑节点的个数 root = root->_Left; } return _ISRBtree(_Proot, m, n); } bool _ISRBtree(Node* root, int m, int n) { if (root == nullptr) { if (m == n) return true; else return false; } else { if (root->_color == BLACK) m++; else if (root->_color == RED && root->_Parents && root->_Parents->_color == RED)//判断是否有连续的红节点 { cout << "连续的红节点" << endl; return false; } } return _ISRBtree(root->_Left, m, n) && _ISRBtree(root->_Right, m, n); } public: Node* _Proot; };测试数据
for（int i=0;i<70;i++）结果：
包括构造，插入，验证函数代码和中序遍历代码。（至于删除的代码emmmm… 还在研究中 ?）
template<class K, class V> struct AVLTree { typedef AVLTreeNode<K, V> Node; public: AVLTree() { _Proot = nullptr; } bool Insert(const K& key, const V& value) { if (_Proot == nullptr) { _Proot = new Node(key, value); _Proot->_color = BLACK; return true; } Node* root = _Proot; Node* pnode = nullptr; while (root) { pnode = root; if (root->_value > value) { root = root->_Left; } else if (root->_value < value) { root = root->_Right; } else if (root->_value == value) return true; } root = new Node(key, value); root->_color = RED;//可有可无 if (pnode->_value > value)//改 { pnode->_Left = root; root->_Parents = pnode;//不要忘记父子也要连上 } else { pnode->_Right = root; root->_Parents = pnode; } while (pnode && pnode->_color == RED)//如果插入的父节点为黑色就不需要修改 { Node* grandfather = pnode->_Parents; Node* uncle; if (pnode == grandfather->_Left) { uncle = grandfather->_Right; //三种情况 if (uncle && uncle->_color == RED) { uncle->_color = BLACK; pnode->_color = BLACK; grandfather->_color = RED; root = grandfather; pnode = root->_Parents; } else { if (root == pnode->_Right) { _RotateL(pnode); swap(root, pnode);//完成 } _RotateR(grandfather); grandfather->_color = RED; pnode->_color = BLACK; break; } } else if (pnode == grandfather->_Right) { uncle = grandfather->_Left; //三种情况 if (uncle && uncle->_color == RED) { uncle->_color = BLACK; pnode->_color = BLACK; grandfather->_color = RED; root = grandfather; pnode = root->_Parents; } else { if (root == pnode->_Left) { _RotateR(pnode); swap(root, pnode);//完成 } _RotateL(grandfather); grandfather->_color = RED; pnode->_color = BLACK; break; } } _Proot->_color = BLACK; } return true; } void _RotateL(Node* pnode) { Node* ppnode = pnode->_Parents; Node* Rnode = pnode->_Right; pnode->_Right = Rnode->_Left; if (Rnode->_Left) { Rnode->_Left->_Parents = pnode; } Rnode->_Left = pnode; pnode->_Parents = Rnode; if (ppnode == nullptr)// { _Proot = Rnode; _Proot->_Parents = nullptr; } else { if (ppnode->_Left == pnode) { ppnode->_Left = Rnode; } else if (ppnode->_Right == pnode) { ppnode->_Right = Rnode; } Rnode->_Parents = ppnode; } } void _RotateR(Node* pnode) { Node* ppnode = pnode->_Parents; Node* Lnode = pnode->_Left; pnode->_Left = Lnode->_Right; if (Lnode->_Right) { Lnode->_Right->_Parents = pnode; } Lnode->_Right = pnode; if (ppnode == nullptr) { _Proot = Lnode; _Proot->_Parents = nullptr; } else { Lnode->_Parents = ppnode; if (ppnode->_Left == pnode) { ppnode->_Left = Lnode; } else if (ppnode->_Right == pnode) { ppnode->_Right = Lnode; } } pnode->_Parents = Lnode; } void _RotateRL(Node* pnode) { _RotateR(pnode->_Right); _RotateL(pnode); } void _RotateLR(Node* pnode) { _RotateL(pnode->_Right); _RotateR(pnode); } void showtree() { Node* root = _Proot; _show(root); } void _show(Node* root) { if (nullptr == root) return; _show(root->_Left); cout << root->_value<<" "; _show(root->_Right); } bool _IsBlanace(Node* root)//代码就不在详细解答了，一个简单的判断问题 { if (root == nullptr) return true; int leftHeight = _Height(_Proot->_Left); int rightHeight = _Height(_Proot->_Right); return 10*leftHeight / rightHeight <= 20 || 10 * leftHeight / rightHeight >= 5 && _IsBlanace(root->_Left) && _IsBlanace(root->_Right); } int _Height(Node* root) { if (root == nullptr) { return 0; } int leftheight = _Height(root->_Left); int rightheight = _Height(root->_Right); int i = leftheight > rightheight ? leftheight + 1 : rightheight + 1; return leftheight > rightheight ? leftheight + 1 : rightheight + 1; } bool ISRBtree() { if (_Proot->_color == RED) return false; Node* root = _Proot; int m, n; m = n = 0; while (root) { if (root->_color == BLACK) n++; root = root->_Left; } return _ISRBtree(_Proot, m, n); } bool _ISRBtree(Node* root, int m, int n) { if (root == nullptr) { //cout << m << endl; if (m == n) return true; else return false; } else { if (root->_color == BLACK) m++; else if (root->_color == RED && root->_Parents && root->_Parents->_color == RED) { cout << "连续的红节点" << endl; return false; } } return _ISRBtree(root->_Left, m, n) && _ISRBtree(root->_Right, m, n); } public: Node* _Proot; };