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

文章目录

- - - 1.红黑树的概述
    - 2.红黑树的性质
    - 3.红黑树的代码实现
    - - 3.1.红黑树的节点定义
      - 3.2.红黑树的插入操作
      - 3.3.红黑树是否平衡

黑红树是一颗特殊的搜索二叉树，本文在前文的基础上，图解红黑树插入：前文
链接，完整对部分关键代码展示，完整的代码在gitee仓库中：
链接

文章中有错误的地方，欢迎大家指正！如果有帮助到你，也请多多点赞支持！

1.红黑树的概述

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

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

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

2.红黑树的性质

每个结点不是红色就是黑色
根节点必须是黑色的
如果一个节点是红色的，则它的两个孩子结点必须是是黑色的，（即：不会有两个连续的红节点）
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（即：每条路径上黑色的节点相同）
每个叶子结点都是黑色的(此处的叶子结点指的是空结点，即下图的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存在且为红！

在这里插入图片描述

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

在这里插入图片描述

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

单旋的情况：

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

在这里插入图片描述

双旋的情况：

通过上面的例子可以知道，存在uncle且为黑和不存在uncle的处理结果是一样的！
通过下图的判断，是折线：grandfather ->left = parnt；parent->right =cur；通过平衡二叉树的插入操作的学习，可以知道，这种情况先左单旋，再右单旋！
变色：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;
}