1. Toy模板网首页
  2. > Toy博客

数据结构：红黑树讲解（C++）

9月前 作者：派小星233 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构：红黑树讲解（C++）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.前言

  • 本文旨在理解红黑树基本概念以及变色旋转规则，以理解C++map和set的底层原理，不会讲红黑树的删除操作。
  • 对于基本的旋转操作(单旋和双旋)，本文不会展开讲，详细讲解在这里：
    AVL树旋转讲解。



2.红黑树简述

2.1概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保最长路径不超过最短路径两倍，因而是接近平衡的。


2.2性质

  1. 每个节点不是红色就是黑色。
  2. 根部节点是黑色的。(为了减少旋转次数，后面讲旋转大家就明白了）
  3. 对于一个红节点，它的孩子只能是黑色。(即一条路径上不能出现连续的红色节点)
  4. 每条路径都必须包含相同数量的黑色节点。

通过上面规则的限制，红黑树最长路径一定不会超过最短路径两倍，也就维持了高度的相对平衡。
结合3、4来看下面的两条路径：
最长：黑、红、黑、红、黑、红…………
最短：黑、黑、黑…………



3.红黑树的插入

3.1关于新插入节点的颜色

对于新插入节点，我们设置为红色，原因是红黑树每条路径都必须包含相同数量的黑色节点（性质4），新插入红节点不一定破坏红黑树的结构，新插入黑色节点一定不符合性质4而且很难调整。
数据结构：红黑树讲解（C++）,高阶数据结构,数据结构,c++,学习,笔记,经验分享


3.2节点的定义

//用枚举来定义颜色
enum Color
{
	RED,
	BLACK
};

//这里直接实现key_value模型
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;  //涉及到旋转，多加父亲指针来简化操作
	pair<K, V> _kv;  //存储键值对
	Color _col; //颜色
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(RED)  //新节点颜色为红色
	{}
};

3.3插入新节点

这里比较简单，按二叉搜索树的规则插入即可：

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 (kv.first > cur->_kv.first) //待插入节点在右子树
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)  //待插入节点在左子树
		{
			parent = cur;
			cur = cur->_left;
		}
		else  //相同
		{
			return false;
		}
	}
	cur = new Node(kv);
	if (kv.first > parent->_kv.first) //新节点在父亲右子树
	{
		parent->_right = cur;
	}
	else  //新节点在父亲左子树
	{
		parent->_left = cur;
	}
	cur->_parent = parent;  //记得更新父亲指针
	
	/// 变色旋转维持红黑树结构（暂时省略）  //
	
	_root->_col = BLACK; //可能改变根部颜色，保持根部为黑色
	return true;
}

3.4判断插入后是否需要调整

其实红黑树插入后只需要看当前节点和父亲的颜色即可，其中新节点一定为红。

  1. 父亲为黑，符合规则，不需要调整。
  2. 父亲为红，此时出现红红的连续节点，需要进行调整。

3.5插入后维持红黑树结构（重点）

为了方便叙述，我们做如下定义：

  1. cur表示当前节点
  2. p表示cur父亲节点
  3. u表示叔叔节点
  4. g表示祖父(p和u的父亲)节点
3.5.1cur、p、u为红，g为黑

数据结构：红黑树讲解（C++）,高阶数据结构,数据结构,c++,学习,笔记,经验分享
代码：

while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束
{
	Node* granderfather = parent->_parent;  //祖父
	//需要对叔叔进行操作，需要判断叔叔是祖父的左还是右
	if (parent == granderfather->_left)  //父亲是祖父的左子树
	{
		Node* uncle = granderfather->_right;
		if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可
		{
			uncle->_col = parent->_col = BLACK;
			granderfather->_col = RED; 
			//当前子树可能为部分，继续向上调整
			cur = granderfather;
			parent = cur->_parent;
		}
		else  //叔叔为空或为黑色
		{ 
			//先省略
		}
	}
	else  //父亲是祖父的右子树
	{
		Node* uncle = granderfather->_left;
		if (uncle && uncle->_col == RED)  //叔叔不空并且为红
		{
			parent->_col = uncle->_col = BLACK;
			granderfather->_col = RED;  
			//当前可能为部分子树，需要继续上调
			cur = granderfather;
			parent = cur->_parent;
		}
		else  //叔叔为空或为黑色
		{
			// 先省略
		}
	}
}

