数据结构：搜索二叉树 | 红黑树 | 验证是否为红黑树

1.红黑树的概述

平衡二叉树要求左右子树的高度差的绝对值不超过1，所以平衡二叉树是高度平衡的，正是因为它要求严格控制高度差，在频繁的插入的删除的时候导致旋转次数过多带来了一定的性能消耗！

红黑树也是一颗特殊的搜索二叉树，任何一条从根到叶子的路径上各个结点由颜色（红黑）方式的限制，红黑树确保没有一条路径会比其他路径长出两倍（最长路径不会超过最短路径的两倍），它而是接近平衡的。红黑树没有严格要求高度的平衡，所以红黑树在总体的性能上会略优于平衡二叉树（AVL树）。

在现实的各种应用中都是使用红黑树的来充当数据结构，如：Java集合中的TreeMap，C++STL中Set、Map等都是使用红黑树而不是AVL树。可能在查找方面AVL树会由于红黑树，但是几十次的常数差别，在现代CPU（大概每秒几十亿次）来说完全不受影响，AVL树和红黑树查找的时间复杂度都是在一个等级上O(log_2(N))，红黑树在插入和删除会优于AVL树！

2.红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点必须是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点必须是是黑色的，（即：不会有两个连续的红节点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（即：每条路径上黑色的节点相同）
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，即下图的NIL)

关于路径问题

上图有11条路径

为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍

最短路径：全黑的路径 最长路径：一黑一红相间的路径

上面的图情况就是最大的（4个节点/2个节点 = 2倍）的情况！

3.红黑树的代码实现

3.1.红黑树的节点定义

enum color
{
   
    RED,
    BLACK
};

template<class K, class V>
struct RBNode
{
   
    std::pair<K, V> _kv;

    RBNode<K, V>* _left;
    RBNode<K, V>* _right;
    RBNode<K, V>* _parent;
    color _color;

    RBNode(const std::pair<K, V> kv)
        :_kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _color(RED)
    {
   }
};

3.2.红黑树的插入操作

第一大类情况：cur、parent为红，grandfather为黑，uncle存在且为红！

1. 将parent和uncle都变为黑，grandfather变为红
2. 但是grandfather，如果是根节点直接将其设为黑即可，
3. 如果grandfather不为红，如下图：则将cur = grandfather继续重复步骤1和步骤2

**第二大类情况：**cur为红，parent为红，grandfather为黑，uncle不存在或uncle存在且为黑

单旋的情况：

1. 下图是uncle不存在或uncle存在且为黑单旋的情况，通过节点的位置判断单旋：如条件是grandfather ->left = parent; parent->left = cur; 直线说明是单旋，都是左边说明右边高，要右单旋！
2. 变色，grandfather变为红，parent变为黑色；可以看到，调整后的根据原来的grandfather是黑色，无论往上的祖先是何种颜色，都不会出现两个红色连一起的情况,不用往上调整了！

双旋的情况：

1. 通过上面的例子可以知道，存在uncle且为黑和不存在uncle的处理结果是一样的！
2. 通过下图的判断，是折线：grandfather ->left = parnt；parent->right =cur；通过平衡二叉树的插入操作的学习，可以知道，这种情况先左单旋，再右单旋！
3. 变色：grandfather变为红，cur变为黑；可以看到，调整后的根据原来的grandfather是黑色，无论往上的祖先是何种颜色，都不会出现两个红色连一起的情况,不用往上调整了！

上面就是红黑树的**左子树的插入操作！右子树的插入99%是一样的！**可能没有99%，哈哈哈！但是是类似的操作！简单画个图：

第一大类情况：

第二大类情况：

单旋情况：

双旋情况：

bool insert(const std::pair<K, V>& kv)
{
   
	if (_root == nullptr)
	{
   
		_root = new Node(kv);
		_root->_color = BLACK;
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
   
		if (cur->_kv.first < 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);

	if (parent->_kv.first < kv.first)
	{
   
		parent->_right = cur;
	}
	else
	{
   
		parent->_left = cur;
	}

	cur->_parent = parent;

	while (parent && parent->_color == RED)
	{
   
		Node* grandfather = parent->_parent;

		// parent是左子树
		if (parent == grandfather->_left)
		{
   
			
			Node* uncle = grandfather->_right;
			// 第一大类：uncle存在且为红
			if (uncle && uncle->_color == RED)
			{
   
				// 改变颜色
				parent->_color = uncle->_color = BLACK;
				grandfather->_color = RED;

				// 修改条件，继续往上执行
				cur = grandfather;
				parent = cur->_parent;
			}
			else // 第二大类：uncle不存在或uncle存在且为黑
			{
   
				// 单旋情况
				if (cur == parent->_left)
				{
   
					// 右单旋
					RotateRight(grandfather);

					// 改变颜色
					parent->_color = BLACK;
					grandfather->_color = RED;
				}
				else  // 双旋情况
				{
   
					RotateLeft(parent);
					RotateRight(grandfather);

					cur->_color = BLACK;
					grandfather->_color = RED;
				}

				// 这种情况就不用重复调整，直接跳出循环
				break;
			}
		}
		else // parent是右子树
		{
   
			Node* uncle = grandfather->_left;

			if (uncle && uncle->_color == RED)
			{
   
				parent->_color = uncle->_color= BLACK;
				grandfather->_color = RED;

				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
   
				if (cur == parent->_right)
				{
   
					RotateLeft(grandfather);

					parent->_color = BLACK;
					grandfather->_color = RED;
				}
				else
				{
   
					RotateRight(parent);
					RotateLeft(grandfather);

					cur->_color = BLACK;
					grandfather->_color = RED;
				}
				break;
				
			}
			
		}
	}
	// 根绝对为黑色
	_root->_color = BLACK;

	return true;
}

3.3.红黑树是否平衡

根据每条路径的黑节点的个数相同判断！

bool isBanlan()
{
   
    // 如何判断是否为红黑树
    // 1.高度行不行？ 不行！ 2.能不能根据节点的个数不操作2倍的关系？ 也不行
    // 3.那有什么是确定的？所有路径黑节点的个数相等！根据这个性质！
    Node* cur = _root;

    int checkNum = 0;
    while (cur)
    {
   
        if(cur->_color == BLACK)
            checkNum++;

        cur = cur->_left;
    }
  
    return isBanlan(_root,checkNum,0); 
}

bool isBanlan(Node* root,int &checkNum,int blackNum)
{
   
	if (root == nullptr)
		return true;

	if (root->_color == BLACK)
	{
   
		blackNum++;
	}

	if (root->_left == nullptr && root->_right == nullptr)
	{
   
		return blackNum == checkNum ? true : false;
	}
	bool left = isBanlan(root->_left, checkNum, blackNum);
	bool right = isBanlan(root->_right, checkNum, blackNum);
	
	return left && right;
}