数据结构篇十:红黑树

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

前言

  红黑树是解决单支树问题的另一种解决方法,它相比较AVL树减少了调整的次数,AVL是一格绝对平衡的树,而红黑树只要求最长路径不超过最短路径的二倍,相比较大大减少了调整次数。在实际中更多的也是使用红黑树,就比如后面的map和set,我们就是以红黑树进行封装的。

1. 红黑树的概念

  红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
数据结构篇十:红黑树,数据结构

2. 红黑树的性质

  1. 每个结点不是红色就是黑色 。
  2. 根节点是黑色的 。
  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的 。
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点 。
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。

思考:为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?

  按照上面的性质,最短路径应该是全为黑色节点,而在每条路径黑色节点数量相同并且不难出现连续红色节点的的情况下,最长路径应该是一红一黑,红黑相间的方式,所以最长路径是不会超过最短路径的二倍的,

3. 红黑树节点的定义

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K,V>* _left;
	RBTreeNode<K,V>* _right;
	RBTreeNode<K,V>* _parent;
	pair<K, V> _kv;

	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};

  思考:在节点的定义中,为什么要将节点的默认颜色给成红色的?

  这是因为有一个性质是要求每条路径的黑色节点数目相同,如果我们将新插入节点的颜色默认给成黑色,就会影响全部路径,那么就会在全局破坏这一性质。而如果我们将节点颜色给成红色,我们可能会破坏不能出现连续的红色节点这一性质,也只是影响了这一条路径,也仅仅只是在局部破坏了红黑树的性质,相比较前一种更容易进行处理。

4. 红黑树的插入

  红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

  1. 按照二叉搜索的树规则插入新节点
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 (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		
		//调整
		…………
		
  • 检测新节点插入后,红黑树的性质是否造到破坏
      因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论。(约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点)

4.1 情况一: cur为红,p为红,g为黑,u存在且为红

  • 情况一: cur为红,p为红,g为黑,u存在且为红

数据结构篇十:红黑树,数据结构
  解决方式:将p,u改为黑,g改为红,然后把g当成cur,继续向上调整

4.2 情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑。

  • 情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑。
    数据结构篇十:红黑树,数据结构

  • p为g的左孩子,cur为p的左孩子,则进行右单旋转。

  • p为g的右孩子,cur为p的右孩子,则进行左单旋转。

  • p、g变色–p变黑,g变红。

4.2.1 u不存在

  光看上面的图有人可能会不理解为什么还需要旋转,我们来单独拿出一个例子:
数据结构篇十:红黑树,数据结构
  当u不存在时,它是违反最长路径超过最短路径的二倍的,因此需要先进行旋转再变色。

4.2.2 u存在且为黑

  先新插入一个节点,目前是情况一,直接变色处理就可以了。
数据结构篇十:红黑树,数据结构
  处理完后就是此时所讲的情况二: cur为红,p为红,g为黑,u存在且为黑。我们发现此时违反了最长路径不能超过最短路径的二倍,因此需要先旋转,再变色。
数据结构篇十:红黑树,数据结构
  此时再回归到我们一开始的图解,上下图结合,也就是cur的孩子就是下图中的a
数据结构篇十:红黑树,数据结构
  这样就可以完美的解决问题了。

4.3 情况三

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

数据结构篇十:红黑树,数据结构

  • p为g的左孩子,cur为p的右孩子,则针对p做左单旋转。
  • p为g的右孩子,cur为p的左孩子,则针对p做右单旋转。
  • 则转换成了情况2。

  情况三的原理与情况二一致,只不过是换成了双旋的问题。(记忆窍门:单旋是的情况是一条直线,双旋的情况是一条折线)。
数据结构篇十:红黑树,数据结构

  情况二就是新插入节点是属于直线的情况,只需要旋转一次,情况三是新插入节点属于折线的情况,需要旋转一次变成情况二,再旋转一次解决问题,实际上也就是双旋。(还有一个记忆敲门:左边高往右边旋,右边高往左边旋)
  更具体的情况大家可以像我讲解情况二那样画出详细的图来理解。
  需要格外注意到最后要将根节点改为黑色, 因为在调整过程中有可能将根节点改为红色
  左右子树的旋转在上一篇AVL树中有纤细的讲解,不懂的小伙伴可以去阅读。

5. 红黑树的验证

  红黑树的检测分为两步:

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)。
  2. 检测其是否满足红黑树的性质。

5.1 检测其是否满足二叉搜索树

  写一个中序遍历就可以了。

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

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

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

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

  最主要的是检验每条路径的黑色节点数目是否一样,是否有连续的红色节点。
  对于检验每条路径的黑色节点数目是否一样,我们可以先遍历一条路径记录黑色节点的数目,再通过递归遍历每条路径记录黑色节点的数目,当遍历到nullptr时说明一条路径遍历完了,再与我们一开始记录的黑色节点数目进行比较,相同就返回true,不同就返回false。(注意:传参时需要传值传递,不能引用传递,否则在统计黑色节点数目时,左子树的黑色节点数目会累加到右子树上
  对于是否有连续的红色节点,在递归时对于一个节点,我们如果是拿这个节点与它的孩子节点比较会很麻烦,因为要比较两个。我们不如换个思路,与该节点的父亲节点比较,如果该节点为红色,它的父亲也为红色,就返回false。

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);
}