3.5.2cur、p为红，g为黑，u为空/u存在为黑

下面是一会要用到的旋转接口：

void RotateL(Node* parent)  //左单旋,rotate->旋转
{
	Node* SubR = parent->_right;
	Node* SubRL = SubR->_left;  //这个有可能为空
	Node* ppnode = parent->_parent;  //原来父亲的父亲

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

	SubR->_left = parent;
	parent->_parent = SubR;

	if (ppnode == nullptr)  //旋转的是整颗树
	{
		_root = SubR;
		SubR->_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;  //这个有可能为空
	Node* ppnode = parent->_parent;

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

	SubL->_right = parent;
	parent->_parent = SubL;

	if (ppnode == nullptr)  //旋转的是整颗树
	{
		_root = SubL;
		SubL->_parent = nullptr;
	}
	else  //旋转部分
	{
		if (ppnode->_left == parent)  //是左子树
		{
			ppnode->_left = SubL;
		}
		else  //右子树
		{
			ppnode->_right = SubL;
		}
		SubL->_parent = ppnode;
	}
}

涉及旋转情况比较复杂，分开讨论：

（1）p为g的左孩子，cur为p的左孩子
数据结构：红黑树讲解（C++）,高阶数据结构,数据结构,c++,学习,笔记,经验分享


（2）p为g的左孩子，cur为p的右孩子

数据结构：红黑树讲解（C++）,高阶数据结构,数据结构,c++,学习,笔记,经验分享


（3）p为g的右孩子，cur为p的右孩子

数据结构：红黑树讲解（C++）,高阶数据结构,数据结构,c++,学习,笔记,经验分享


（4）p为g的右孩子，cur为p的左孩子

数据结构：红黑树讲解（C++）,高阶数据结构,数据结构,c++,学习,笔记,经验分享

整合一下（1、2、3、4）得到下面的调整代码：

//到这里插入新节点的工作完成，下面进行结构调整：
while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束
{
	Node* granderfather = parent->_parent;  //祖父
	if (parent == granderfather->_left)  //父亲是祖父的左子树，p为g的左孩子
	{
		Node* uncle = granderfather->_right;
		if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可
		{
			uncle->_col = parent->_col = BLACK;
			granderfather->_col = RED; 
			//当前子树可能为部分，继续向上调整
			cur = granderfather;
			parent = cur->_parent;
		}
		else  //叔叔为空或为黑色
		{ 
			//     g
			//   p   u
			// c
			if (cur == parent->_left)  //当前为父亲的左子树，cur为p的左孩子
			{
				RotateR(granderfather);
				granderfather->_col = RED;
				parent->_col = BLACK;
			}
			else   //当前为父亲的右子树，cur为p的右孩子
			{
				//    g
				//  p   u
				//    c
				//左右双旋
				RotateL(parent);
				RotateR(granderfather);
				granderfather->_col = RED;
				cur->_col = BLACK;
			}
			break;  //这两种情况调整完可以结束
		}
	}
	else  //父亲是祖父的右子树，p为g的右孩子
	{
		Node* uncle = granderfather->_left;
		if (uncle && uncle->_col == RED)  //叔叔不空并且为红
		{
			parent->_col = uncle->_col = BLACK;
			granderfather->_col = RED;  
			//当前可能为部分子树，需要继续上调
			cur = granderfather;
			parent = cur->_parent;
		}
		else  //叔叔为空或为黑色
		{
			if (cur == parent->_right)  //当前为父亲的右，cur为p的右孩子
			{
				//    g
				//  u   p
				//        c
				//左旋
				RotateL(granderfather);
				parent->_col = BLACK;
				granderfather->_col = RED;
			}
			else  //当前为父亲的左，cur为p的左孩子
			{
				//   g
				// u   p
				//   c
				//右左双旋
				RotateR(parent);
				RotateL(granderfather);
				cur->_col = BLACK;
				granderfather->_col = RED;	
			}
			break;  //这两种情况调整完可以结束
		}
	}
}
_root->_col = BLACK; //保持根部为黑色



4.一些简单的测试接口

void InOrder()   //中序遍历，验证是否为二叉搜索树
{
	_InOrder(_root);
	cout << endl;
}

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

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

// 根节点->当前节点这条路径的黑色节点的数量
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);
}

