红黑树：

红黑树是一颗二叉搜索树，但是它在每个节点上都增加了一个存储位来表示节点的颜色，这个颜色非RED 即BLACK。 红黑树保证最长路径不超过最短路径的2倍，因而近似于平衡。

红黑树是满足下面红黑树性质的二叉搜索树 1. 每个节点，不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的，则它的两个子节点是黑色的。（意思就是没有连续的两个红节点）。 4. 对于每个节点，从该节点到其他后代叶节点的简单路径上，均包含有相同数目的黑色节点。

从上面的性质可以推断出： 为什么红黑树可以保证最长路径不超过最短路径的两倍？

很容易可以猜测出： 最长路径：红黑节点交替出现的一条路径； 最短路径：只有黑节点的一条路径。

插入算法图形解析：

在调节红黑树中节点的颜色使得红黑树恢复平衡时，需要用一个循环来调整，而这个循环的条件应该是什么？需要好好考虑。

观察上面的三种情况，可以发现，一直在调整cur/p/g三个节点的颜色以及位置从而使得红黑树达到平衡。

在调整的过程中，可以发现改变颜色的节点一直是节点p和g，而cur（新插入的节点或者祖父节点）节点的颜色一直不变，而且parent和cur的相对位置一直不变， 所以当父节点的颜色时黑色时，就说明这个红黑树已经调节好了。 要特别注意：当cur代表的是不是新增节点而是从下面调节上来的祖父节点——————-》这种情况还需要再继续向上调节（类似于一种新的情况—》有可能是第一种情况也有可能是第二、三种情况）。

代码：

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include <assert.h> using namespace std; enum Color { BLACK, RED, }; template<class K, class V> struct RBTreeNode { RBTreeNode() {} RBTreeNode(const K& key, const V& value) :_key(key) , _value(value) , _left(NULL) , _right(NULL) , _parent(NULL) , _color(RED) {} K _key; V _value; Color _color; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; }; template<class K,class V> class RBTree { typedef RBTreeNode<K, V> Node; public: RBTree() :_root(NULL) {} bool Insert(const K& key, const V& value) { //注意:插入的节点一般最好是红色节点（为了保证每条路径的黑色节点个数不变） if (NULL == _root) { _root = new Node(key, value); _root->_color = BLACK;//根节点一定是黑色 return true; } Node* cur = _root; Node* parent = NULL; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } //cur-->要插入的位置 cur = new Node(key, value);//要插入的非根节点都是红色 if (parent->_key > key) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //插入节点，需要判断红黑树的规则 //1.cur的父亲节点为黑色节点，可以直接退出 if (parent->_color == BLACK) { return true; } //注意循环条件（因为三种情况下的变色都不会改变cur的颜色，而parent永远都是cur的parent） //所以只要parent的颜色为黑即可结束 while (parent && parent->_color == RED) { //parent->color 为红--->祖父一定存在 Node* grandFather = parent->_parent; if (parent == grandFather->_left)//uncle为祖父的右孩子 { Node* uncle = grandFather->_right; //第一种情况 if (uncle && uncle->_color == RED) { //将p和u的颜色从红变黑，然后将祖父的颜色变红 parent->_color = uncle->_color = BLACK; grandFather->_color = RED; if (grandFather->_parent && grandFather->_parent->_color == RED)//继续向上检测 { cur = grandFather; parent = cur->_parent; grandFather = parent->_parent; } else { //grandfather的父亲不存在或者grandFather的父亲的颜色为黑 break; } } else { //uncle为黑或者uncle不存在----》需要旋转 //第二种情况/或者第三种情况 if (cur == parent->_right) { _RotateL(parent); swap(parent, cur); } _RotateR(grandFather); parent->_color = BLACK; grandFather->_color = RED; } } else//uncle是grand的左孩子 {//第一种情况 Node* uncle = grandFather->_left; if (uncle && uncle->_color == RED) { parent->_color = BLACK; uncle->_color = BLACK; grandFather->_color = RED; if (grandFather->_parent && grandFather->_parent->_color == RED) { cur = grandFather; parent = cur->_parent; grandFather = parent->_parent; } else { break; } } else { //处理第三或第二种情况 if (cur == parent->_left) { _RotateR(parent); swap(parent, cur); } _RotateL(grandFather); parent->_color = BLACK; grandFather->_color = RED; } } } _root->_color = BLACK; } ~RBTree() { _Destroy(_root); } bool IsBalance() { if (NULL == _root) { return true; } int blackNums = 0; int nums = 0; Node* left = _root; while(left) { if (left->_color == BLACK) { blackNums++; } left = left->_left; } return _IsBalance(_root,nums,blackNums); } void InOrder() { _InOrder(_root); } private: void _Destroy(Node* root) { if (NULL == root) { return; } _Destroy(root->_left); _Destroy(root->_right); delete root; root = NULL; } void _InOrder(Node* root) { if (NULL == root) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } //--------------------------*******判断红黑树是否平衡（主要是判断是否满足三个规则）*******—————————— bool _IsBalance(Node* root,int nums,const int blacknums) { if (NULL == root) { return true; } if (root->_color == RED && root->_parent->_color == RED) { cout << "有连续的红节点" << root->_key << " "; return false; } if (root->_color == BLACK) { nums++; } if (root->_left == NULL && root->_right == NULL)//当前节点是叶子节点时 { if (nums != blacknums) { cout << "黑色节点的数量不相等" << root->_key << endl; return false; } } return _IsBalance(root->_left, nums, blacknums) && _IsBalance(root->_right, nums, blacknums);//如果左子树中有连续红节点不需要查看右子树了 } //---------------------------****************---------------------- void _RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } subL->_right = parent; Node* ppNode = parent->_parent; parent->_parent = subL; if (NULL == ppNode) { _root = subL; _root->_parent = NULL; } else { if (parent == ppNode->_left) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; } } void _RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } subR->_left = parent; Node* ppNode = parent->_parent; parent->_parent = subR; if (NULL == ppNode) { _root = subR; subR->_parent = NULL; } else { if (parent == ppNode->_left) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } } Node* _root; };