红黑树的模拟实现

前言

我在前面的文章中，已经详细讲解了二叉搜索树（二叉搜索树的模拟实现-CSDN博客）、AVL树（AVL树模拟实现-CSDN博客）的模拟实现，终于，我要讲解红黑树啦~~~，让我们进入正题吧

ヾ(≧▽≦*)o

概念

红黑树也是一棵二叉搜索树，它有如下特点

1、每个节点不是红色就是黑色 （从红黑树名字就可得知） 2、根节点是黑色的 （这是检查红黑树是否正确的一个判断条件） 3、如果一个节点是红色的，那它的两个孩子就是黑色的 （因此在每个路径上，不可以出现连续的两个红色节点，这既可以作为检查红黑树是否正确的判断条件，也是判断插入一个节点后是否需要进行旋转操作的一个条件） 4、从该节点到所有后代叶节点的简单路径上，均包含相同数目的黑色节点 （这是检查红黑树是否正确的一个判断条件）

这些特点使得红黑树效率也很高，因为他们构成了一个大特点：

最长路径的节点个数 <= 2 * 最短路径的节点个数

为什么红黑树满足最长路径的节点个数 <= 2 * 最短路径的节点个数？

通过第四个特点，我们思考一下：

(1) 最短路径满足什么条件？ (2) 从最短路径的情况能推断出最长路径应该长什么样？

答案揭晓

(1) 最短路径满足什么条件？

答：当该路径所有节点都是黑色节点时，该路径最短

(2) 从最短路径的情况能推断出最长路径应该长什么样？

答：当该路径黑红相间时，该路径最长

举例

当每条路径上的黑色节点数为3时

❁ 当所有节点为黑色时，该路径长为3 ❁ 当该路径黑红相间时，该路径长为6

所以红黑树满足：最长路径的节点个数 <= 2 * 最短路径的节点个数

下图就清晰明了了

红黑树诞生原因

我们通过了解AVL树可知，AVL树的效率非常高，它通过维持左右子树高度差的绝对值 < 2来维持平衡，如果该绝对值 >= 2，则将进行旋转，在面对杂乱顺序的数据的情况下，仍然游刃有余。

但是，当数据是有序的，也就是基本升序或者降序时，AVL树将花大量时间在旋转上，这就使得AVL树的效率变低，而造成这一结果的原因是：AVL树追求的是极度平衡。

【注】这一特点使得AVL树高度较低，面对100w个数据，树的高度也是在27~28之间，这使得在最坏情况下，我们需要查找比较的次数控制在30以内，这也是AVL树效率高的原因

因此，红黑树在付出更少的旋转的代价下，诞生了

红黑树的模拟实现

“颜色”定义

虽然红黑树有颜色，但是红色和黑色并不是真的颜色，而是用了枚举enum的知识，将字符串转化为数字（内部），因此黑色红色的定义就是一个枚举

代码语言：javascript复制

enum COLOR
{
	BLACK,
	RED
};
// 枚举常量通常用大写

基本数据结构定义

RBTreeNode的定义

该部分和AVL树极其相似（忘记的可以去复习哦：AVL树模拟实现-CSDN博客），只不过多了一个颜色的成员

代码语言：javascript复制

template <typename T, typename V>
struct RBTreeNode//RadBlackTree的缩写
{
	RBTreeNode<T,V>* _left;
	RBTreeNode<T, V>* _right;
	RBTreeNode<T, V>* _parent;
	pair<T, V> _data;
	COLOR _col;/**/

	RBTreeNode(const pair<T, V>& kv)// 构造函数
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(kv)
		, _col(RED)
		/*
		插入节点起初都为红色最好，这样只需要检查  当前所在子树  是否出现连续的红节点的情况，
		若为黑色将会改变该路径的长度，将会影响   所有路径  
		*/
	{}
};

RBTree的定义

仍然和普通的树一样

代码语言：javascript复制

template <typename T, typename V>
class RBTree
{
	typedef RBTreeNode<T, V> Node;
public:
	
private:
	Node* _root = nullptr;
};

基本操作实现

Insert函数

所有的二叉搜索树都一样，最关键的部分就是Insert部分，而红黑树的Insert部分无非就是 = 平衡的调整颜色的变换

也就是说

Insert = 旋转变色

基础知识

“叔叔”这个身份的认知

我们在红黑树的插入部分，需要注意的就是“叔叔”这个角色，叔叔就是自己的父亲的兄弟，也就是自己爷爷的另一个儿子，“叔叔”将会是插入操作的重要部分。

