史上最详细的红黑树讲解(一篇文章教你手撕红黑树)-Toy模板网

这篇具有很好参考价值的文章主要介绍了史上最详细的红黑树讲解(一篇文章教你手撕红黑树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🔥🔥 欢迎来到小林的博客！！
🛰️博客主页：✈️小林爱敲代码
🛰️博客专栏：✈️数据结构与算法
🛰️欢迎关注：👍点赞🙌收藏✍️留言

今天给大家讲解红黑树，和AVL树一样，这章暂且不讲删除。后续有时间会为大家带来红黑树的删除操作。

每日一句: 生活原本沉闷，但跑起来就会有风。

💖1. 红黑树的概念

红黑树，是一种二叉搜索树，与AVL树不同的是，它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。因此红黑树相比于AVL树，没有那么平衡。30层高度的AVL树换成红黑树可能会有60层，但查找30次和60次并没有什么区别。AVL树的平衡是付出了代价的，它旋转的次数更多了。而红黑树也是平衡的，它旋转的次数并没有AVL多。

💖2. 红黑树的性质

红黑树必须满足以下五点性质，有一条不满足，就不是红黑树了。
1.每个节点不是红色就是黑色
2.根节点是黑色的
3.红节点的孩子必须是黑色
4.每条路径黑色节点的数量相同
5.空节点都是黑色的
满足上面性质的红黑树，它的最长路径中节点的个数不会超过最短路径的2倍

那我们先来观赏一颗红黑树
红黑树一边高的情况,数据结构与算法,小林的C++之路,数据结构,c++
我们可以发现，
每个节点不是黑色就是红色，满足条件1
根节点 50 是黑色的，满足条件2
红色节点的孩子都是黑色，满足条件3
每条路径都有2个黑色节点，满足条件4
所有空节点的孩子都是黑色，不过是空节点，就不需要画出来了。
介绍完红黑树之后，接下来我们来实现一颗红黑树。

💖3. 红黑树的节点创建

首先，我们依旧采用三叉链，一个指针指向左孩子，一个指向右孩子，还有一个指向自己的父亲。再用一个枚举常量col 来记录节点的颜色，kv是存储的一对值。

代码：

enum Color
	{
		RED,
		BLACK
	};

	//红黑树节点
	template<class K,class V>
	struct RBTreeNode
	{
		RBTreeNode(const pair<K,V>& kv)
			: _left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_col(RED)
			,_kv(kv){}
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;
		Color _col;
		pair<K, V> _kv;
	};

💖4.红黑树的定义

红黑树的定义很简单，我们存一个节点指针_root来代表整棵树的根。

//红黑树实现
	template<class K, class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> Node;
	public:
		RBTree():_root(nullptr){}
	private:
		Node* _root;
	};

💖5.节点的插入

个人认为，红黑树的插入并没有AVL那么繁琐。AVL插入时需要考虑的情况太多，而红黑树并不需要考虑太多情况。

假设我们有一颗红黑树
红黑树一边高的情况,数据结构与算法,小林的C++之路,数据结构,c++
那么接下来我们要插入一个10，那么10应该插入20的左边。那么我们让新插入的节点颜色固定为10。根节点颜色固定为黑。

那么我们发现在插入10之后，这颗红黑树是还是正常的，满足了5条性质。此时我们在插入1个25。
红黑树一边高的情况,数据结构与算法,小林的C++之路,数据结构,c++
我们发现插入25之后，这棵树还是正常的。所以我们可以得出一个结论，如果插入节点的父亲是黑色，那么这是一颗正常的红黑树。

那么我们此时再插入一个5，它的父亲节点就是10，也就是红色。
红黑树一边高的情况,数据结构与算法,小林的C++之路,数据结构,c++

这种情况，这颗红黑树就不满足性质3了，因为红节点的孩子必须是黑节点。那么此时我们看它的叔叔，叔叔是25。
那么此时就会出现2种情况