bool IsBalance()
{
	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);
}



文章来源地址https://www.toymoban.com/news/detail-752363.html

5.完整代码

#pragma once
#include <iostream>
#include <utility>
using namespace std;

//用枚举来定义颜色
enum Color
{
	RED,
	BLACK
};

//这里直接实现key_value模型
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;  //涉及到旋转，多加父亲指针来简化操作
	pair<K, V> _kv;  //存储键值对
	Color _col; //颜色
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(RED)  //新节点颜色为红色
	{}
};

template<class K, class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;

	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 (kv.first > cur->_kv.first) //待插入节点在右子树
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)  //待插入节点在左子树
			{
				parent = cur;
				cur = cur->_left;
			}
			else  //相同
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first > parent->_kv.first) //在右子树
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束
		{
			Node* granderfather = parent->_parent;  //祖父
			if (parent == granderfather->_left)  //父亲是祖父的左子树
			{
				Node* uncle = granderfather->_right;
				if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可
				{
					uncle->_col = parent->_col = BLACK;
					granderfather->_col = RED; 
					//当前子树可能为部分，继续向上调整
					cur = granderfather;
					parent = cur->_parent;
				}
				else  //叔叔为空或为黑色
				{ 
					//     g
					//   p   u
					// c
					if (cur == parent->_left)  //当前为父亲的左子树
					{
						RotateR(granderfather);
						granderfather->_col = RED;
						parent->_col = BLACK;
					}
					else   //当前为父亲的右子树
					{
						//    g
						//  p   u
						//    c
						//左右双旋
						RotateL(parent);
						RotateR(granderfather);
						granderfather->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}
			}
			else  //父亲是祖父的右子树
			{
				Node* uncle = granderfather->_left;
				if (uncle && uncle->_col == RED)  //叔叔不空并且为红
				{
					parent->_col = uncle->_col = BLACK;
					granderfather->_col = RED;  
					//当前可能为部分子树，需要继续上调
					cur = granderfather;
					parent = cur->_parent;
				}
				else  //叔叔为空或为黑色
				{
					if (cur == parent->_right)  //当前为父亲的右
					{
						//    g
						//  u   p
						//        c
						//左旋
						RotateL(granderfather);
						parent->_col = BLACK;
						granderfather->_col = RED;
					}
					else  //当前为父亲的左
					{

						//   g
						// u   p
						//   c
						//右左双旋
						RotateR(parent);
						RotateL(granderfather);
						cur->_col = BLACK;
						granderfather->_col = RED;	
					}
					break;
				}
			}
		}
		_root->_col = BLACK; //保持根部为黑色
		return true;
	}


/// //
/// /
/// 	测试代码
	 
	void InOrder()   //中序遍历，验证是否为二叉搜索树
	{
		_InOrder(_root);
		cout << endl;
	}

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

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

	// 根节点->当前节点这条路径的黑色节点的数量
	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);
	}

	bool IsBalance()
	{
		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);
	}


	int Height()
	{
		return _Height(_root);
	}

	int _Height(Node* root)  //求高度的
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}


	Node* Find(K key)
	{
		return _Find(key, _root);
	}

	Node* _Find(K key, Node* root)
	{
		if (root == nullptr)
			return nullptr;
		if (key > root->_kv.first) //在右子树
		{
			return _Find(key, root->_right);
		}
		else if (key < root->_kv.first) //在左子树
		{
			return _Find(key, root->_left);
		}
		else  //找到了
		{
			return root;
		}
	}