6. 红黑树的删除

  红黑树的删除本节不做讲解,有兴趣的小伙伴可参考:《算法导论》或者《STL源码剖析》。

7. 红黑树与AVL树的比较

  红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。

8. 代码实现

8.1 RBTree.h

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

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K,V>* _left;
	RBTreeNode<K,V>* _right;
	RBTreeNode<K,V>* _parent;
	pair<K, V> _kv;

	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	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 (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_col == RED)
		{
			Node* uncle = nullptr;
			Node* grandparent = parent->_parent;

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

			//叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;

				cur = grandparent;
				parent = cur->_parent;
			}
			//叔叔不存在或者存在且为黑
			else
			{
				if (parent == grandparent->_left && cur == parent->_left)
				{
					//右旋
					RotateR(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				else if (parent == grandparent->_left && cur == parent->_right)
				{
					//先左旋,再右旋
					RotateL(parent);
					RotateR(grandparent);
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
				else if (parent == grandparent->_right && cur == parent->_right)
				{
					//左旋
					RotateL(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				else
				{
					//先右旋,再左旋
					RotateR(parent);
					RotateL(grandparent);
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
				break;
			}
		}
		_root->_col = BLACK;
		return true;
	}

	void RotateL(Node* parent)
	{
		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 (parent == _root)
		{
			subR->_parent = nullptr;
			_root = subR;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				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 (parent == _root)
		{
			subL->_parent = nullptr;
			_root = subL;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}


	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);*/

		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);
	}

private:
	Node* _root = nullptr;
};

8.2 Test.cpp

int main()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.insert(make_pair(e, e));
	}
	t.InOrder();

	//cout << t.IsBalance() << endl;

	return 0;
}

int main()
{
	const int N = 1000;
	vector<int> v;
	v.reserve(N);
	//srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	//size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		if (e == 506)
		{
			int i = 0;
		}
		t.insert(make_pair(e, e));
		cout << "insert:" << e << "->" << t.IsBalance() << endl;
	}
	//size_t end2 = clock();

	//cout << "Insert:" << end2 - begin2 << endl;

	cout << t.IsBalance() << endl;
	return 0;
}

9. 总结

  红黑树比AVL树更加复杂一些,关于二叉树这部分的内容我建议还是多多画图来加深自己的理解,忌讳眼高手低。希望大家都能有所收获。
  如果大家发现有什么错误的地方,可以私信或者评论区指出喔。我会继续深入学习C++,希望能与大家共同进步,那么本期就到此结束,让我们下期再见!!觉得不错可以点个赞以示鼓励!!文章来源地址https://www.toymoban.com/news/detail-838811.html

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

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

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——红黑树

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

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

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

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

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

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

    数据结构可视化演示链接,也就是图片演示的网址 数据结构之AVL Tree 数据结构之B树和B+树 数据结构之Radix和Trie 数据结构之二叉搜索树 红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个

    2024年01月17日
    浏览(42)
  • 手写红黑树【数据结构】

    2024-3-30 10:52:57 昨天晚上B站看到的视频 00:00~01:00 以下内容源自《【数据结构】》 仅供学习交流使用 禁止其他平台发布时删除以下此话 本文首次发布于CSDN平台 作者是CSDN@日星月云 博客主页是https://jsss-1.blog.csdn.net 禁止其他平台发布时删除以上此话 我红黑树那么牛,你们凭什

    2024年04月25日
    浏览(33)
  • 【数据结构】红黑树详解

    目录 前言: 红黑树的概念: 红黑树的性质: 红黑树节点的定义: 红黑树的插入: 情况1:cur为红,p为红,g为黑,u存在且为红  情况2:cur为红,p为红,g为黑,u不存在或者u为黑(p和cur都在其父亲节点同一侧) 情况3:cur为红,p为红,g为黑,u不存在或者u为黑(p和cur在其父

    2024年04月14日
    浏览(52)
  • C++数据结构--红黑树

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。如图所示: 每个结点不是红色就是黑色。

    2024年02月09日
    浏览(45)
  • 数据结构--红黑树详解

    红黑树(Red Black Tree)是一种自平衡二叉查找树。它是在 1972 年由 Rudolf Bayer 发明的,当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来,在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 由于其自平衡的特性,保证了最坏情形下在 O(logn) 时间复杂度内完

    2024年02月22日
    浏览(44)
  • 数据结构——红黑树详解

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树 确保没有一条路径会比其他路径长出两倍 ,因而是接近平衡的。(说它是接近平衡因为它并没有像AVL树的

    2024年04月13日
    浏览(37)
  • 数据结构入门-11-红黑树

    史上最负盛名的平衡二叉树–红黑树,但其实就是2-3树的一种实现 也是BST,每一个节点都有颜色 性质 看 后面推导出来的结论 2-3树 :和红黑树是等价的 满足BST的基本性质,但不是一种二叉树 有两种节点: 2-3 绝对平衡:根节点到叶子节点 一定相同 2.3.1 如何维护绝对平衡

    2023年04月17日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包