中级C++：红黑树

• 红黑树的特征
• 红黑树节点的定义
• 红黑树的插入
• 验证是否是红黑树
• G.

• 也是对二叉搜索树高度的控制，但没有AVL树（也叫高度平衡二叉搜索树）那么严格；红黑树：最长路径不超过最短路径的两倍。
  • 在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
  • 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
• 红黑树的性质
  • 每个结点不是红色就是黑色；
  • 根节点是黑色的；
  • 如果一个节点是红色的，则它的两个孩子结点是黑色的；（不能有连续的红色）
  • 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点；
  • 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，用来确定有多少条路经的)。
    
• 时间复杂度：
  • 接近平衡，按满二叉树的节点总数来算，h层一共有 2^h-1 个节点，又是搜索二叉树，因此查找一个值只需要查找高度次：
  • 2^h-1 = N ; h = log2 (N+1) ; h = log2 N…
  • 最坏情况：最长路径是最短的2倍，则： h = 2log2 N ,当 N 是10亿时，h 是 30；对于现在的cpu来说，2倍找60 次可以忽略。
• 红黑树与AVL树的比较：
  • 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( log2 N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍。
  • 相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
• 课外阅读：
  • 红黑树的删除…可参考：《算法导论》或者《STL源码剖析》
  • 分析红黑树的一篇博客

#include
using namespace std;
enum Colour
{
	RED,
	BLACK
};

	template
	struct RBTreeNode
	{
		RBTreeNode* _left;
		RBTreeNode* _right;
		RBTreeNode* _parent;
		pair _kv;
		Colour _col;

		RBTreeNode(const pair& kv)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_kv(kv)
			,_col(RED)
		{

		}
	};

• 插入新节点的颜色
  • 根据上述几点性质可知，新插入节点的颜色是红色合适，如果节点父亲是红色，那么影响的只有某个子树的某格子数的某一条边…；
  • 如果节点父亲是黑色，新插入的也是黑色，那么每条路径的黑色节点个数就不一样了，影响的是整个树。
• 插入新节点的父亲节点是红色时，那么必然有祖父结点且为黑；此时看叔叔结点：分两种情况（变色/旋转加变色）
  • （情况一）叔叔节点存在且为红，则父亲和叔叔变红色，祖父结点变红色，继续往上处理；
    • 如果祖父就是根，那么祖父也变黑。
    • 不是根就会变成情况二的情况：因为祖父节点原来是黑色，变成了红色；
    • 对于祖父上面的那一条路径来说，祖父的父亲可能是红，就不满足红黑树的性质了；
    • 所以情况二的 新插入节点 也可能是变了色的祖父节点更新过来的…
  • （情况二）叔叔节点不存在 或 存在且为黑，那么看情况进行单旋变色，或双璇变色；
    • 如果新插入节点是在 父亲 的 左边，父亲也是在 祖父 的 左边，那么进行 右单旋；之后，父亲变黑，祖父变红。
    • 如果新插入节点是在 父亲 的 右边，父亲也是在 祖父 的 右边，那么进行 左单旋；之后，父亲变黑，祖父变红。
    • 如果新插入节点是在 父亲 的 右边，父亲也是在 祖父 的 左边，那么进行 左单旋，再进行右单旋；之后，新插入节点变黑，祖父变红。
    • 如果新插入节点是在 父亲 的 左边，父亲也是在 祖父 的 右边，那么进行 右单旋，再进行左单旋；之后，新插入节点变黑，祖父变红。
      
      
• 插入还是二叉搜索树的插入，这里只展示对节点颜色的处理：
• 旋转和AVL树的旋转一样：看这里

template
		class RBTree
		{
			typedef RBTreeNode Node;
		public:
			RBTree()
				:_root(nullptr)
			{
			}
			..../insert...
		private:
			Node* _root;
		}
          bool Insert(const pair& kv)
			{
				if (_root ==nullptr)
				{
					_root = new Node(kv);
					_root->_col = BLACK;//根节点必须是黑色
					return true;
				}
				Node* parent = nullptr;
				Node* cur = _root;
				while (cur)
				{
					if (cur->_kv.first
						parent = cur;
						cur = cur->_right;
					}
					else if (cur->_kv.first > kv.first)
					{
						parent = cur;
						cur = cur->_left;
					}
					else
					{
						return false;//不允许冗余
					}
				}
				cur = new Node(kv);
				cur->_col = RED;  //如果添加的是黑色，则对整个树都有影响，红色只对一个子树的一个路径有影响
				cur->_parent = parent;
				if (parent->_kv.first_kv.first)
				{
					parent->_right = cur;
				}
				else
				{
					parent->_left = cur;
				}
				//1，叔叔存在且为红，变色往上继续处理；2，叔叔不存在或存在且为黑：旋转+变色
				//若插入节点双亲的颜色是黑色便不需要处理
				while (parent&&parent->_col==RED)
				{
					Node* grandf = parent->_parent;//根不能是黑色，那么必定有个黑色的父亲
					if (grandf->_left==parent)
					{
						Node* uncle = grandf->_right;
						if (uncle && uncle->_col == RED)
						{
							parent->_col = uncle->_col = BLACK;//每条路径上的黑色节点个数保持不变
							grandf->_col = RED;

							cur = grandf;//祖父变红以后迭代往上更新，看没有连续的红色
							parent = cur->_parent;
						}
						else//叔不存在或黑 旋转变色
						{
							//祖父为节点进行右单旋或双旋
							if (cur=parent->_left)
							{
								//右单旋
								RotateR(grandf);
								grandf->_col = RED;
								parent->_col = BLACK;
							}
							else//先左旋 ，再右旋
							{
								RotateL(parent);
								RotateR(grandf);
								cur->_col = BLACK;
								grandf->_col = RED;								
							}
							break;
						}
					}
					else//(grandf->_right==parent)  叔叔存在为红，或不存在为黑
					{
						Node* uncle = grandf->_left;
						if (uncle && uncle->_col == RED)
						{
							parent->_col = uncle->_col = BLACK;
							grandf->_col = RED;

							cur = grandf;//祖父变红以后迭代往上更新，看没有连续的红色
							parent = cur->_parent;
						}
						else
						{
							if (cur=parent->_right)//左单旋
							{
								RotateL(grandf);
								parent->_col = BLACK;
								grandf->_col = RED;
							}
							else//先右旋，再左旋
							{
								RotateR(parent);
								RotateL(grandf);
								cur->_col = BLACK;
								grandf->_col = RED;
							}
							break;
						}
					}

				}
				_root->_col = BLACK;//当叔叔存在且为红，祖父就是根，上面变完色出来把祖父的颜色改为黑色。
				return true;
			}

• 一、中序遍历是否有序
• 二、是否满足红黑树的性质
  • 每一条路径都和我基准值一样则满足每条路径的黑色个数相等
  • 不能有连续的红色：红色节点的两个孩子节点必须是黑色，转换成看红色节点的父亲是不是黑色；因孩子节点可能为空，不好处理。

           bool IsRBTree()
			{
				return _IsRBTree(_root);//包一层，方便外面对象调用
			}
           bool _IsRBTree(Node* cur)
			{
				if (cur==nullptr)
				{
					return true;//空树也是红黑树
				}
				if (cur->_col==RED)
				{
					cout << "根节点不是黑色，不是红黑树" << endl;
					return false;
				}
				int Benchmark = 0;//基准值
				Node* countcur = cur;
				while (countcur)
				{
					if (countcur->_col==BLACK)//每一条路径都和我基准值一样则满足每条路径的黑色个数相等
					{
						++Benchmark;
					}
					countcur = countcur->_left;//任选一条路径作为基准值。
				}
				int layer_black = 0;//递归调用再传一个参数：记录一下每一层到上面总共有的黑色节点个数，这样就方便很多了
				return red_node_is_black(cur)&&
					black_num_is_same(cur, layer_black, Benchmark);
			}
			
           bool red_node_is_black(Node* cur)//看红色节点孩子是不是黑色等于是看有没有连续的红色。
			{
				if (cur==nullptr)
				{
					return true;
				}
				if (cur->_col == RED && cur->_parent->_col != BLACK)
				{
					return false;//当前节点是红，那么必有双亲节点是黑色。
				}

				return red_node_is_black(cur->_left) &&
					red_node_is_black(cur->_right);
			}
			
		bool black_num_is_same(Node* cur, int layer_black, int Benchmark)
			{
				if (cur==nullptr)
				{
					if (layer_black==Benchmark)//路径走完，与基准值比较
					{
						return true;
					}
					else
					{
						return false;
					}
				}
				if (cur->_col==BLACK)
				{
					++layer_black;
				}
				return black_num_is_same(cur->_left, layer_black, Benchmark) &&
					black_num_is_same(cur->_right, layer_black, Benchmark);
			}

下一篇是，将红黑树改造成 map和set 的 底层，模板参数再度来袭，红黑树的迭代器…