情况1.叔叔存在且为红色
这种情况我们只需要把父亲和叔叔变成黑色，然后把祖父变红，再把cru给祖父，循环操作直到父亲为空即可。
红黑树一边高的情况,数据结构与算法,小林的C++之路,数据结构,c++
这种操作会把我们的根节点变成红色，所以我们在最后的时候强制把根节点变成黑色即可。
最后这颗红黑树就会变成这样

我们可以发现它依然满足上面的五个性质。

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

叔叔不存在或者叔叔为黑色的情况是一样的。
我们先来看叔叔不存在的情况。
叔叔不存在
那么这颗红黑树是这样的
红黑树一边高的情况,数据结构与算法,小林的C++之路,数据结构,c++
这种情况我们就要发生旋转了，因为叔叔不存在，就意味着这颗红黑树已经左边一边高了。所以我们来个右单旋即可。在右边就左单旋，具体的旋转细节可以看我上篇讲解AVL树的文章。

旋转完之后是这样的
红黑树一边高的情况,数据结构与算法,小林的C++之路,数据结构,c++
这时候我们在把 c(新增节点) 和 g(祖父节点)变成红色，再把p(父亲节点)变为黑色。这颗红黑树就调整完毕了。

叔叔为黑的情况
叔叔为黑和叔叔不存在的情况是一样的。
我们来看看叔叔为黑的情况。
红黑树一边高的情况,数据结构与算法,小林的C++之路,数据结构,c++
这时候我们一样要发生旋转。
旋转动图：

然后我们再把c和g变为红色，p变为黑色

这样我们的红黑树就调整完毕了。这是我们的parent在左边，uncle在右边的情况。反过来的逻辑也是一样的。

插入代码：

		bool insert(const pair<K,V> kv)
		{
			//第一次插入
			if (_root == nullptr)
			{
				_root = new Node(kv);
				_root->_col = BLACK;
				return true;
			}
			//先查找值的位置
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					break;
			}
			//如果cur不为空说明有重复的值
			if (cur)
				return false;
			
			//创建新节点
			cur = new Node(kv);
			cur->_parent = parent;
			if (cur->_kv.first > parent->_kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;

			cur->_col = RED;
			//有连续的红节点,需要调整
			while (parent && parent->_col == RED)
			{
				Node* grandparent = parent->_parent;//祖父节点
				//parent是左孩子的情况
				if (parent == grandparent->_left)
				{
					// 叔叔节点
					Node* uncle = grandparent->_right;
					//如果叔叔存在且为红
					if (uncle && uncle->_col == RED)
					{
						//父亲和叔叔变黑
						parent->_col = uncle->_col = BLACK;
						grandparent->_col = RED;
						//迭代
						cur = grandparent;
						parent = cur->_parent;
					}
					else
					{
						//叔叔为黑或者叔叔不存在
						if (cur == parent->_left)
						{
							//右单旋
							RotateR(grandparent); //旋转祖父
							parent->_col = BLACK;
							grandparent->_col = cur->_col = RED;
						}
						else
						{
							//左右双旋
							RotateL(parent);
							RotateR(grandparent);
							cur->_col = BLACK;
							parent->_col = grandparent->_col = RED;
						}	
					}
				}
				else
				{
					//parent是右孩子的情况
					Node* uncle = grandparent->_left;
					//叔叔存在且为红
					if (uncle && uncle->_col == RED)
					{
						uncle->_col = parent->_col = BLACK;
						grandparent->_col = RED;
						cur = grandparent;
						parent = cur->_parent;
					}
					else
					{
						//叔叔不存在或为黑
						if (cur = parent->_right)
						{
							//左单旋
							RotateL(grandparent);
							grandparent->_col = cur->_col = RED;
							parent->_col = BLACK;
						}
						else
						{
							//右左双旋
							RotateR(parent);
							RotateL(grandparent);
							cur->_col = BLACK;
							parent->_col = grandparent->_col = RED;
						}
					}
	
				}
			}
			_root->_col = BLACK;	//不管如何，根节点的颜色一定为黑
			return true;
		}
		//右单旋
		void RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = parent->_right;
			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;

			Node* grandparent = parent->_parent;
			subL->_right = parent;
			parent->_parent = subL;
			if (grandparent == nullptr)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (parent == grandparent->_left)
					grandparent->_left = subL;
				else
					grandparent->_right = subL;
				subL->_parent = grandparent;
			}
		}
		//左单旋
		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;

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