private:
	Node* _root = nullptr;

	void RotateL(Node* parent)  //左单旋,rotate->旋转
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;  //这个有可能为空
		Node* ppnode = parent->_parent;  //原来父亲的父亲

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

		SubR->_left = parent;
		parent->_parent = SubR;

		if (ppnode == nullptr)  //旋转的是整颗树
		{
			_root = SubR;
			SubR->_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;  //这个有可能为空
		Node* ppnode = parent->_parent;

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

		SubL->_right = parent;
		parent->_parent = SubL;

		if (ppnode == nullptr)  //旋转的是整颗树
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else  //旋转部分
		{
			if (ppnode->_left == parent)  //是左子树
			{
				ppnode->_left = SubL;
			}
			else  //右子树
			{
				ppnode->_right = SubL;
			}
			SubL->_parent = ppnode;
		}
	}
};

到了这里，关于数据结构：红黑树讲解（C++）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】—红黑树（C++实现）

    【数据结构】—红黑树（C++实现）

                                                            🎬 慕斯主页 ： 修仙—别有洞天                                                  💜 本文前置知识：  AVL树                                                       ♈️ 今日夜电波 ：

    2024年02月05日
    浏览(48)
  • 【数据结构】红黑树（C++实现）

    【数据结构】红黑树（C++实现）

    👀 樊梓慕： 个人主页  🎥 个人专栏： 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子，都是对生命的辜负 目录 前言 1.概念 2.性质 3.节点的定义  4.插入 4.1情况1：叔叔u存在且为红 4.2情况2：

    2024年03月13日
    浏览(52)
  • [数据结构 - C++] 红黑树RBTree

    [数据结构 - C++] 红黑树RBTree

    我们在学习了二叉搜索树后，在它的基础上又学习了AVL树，知道了AVL树是靠平衡因子来调节左右高度差，从而让树变得平衡的。本篇我们再来学习一个依靠另一种平衡规则来控制的二叉搜索树——红黑树。 红黑树 ，是一种 二叉搜索树 ， 但在每个结点上增加一个存储位表示

    2024年01月23日
    浏览(43)
  • 【C++高阶(四)】红黑树深度剖析--手撕红黑树!

    【C++高阶(四)】红黑树深度剖析--手撕红黑树!

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 如果说发明AVL树的人是天才,那么 发明红黑树的人可以称为天才中的 精英!为什么AVL树这么强大但是没啥 人用呢?就是因为红黑树比你还好

    2024年02月05日
    浏览(44)
  • 【数据结构-树】红黑树

    【数据结构-树】红黑树

    💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(42)
  • 数据结构 | 红黑树

    数据结构 | 红黑树

    节点的左边比节点的值小，右边比节点的值大。 节点要么是 红色 ，要么是 黑色 根节点 是黑色 叶子节点都是黑色的空节点 红黑树中红色节点的子节点都是黑色 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点 在添加或者删除节点的时候，如果不满足这些性质会

    2024年01月21日
    浏览(41)
  • 数据结构——红黑树

    数据结构——红黑树

    目录 概念 性质 结点的定义  插入 调整 当p是g的左孩子时 当p为g的右孩子时 插入完整代码 红黑树的检测 红黑树完整代码（包括测试数据）   红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或BLACK。 通过对任何一条从根到叶子的路径

    2023年04月09日
    浏览(42)
  • [数据结构]-红黑树

    [数据结构]-红黑树

    前言 作者 ： 小蜗牛向前冲 名言： 我可以接受失败，但我不能接受放弃   如果觉的博主的文章还不错的话，还请 点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、红黑树的基本知识  1、红黑树的概念 2、性质  二、红黑树的模拟实

    2024年02月04日
    浏览(44)
  • 【数据结构】红黑树

    【数据结构】红黑树

    🐱作者：一只大喵咪1201 🐱专栏：《数据结构与算法》 🔥格言： 你只管努力，剩下的交给时间！ 在学习AVL树的时候，我们知道，当修改AVL树的结构(插入，删除)时，会通过旋转来保证平衡因子不超过1，所以频繁的修改结构会导致效率低下，今天我们学习的红黑树就完美解

    2023年04月17日
    浏览(46)
  • 红黑树数据结构

    红黑树数据结构

    现在JAVASE中HashMap中底层源码是由数组+链表+红黑树进行设计的，然后很多地方也是用到红黑树，这里单独对红黑树数据结构进行简单的介绍。 目录 红黑树概念 红黑树的性质 自平衡规则 代码   红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可

    2024年02月01日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包