插入原则

❁ 保证目前子树的所有路径的黑色节点数不变，否则和插入黑色节点没区别（将影响所有路径） ❁ 根节点必须是黑色

插入的准备工作

在插入前，我们首先要做的就是找到

❁ 插入位置 ❁ 插入位置的父亲

这一部分也和二叉搜索树相同啦

代码语言：javascript复制

bool Insert(const pair<T, V>& kv)
{
    Node* cur = _root;
    Node* parent = nullptr;

    while (cur)
    {
        parent = cur;
        if (kv.second > cur->_data.second)
        {
            cur = cur->_right;
        }
        else if (kv.second < cur->_data.second)
        {
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }

    Node* newnode = new Node(kv);
    newnode->_parent = parent;
    if (kv.second > parent->_data.second)
    {
        parent->_right = newnode;
    }
    else if (kv.second < parent->_data.second)
    {
        parent->_left = newnode;
    }

    
    cur = newnode;
    while (parent && parent->_col == RED)
    {
        Node* grandfather = parent->_parent;
        Node* uncle;

        if (parent == grandfather->_left)
        {
            uncle = grandfather->_right;
        }
        else
        {
            uncle = grandfather->_left;
        }
    }

    _root->_col = BLACK; /*重点(插入原则：根节点为黑色)*/

    return true;
}

插入节点的颜色定义

我在“基础数据结构定义”部分已经注释了：

插入节点起初都为红色最好，这样只需要检查 当前所在子树 是否出现连续的红节点的情况，

若为黑色将会改变该路径的长度，将会影响 所有路径

通过这里，我们就知道我们插入的节点应该起初定义为红色

但是我们红黑树的一个重要特点就是：一条路径下不能有连续的红色节点

这一点造成我们插入一个数据后，需要判断其父亲的颜色

❁ 如果父亲为黑色，那么不需要在意 ❁ 如果父亲为红色，那我们需要按情况调整，情况已经在下面列举出来啦，让我们看看吧(´▽`ʃ♡ƪ)

情况分类

情况1：根节点为空

这个情况自然是第一个节点插入的时候，只需要给_root分配空间，并将其颜色设置为黑色，就可以返回啦

代码语言：javascript复制

if (_root == nullptr)
{
	_root = new Node(kv);
	_root->_col = BLACK;
	return true;
}

情况2：叔叔为红色

如下图所示

我们需要满足“插入原则”

1、该子树所有路径黑色节点数不变

所以我们可以通过如下操作来改变：

(1) 父亲必须变为黑色（这是一定的）根据第一点，我们会发现该子树最左边的路径的黑色节点数增加1，为了不改变路径的黑色节点数，我们进行第二步 (2) 爷爷变为红色根据红黑树的特点：不可以有连续的两个红色节点。我们进行第三步 (3) 叔叔变为黑色

如下图所示

细心的读者可能会发现：爷爷的颜色变为红色了

在红黑树这个非红即黑的树下，我们就需要对“红色”极其敏感

这里爷爷不一定是祖先，所以，我们应该注意爷爷的父亲是什么颜色，因此将更新cur = grandfather，parent也随其改变，parent = cur->_parent

cur = grandfather，parent也随其改变，parent = cur->_parent

代码如下

代码语言：javascript复制

if (uncle && uncle->_col == RED/*叔叔颜色是红色*/)
{
    /*只需要变色,然后grandfather变为cur*/
    /*
        grandfather变为红色
        parent和uncle变为黑色
    */

    grandfather->_col = RED;
    uncle->_col = parent->_col = BLACK;
    
    // 继续向上更新
    cur = grandfather;
    parent = cur->_parent;
}

情况2：叔叔不存在或者叔叔为黑色

这两种情况我们需要进行的操作如下：

旋转变色 旋转： 左左、右右情况同AVL树的旋转左右、右左情况按照cur的情况分析：如果parent是左孩子cur是右孩子，左旋parent，然后就转化为左左情况如果parent是右孩子cur是左孩子，右旋parent，然后就转化为右右情况 变色： parent变为黑色，因为他变为了该子树的祖先 grandfather、cur变为红色，为了不影响每条路径的黑色节点个数

分析

1、叔叔不存在

左左情况

红黑树是一棵“近似平衡”的树，但如上图所示，该树不平衡，这个时候我们就需要“旋转”

根据AVL树的知识，我们就可以知道该树为“左左情况”，因此我们需要“右旋”，如下所示

而插入原则规定：不可改变该子树路径中的黑色节点个数

因此这里我们需要保证每条路径的黑色节点数目不变，因此

1、将parent的颜色改为黑色 2、新插入节点和 grandfather的颜色改为红色

同样，我们观察一下最上面的节点，我们可以发现，它的颜色为黑色，因此我们不需要向上更新

2、叔叔为黑色

左左情况

根据叔叔不存在且为“左左”的情况，我们同样可以知道，叔叔存在时的“左左”情况可以写为：

1、右旋grandfather 2、更改颜色（parent变黑色，cur和grandfather变红色）

通过以上可见，uncle不存在和 uncle为黑色的情况的处理方法一样，所以如下部分我将以 uncle为黑色的情况讲述~(￣▽￣)~*

代码语言：javascript复制

    if (parent == grandfather->_left)
    {
        if (cur == parent->_left)
        {
            // 左左情况
            // 右旋
            RotateR(grandfather);

            // 变色
            parent->_col = BLACK;
            cur->_col = grandfather->_col = RED;
        }
    }

右右情况

很显然，右右情况和左左情况类似，只不过旋转方向变了，因此它的操作如下：

1、左旋grandfather 2、parent的颜色 = 黑色，cur的颜色 = grandfather的颜色 = 红色

代码语言：javascript复制

    else
    {
        if (cur == parent->_right)
        {
            // 右右情况
            // 左旋
            RotateL(grandfather);

            // 变色
            parent->_col = BLACK;
            cur->_col = grandfather->_col = RED;
        }
    }

左右情况

这种情况看似复杂，其实我们能发现：这棵树不平衡。

因此我们思路就是：先变平衡。

很显然，从parent那里就已经不平衡了，因此我们需要左旋parent

我们会发现：这个情况变为了“左左”情况！！！！！！！！

因此我们只需要右旋grandfather就好，并更改颜色

颜色更改：

cur = 黑色 parent = grandfather = 红色

我们可以发现：最上面的节点为黑色。

因此我们不用继续向上更新

代码语言：javascript复制

 // 左右情况

 // 先左旋parent
 RotateL(parent);
 // 再右旋grandfather
 RotateR(grandfather);

 // 变色
 cur->_col = BLACK;
 parent->_col = grandfather->_col = RED;

右左情况

同样，和左右情况类似，步骤：

1、右旋parent 2、变为了“右右”情况，左旋grandfather 3、更改颜色： cur = 黑色 parent = grandfather = 红色

代码语言：javascript复制

 // 右左情况

 // 先右旋parent
 RotateR(parent);
 // 再左旋grandfather
 RotateL(grandfather);

 // 变色
 cur->_col = BLACK;
 parent->_col = grandfather->_col = RED;

IsBalance函数

该部分用来检查该红黑树是否正确

代码语言：javascript复制

public:
	bool IsBalance()
	{
		return _IsBalance(_root);
        // 这种在外部接口里面调用内部接口的原因我在AVL树和二叉搜索树部分讲过
        // 原因：这样子使用就不需要设置外部接口让类外访问_root，再调用该函数
	}
private:
	bool _IsBalance(Node* root, int numfirst = -1/*第一条路径的黑色节点个数*/, int num = 0/*该路径黑色节点的个数*/)
	{
		if (root == nullptr)// 到了一条路径的末尾
		{
			if (numfirst == -1)// 说明是第一条路径
			{
				numfirst = num;
				return true;
			}
			else// 不是第一条路就
			{
				// 打印提示信息方便定位插入哪个部分代码不对
				if (numfirst != num)
					cout << "不是所有路径的黑色节点个数相同" << endl;

				return numfirst == num;// 判断每条路径的黑色节点个数是否相同
			}
		}

		// 根必须为黑色
		if (root == _root && _root && root->_col == RED)
		{
			cout << "根为红色" << endl;
			return false;
		}

		// 不能有连续的红色
		if (root->_col == RED)
		{
			if (root->_left && root->_left->_col == RED)
			{
				cout << "两个连续节点为红色" << endl;
				return false;
			}

			if (root->_right && root->_right->_col == RED)
			{
				cout << "两个连续节点为红色" << endl;
				return false;
			}
		}
		else // 每条路径的黑色节点数相同
		{
			return _IsBalance(root->_left, numfirst, num   1)
				&/*注意不是&&*/ _IsBalance(root->_right, numfirst, num   1);
		}

		return true;
	}

测试代码

我们可以采用随机数的方法来检测我们的代码是否有bug哦，以下部分就是该方法的代码啦

代码语言：javascript复制

void test()
{
	const int N = 10000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));// 随机数种子
	
	for (size_t i = 0; i < N; i  )
	{
		v.push_back(rand()   i);//   i：使得数据更随机
	}
	
	size_t begin2 = clock();// 记录Insert部分的起始时间
	RBTree<int, int> t;
	for (auto e : v)
	{
		//cout << "Insert:" << e << "->";
		t.Insert(make_pair(e, e));
		//cout << t.IsBalance() << endl;
	}
	size_t end2 = clock();// 记录Insert部分的结束时间
	
	cout << "Insert:" << end2 - begin2 << endl;// 计算Insert  10000000个数据时所需要的时间
	
	cout << t.IsBalance() << endl;
}

中序遍历部分就和普通树的部分一样啦，这里就不过多赘述啦

总代码

代码语言：javascript复制

#pragma once

enum COLOR
{
	BLACK,
	RED
};

template <typename T, typename V>
struct RBTreeNode
{
	RBTreeNode<T,V>* _left;
	RBTreeNode<T, V>* _right;
	RBTreeNode<T, V>* _parent;
	pair<T, V> _data;
	COLOR _col;

	RBTreeNode(const pair<T, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(kv)
		, _col(RED)
		/*
		插入节点起初都为红色最好，这样只需要检查  当前所在子树  是否出现连续的红节点的情况，
		若为黑色将会改变该路径的长度，将会影响   所有路径  
		*/
	{}
};

template <typename T, typename V>
class RBTree
{
	typedef RBTreeNode<T, V> Node;
public:
	bool Insert(const pair<T, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		
		while (cur)
		{
			parent = cur;
			if (kv.second > cur->_data.second)
			{
				cur = cur->_right;
			}
			else if (kv.second < cur->_data.second)
			{
				cur = cur->_left;
			}
			else
				return false;
		}

		Node* newnode = new Node(kv);
		newnode->_parent = parent;
		if (kv.second > parent->_data.second)
		{
			parent->_right = newnode;
		}
		else if (kv.second < parent->_data.second)
		{
			parent->_left = newnode;
		}

		cur = newnode;
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			Node* uncle;

			if (parent == grandfather->_left)
			{
				uncle = grandfather->_right;
			}
			else
				uncle = grandfather->_left;

			if (uncle == nullptr/*叔叔不存在*/ || uncle->_col == BLACK/*叔叔颜色是黑色*/)
			{
				/*旋转   变色*/
				/*
				旋转：
					左左、右右情况同AVL树的旋转
					左右、右左情况按照cur的情况分析：
						如果parent是左孩子cur是右孩子，左旋parent，然后就转化为左左情况
						如果parent是右孩子cur是左孩子，右旋parent，然后就转化为右右情况
				变色：
					p变为黑色，因为他变为了该子树的组先
					g、c变为红色，为了不影响每条路径的黑色节点个数
				*/

				// 旋转
				if (parent == grandfather->_left)
				{
					if (cur == parent->_left)
					{
						// 左左情况
						// 右旋
						RotateR(grandfather);

						// 变色
						parent->_col = BLACK;
						cur->_col = grandfather->_col = RED;
					}
					else
					{
						// 左右情况

						// 先左旋parent
						RotateL(parent);
						// 再右旋grandfather
						RotateR(grandfather);

						// 变色
						cur->_col = BLACK;
						parent->_col = grandfather->_col = RED;
					}
				}
				else
				{
					if (cur == parent->_right)
					{
						// 右右情况
						// 左旋
						RotateL(grandfather);

						// 变色
						parent->_col = BLACK;
						cur->_col = grandfather->_col = RED;
					}
					else
					{
						// 右左情况

						// 先右旋parent
						RotateR(parent);
						// 再左旋grandfather
						RotateL(grandfather);

						// 变色
						cur->_col = BLACK;
						parent->_col = grandfather->_col = RED;
					}
				}

				break;
			}
			else// if (uncle->_col == RED/*叔叔颜色是红色*/)
			{
				/*只需要变色,然后grandfather变为cur*/
				/*
				grandfather变为红色
				parent和uncle变为黑色
				*/

				grandfather->_col = RED;
				uncle->_col = parent->_col = BLACK;
				
				// 继续向上更新
				cur = grandfather;
				parent = cur->_parent;
			}
		}

		_root->_col = BLACK;/*重点*/

		return true;
	}

	// 左单旋
	void RotateL(Node* root)
	{
		Node* subR = root->_right;
		Node* subRL = subR->_left;/*可能为空*/

		root->_right = subRL;

		if (subRL)
		{
			subRL->_parent = root;
		}
		subR->_left = root;

		subR->_parent = root->_parent;
		root->_parent = subR;

		if (root == _root)
			_root = subR;

		if (subR->_parent)
		{
			if (root == subR->_parent->_left)
			{
				subR->_parent->_left = subR;
			}
			else
				subR->_parent->_right = subR;
		}
	}

	// 右单旋
	void RotateR(Node* root)
	{
		Node* subL = root->_left;
		Node* subLR = subL->_right;/*可能为空*/

		root->_left = subLR;

		if (subLR)
		{
			subLR->_parent = root;
		}
		subL->_right = root;

		subL->_parent = root->_parent;
		root->_parent = subL;

		if (root == _root)
			_root = subL;

		if (subL->_parent)
		{
			if (root == subL->_parent->_left)
			{
				subL->_parent->_left = subL;
			}
			else
				subL->_parent->_right = subL;
		}
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	// 检查是否平衡时用
	void PreOrder()
	{
		_PreOrder(_root);
		cout << endl;
	}

	void _PreOrder(Node* root)
	{
		if (root == nullptr)
			return;

		cout << root->_data.first << "(" << root->_col << ") ";
		_PreOrder(root->_left);
		_PreOrder(root->_right);
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	bool IsBalance2()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		//参考值
		int refVal = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				  refVal;
			}

			cur = cur->_left;
		}

		int blacknum = 0;
		return Check(_root, blacknum, refVal);
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_data.first << " ";
		_InOrder(root->_right);
	}

	bool _IsBalance(Node* root, int numfirst = -1/*第一条路径的黑色节点个数*/, int num = 0)
	{
		if (root == nullptr)
		{
			if (numfirst == -1)
			{
				numfirst = num;
				return true;
			}
			else
			{
				// 打印提示信息方便定位插入哪个部分代码不对
				if (numfirst != num)
					cout << "不是所有路径的黑色节点个数相同" << endl;

				return numfirst == num;
			}
		}

		// 根必须为黑色
		if (root == _root && _root && root->_col == RED)
		{
			cout << "根为红色" << endl;
			return false;
		}

		// 不能有连续的红色
		if (root->_col == RED)
		{
			if (root->_left && root->_left->_col == RED)
			{
				cout << "两个连续节点为红色" << endl;
				return false;
			}

			if (root->_right && root->_right->_col == RED)
			{
				cout << "两个连续节点为红色" << endl;
				return false;
			}
		}
		else // 每条路径的黑色节点数相同
		{
			return _IsBalance(root->_left, numfirst, num   1)
				&/*注意不是&&*/ _IsBalance(root->_right, numfirst, num   1);
		}

		return true;
	}

	// 根节点->当前节点这条路径的黑色节点的数量
	bool Check(Node* root, int blacknum, const int refVal)
	{
		if (root == nullptr)
		{
			//cout << balcknum << endl;
			if (blacknum != refVal)
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "有连续的红色节点" << endl;

			return false;
		}

		if (root->_col == BLACK)
		{
			  blacknum;
		}

		return Check(root->_left, blacknum, refVal)
			&& Check(root->_right, blacknum, refVal);
	}

private:
	Node* _root = nullptr;
};

完结撒花~❀❀❀❀❀❀❀❀❀

快开学啦，祝大家在新的一学期收获满满哦，脑子不好的小菜鸟和你一起加油哦(●ˇ∀ˇ●)

数据搜索 parent return root

0 人点赞

红黑树的模拟实现

前言

概念

为什么红黑树满足 最长路径的节点个数 <= 2 * 最短路径的节点个数？

答案揭晓

举例

红黑树诞生原因

红黑树的模拟实现

“颜色”定义

基本数据结构定义

RBTreeNode的定义

RBTree的定义

基本操作实现

Insert函数

基础知识

“叔叔”这个身份的认知

插入原则

插入的准备工作

插入节点的颜色定义

情况分类

情况1：根节点为空

情况2：叔叔为红色

情况2：叔叔不存在或者叔叔为黑色

分析

1、叔叔不存在

2、叔叔为黑色

IsBalance函数

测试代码

总代码

为什么红黑树满足最长路径的节点个数 <= 2 * 最短路径的节点个数？