💖6.节点的查找

插入都会了，查找不是轻轻松松。从根开始找，要找的值比当前节点大，就往这棵树的右边找，小就往左边找，找到了就返回。

	pair<K, V>* find(const K& key)
		{
			if (_root == nullptr)
				return nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first > key)
					cur = cur->_left;
				else if (cur->_kv.first < key)
					cur = cur->_right;
				else
					return &cur->_kv;
			}
			return nullptr;
		}

💖7.检查红黑树

当我们代码写出来了之后，还要检查这棵树是否是红黑树。我们可以先找一个基准值(任意一条路径的黑节点数量)。因为红黑树每条路径的黑节点个数是一样的。然后我们有基准值之后，在遍历的过程计算黑节点的数量。如果与基准值一样，那么这棵树所有路径黑节点的数量是相同的。

//检查红黑树是否正常
		bool IsBalance()
		{
			if (_root->_col == RED)
			{
				cout << "根节点为红色" << endl;
				return false;
			}

			//找基准值
			Node* min = _root;
			int banchmark = 0;
			while (min)
			{
				if (min->_col == BLACK)
					banchmark++;
				min = min->_left;
			}
			return _IsBalance(_root,banchmark,0);
		}
		bool _IsBalance(Node* root,int banchmark,int BNNum)
		{
			if (root == nullptr)
			{
				if (banchmark != BNNum)
				{
					cout << "路径中黑节点数量不相等" << endl;
					return false;
				}
				return true;
			}
			if (root->_col == RED && root->_parent->_col == RED)
			{
				cout << "出现连续红节点"<<endl;
				return false;
			}

			if (root->_col == BLACK)
				BNNum++;

			return _IsBalance(root->_left, banchmark, BNNum) &&
			_IsBalance(root->_right, banchmark, BNNum);
		}

全部代码：

#include<iostream>
using namespace std;
#include<time.h>

namespace wyl
{
	enum Color
	{
		RED,
		BLACK
	};

	//红黑树节点
	template<class K,class V>
	struct RBTreeNode
	{
		RBTreeNode(const pair<K,V>& kv)
			: _left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_col(RED)
			,_kv(kv){}
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;
		Color _col;
		pair<K, V> _kv;
	};
	
	//红黑树实现
	template<class K, class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> Node;
	public:
		RBTree():_root(nullptr){}
		bool insert(const pair<K,V> kv)
		{
			//第一次插入
			if (_root == nullptr)
			{
				_root = new Node(kv);
				_root->_col = BLACK;
				return true;
			}
			//先查找值的位置
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					break;
			}
			//如果cur不为空说明有重复的值
			if (cur)
				return false;
			

