红黑树（RBTree）

一、红黑树简介

二、红黑树的来源

三、什么是红黑树

四、红黑树的性质

五、红黑树的节点定义

六、红黑树的操作

6.1、红黑树的查找

6.2、红黑树的插入

七、红黑树的验证

八、红黑树和AVL树的比较

一、红黑树简介

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。

二、红黑树的来源

对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

三、什么是红黑树

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或

Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路

径会比其他路径长出俩倍，因而是接近平衡的。

四、红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)，下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点

五、红黑树的节点定义

enum Colour
{
	RED,
	BLACK,
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

这里我们默认节点的颜色是红色：

新插入的节点默认为红色，有利于保持红黑树的平衡性质。当插入一个新节点时，由于新节点默认为红色，可以避免破坏红黑树的规则，从而简化了插入操作后的平衡调整。同时，将新节点默认为红色也有助于降低平衡调整的复杂度，使得红黑树的插入和删除操作更加高效。

六、红黑树的操作

红黑树的基本操作和其他树形结构一样，一般都包括查找、插入、删除等操作。前面说到，红黑树是一种自平衡的二叉查找树，既然是二叉查找树的一种，那么查找过程和二叉查找树一样，比较简单，这里不再赘述。相对于查找操作，红黑树的插入和删除操作就要复杂的多。尤其是删除操作，要处理的情况比较多，下面就来分情况讲解。

6.1、红黑树的查找

Node* Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

6.2、红黑树的插入

parent：父节点
sibling：兄弟节点
uncle：叔父节点（ parent 的兄弟节点）
grand：祖父节点（ parent 的父节点）

红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。

红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色，原因也不难理解。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦（参考红黑树的删除操作，就知道为啥多一个或少一个黑色节点时，调整起来这么麻烦了）。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。所以插入的时候将节点设置为红色，可以保证满足性质 1、2、4、5 ，只有性质3不一定满足，需要进行相关调整。如果是添加根节点，则将节点设定为黑色。

检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何

性质，则不需要调整；

但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连 在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一、 cur为红，p为红，g为黑，u存在且为红

解决方法：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

如果g是根节点，调整完成后，需要将g改成黑色；

如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整，否则不用。

情况二、cur为红，p为红，g为黑，u不存在 / u存在且为黑

解决方法：

如果p为g的左孩子，cur为p的左孩子，则进行右单旋转，p变黑，g变红
如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，p变黑，g变红

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

和情况而类似，只不过情况而是单旋，情况三单旋解决不了问题，所以要双旋。

解决方法：

如果p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，p旋转后再对g进行右单旋，旋转后将cur变黑，g变红
如果p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，p旋转后再对g进行左单旋，旋转后将cur变黑，g变红

插入函数的实现：

bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}

		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(data);
		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				// 情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2+3：u不存在/u存在且为黑，旋转+变色
				{
					//     g
					//   p   u
					// c 
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g
						//   p   u
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						//parent->_col = RED;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // (grandfather->_right == parent)
			{
				//    g
				//  u   p
				//        c
				Node* uncle = grandfather->_left;
				// 情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2+3：u不存在/u存在且为黑，旋转+变色
				{
					//    g
					//  u   p
					//        c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						//    g
						//  u   p
						//    c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

		return true;
	}

旋转代码实现：

void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* ppnode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (ppnode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}

			subR->_parent = ppnode;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* ppnode = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}

七、红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质

bool IsRBTree()
{
    //空树
    if (_root == nullptr)
    {
        return true;
    }
    //根节点为黑色
    if (_root->_col == RED)
    {
        cout << "根节点为红色" << endl;
        return false;
    }
    //黑色结点数量各路径上相同
    //先走一条得到基准值
    int Blacknum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
            Blacknum++;
        cur = cur->_left;
    }
    //检查子树
    int i = 0;
    return _IsRBTree(_root, Blacknum, i);
}

bool _IsRBTree(Node* root, int blacknum, int count)
{
    //递归到空节点
    if (root == nullptr)
    {
        if (blacknum == count)
            return true;
        cout << "各路径上黑色节点个数不同" << endl;
        return false;
    }
	//子节点为红则检查父节点是否为红（通过父节点检查子节点会遇到空节点）
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在连续红色节点" << endl;
        return false;
    }
	//计数黑结点
    if (root->_col == BLACK)
        count++;
	//递归左右子树
    return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
}