			//创建新节点
			cur = new Node(kv);
			cur->_parent = parent;
			if (cur->_kv.first > parent->_kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;

			cur->_col = RED;
			//有连续的红节点,需要调整
			while (parent && parent->_col == RED)
			{
				Node* grandparent = parent->_parent;//祖父节点
				//parent是左孩子的情况
				if (parent == grandparent->_left)
				{
					// 叔叔节点
					Node* uncle = grandparent->_right;
					//如果叔叔存在且为红
					if (uncle && uncle->_col == RED)
					{
						//父亲和叔叔变黑
						parent->_col = uncle->_col = BLACK;
						grandparent->_col = RED;
						//迭代
						cur = grandparent;
						parent = cur->_parent;
					}
					else
					{
						//叔叔为黑或者叔叔不存在
						if (cur == parent->_left)
						{
							//右单旋
							RotateR(grandparent); //旋转祖父
							parent->_col = BLACK;
							grandparent->_col = cur->_col = RED;
						}
						else
						{
							//左右双旋
							RotateL(parent);
							RotateR(grandparent);
							cur->_col = BLACK;
							parent->_col = grandparent->_col = RED;
						}	
					}
				}
				else
				{
					//parent是右孩子的情况
					Node* uncle = grandparent->_left;
					//叔叔存在且为红
					if (uncle && uncle->_col == RED)
					{
						uncle->_col = parent->_col = BLACK;
						grandparent->_col = RED;
						cur = grandparent;
						parent = cur->_parent;
					}
					else
					{
						//叔叔不存在或为黑
						if (cur = parent->_right)
						{
							//左单旋
							RotateL(grandparent);
							grandparent->_col = cur->_col = RED;
							parent->_col = BLACK;
						}
						else
						{
							//右左双旋
							RotateR(parent);
							RotateL(grandparent);
							cur->_col = BLACK;
							parent->_col = grandparent->_col = RED;
						}
					}
	
				}
			}
			_root->_col = BLACK;	//不管如何，根节点的颜色一定为黑
			return true;
		}

		pair<K, V>* find(const K& key)
		{
			if (_root == nullptr)
				return nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first > key)
					cur = cur->_left;
				else if (cur->_kv.first < key)
					cur = cur->_right;
				else
					return &cur->_kv;
			}
			return nullptr;
		}


		//检查红黑树是否正常
		bool IsBalance()
		{
			if (_root->_col == RED)
			{
				cout << "根节点为红色" << endl;
				return false;
			}

			//找基准值
			Node* min = _root;
			int banchmark = 0;
			while (min)
			{
				if (min->_col == BLACK)
					banchmark++;
				min = min->_left;
			}
			return _IsBalance(_root,banchmark,0);
		}

	private:
		//右单旋
		void RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = parent->_right;
			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;

			Node* grandparent = parent->_parent;
			subL->_right = parent;
			parent->_parent = subL;
			if (grandparent == nullptr)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (parent == grandparent->_left)
					grandparent->_left = subL;
				else
					grandparent->_right = subL;
				subL->_parent = grandparent;
			}
		}
		//左单旋
		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;

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

		bool _IsBalance(Node* root,int banchmark,int BNNum)
		{
			if (root == nullptr)
			{
				if (banchmark != BNNum)
				{
					cout << "路径中黑节点数量不相等" << endl;
					return false;
				}
				return true;
			}
			if (root->_col == RED && root->_parent->_col == RED)
			{
				cout << "出现连续红节点"<<endl;
				return false;
			}

			if (root->_col == BLACK)
				BNNum++;

			return _IsBalance(root->_left, banchmark, BNNum) &&
			_IsBalance(root->_right, banchmark, BNNum);
		}
		
	private:
		Node* _root;
	};

	//以下是红黑树的测试代码
	void RBTTest1()
	{
		RBTree<int, int> rb;
		srand(time(0));
		int N = 10000000;
		size_t begin1 = clock();
		for (int i = 0; i < N; i++)
		{
			rb.insert(make_pair(i, i));
		}
		size_t end1 = clock();
		cout << "insert " << N << ":" << end1 - begin1 << endl;
		//rb.insert(make_pair(20, 20));
		//rb.insert(make_pair(10, 10));
		//rb.insert(make_pair(5, 5));
		//rb.insert(make_pair(3, 3));
		rb.IsBalance();
	}
}

总结🥳：

💦💦如果有写的有什么不好的地方，希望大家指证出来，我会不断的改正自己的错误。💯💯如果感觉写的还可以，可以点赞三连一波哦~🍸🍸后续会持续为大家更新。

🔥🔥你们的支持是我最大的动力，希望在往后的日子里，我们大家一起进步！！！🔥🔥文章来源地址https://www.toymoban.com/news/detail-793023.html

到了这里，关于史上最详细的红黑树讲解(一篇文章教你手撕红黑树)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！