数据结构——红黑树详解

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

一、红黑树的定义

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。(说它是接近平衡因为它并没有像AVL树的平衡因子的概念,它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构,进而提升整体的性能)

数据结构——红黑树详解,数据结构,c++

 红黑树的性质:

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

2. 根节点是黑色的

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

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

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。

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

由性质4可知,红黑树的根节点到其叶子结点的所有路径上黑色节点的个数相同,那么一条路径上如果没有红色节点,则该路径为最短路径。

由性质3可知,红黑树的红色节点不连续,那么在一条路径上间隔插入红色节点,则该路径为最长路径。

得出结论:最短路径为全黑色节点,最长路径为一黑一红节点。所以,最长路径中节点个数不会超过最短路径节点个数的两倍。最短路径和最长路径可能在一颗红黑树上并不存在,如上图中就不存在最短路径。

二、红黑树的基本操作实现

红黑树同样是二叉查找树的演变,因此红黑树和AVL树一样,查找、遍历操作基本和二叉查找树一样。而红黑树的插入和删除操作与AVL树相比,需要对节点的颜色进行调整,也使用了旋转操作

红黑树节点定义:

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

红黑树节点的结构与AVL树节点类似,这里用节点的颜色来替换平衡因子。

2.1 红黑树的插入操作

插入中需要用到的节点概念:

  • parent:父亲节点
  • uncle:叔叔节点( parent 的兄弟节点)
  • grand:祖父节点( parent 的父节点)

红黑树的节点有颜色之分,那么新插入节点的颜色是红色还是黑色呢?

当插入节点的颜色是黑色,新节点所在路径上的黑色节点个数+1。要保持每条路径上黑色节点个数相同,需要对其他路径一一调整,这样操作是非常繁琐的。

当插入节点的颜色是红色,所有路径上的黑色节点个数均不变。当新节点的父亲是黑色时,插入新节点,依然符合红黑树性质,无需调整。当新节点的父亲是红色时,进行调整。

得出结论:新插入节点默认颜色为红色。

2.1.1 叔叔节点(uncle)存在且为红

新插入节点cur的父亲为黑,插入后依然符合红黑树性质,无需调整。新插入节点cur的父亲为红,并且爷爷节点(grandparent)为黑(红黑树的红色节点不连续),叔叔节点(uncle)存在且为红。

数据结构——红黑树详解,数据结构,c++

此时对该子树进行操作,将parent节点变为黑色,grandparent节点变为红色,这样就能保证该子树中每条路径中黑色节点相同,并且没有连续的红色节点。然后更新cur、parent节点,parent = cur->_parent,cur=grandparent,沿插入路径向上调整,直到该树中没有连续的红节点。如下图所示:

数据结构——红黑树详解,数据结构,c++

2.1.2 叔叔节点(uncle)不存在或存在且为黑

新插入节点cur的父亲为红,并且爷爷节点(grandparent)为黑(红黑树的红色节点不连续),叔叔节点(uncle)不存在或存在且为黑。

数据结构——红黑树详解,数据结构,c++

在插入cur节点前,该树各路径上黑色节点个数已经不同,不满足红黑树的性质。说明cur节点不是新插入的节点,且cur以前是黑色节点,经过第一种情况的颜色调整后,cur节点变为红色。此时需要旋转操作,并更改颜色。这里不对旋转做详细叙述,参考数据结构——AVL树详解-CSDN博客。

右单旋:当parent节点时grandparent节点的右孩子,且cur节点是parent节点的右孩子

数据结构——红黑树详解,数据结构,c++

旋转后将grandparent节点变为红色,parent变为黑色。

右单旋:当parent节点时grandparent节点的左孩子,且cur节点是parent节点的左孩子

数据结构——红黑树详解,数据结构,c++

旋转后将grandparent节点变为红色,parent变为黑色。

左右双旋:当parent节点时grandparent节点的左孩子,且cur节点是parent节点的右孩子

数据结构——红黑树详解,数据结构,c++

旋转后将grandparent节点变为红色,cur变为黑色。 

右左双旋:当parent节点时grandparent节点的右孩子,且cur节点是parent节点的左孩子

数据结构——红黑树详解,数据结构,c++

旋转后将grandparent节点变为红色,cur变为黑色。  

插入代码实现具体实现如下:

bool Insert(const pair<k, v>& kv)
	{
		if (_root == nullptr) {
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (cur->_kv.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv); // 在cur位置插入红色节点
		if (parent->_kv.first < kv.first) {//连接cur节点到红黑树
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//1:当叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}

				else
				{
					//2:叔叔不存在或者存在且为黑,由第一种情况调整而来
					//旋转+变色
					if (cur == parent->_left)
					{
						//     g
						//   p    u
						// c
						//此时路径上黑色节点不相同,且有连续的红色节点,不满足最长路径是最短路径的两倍
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else {
						//     g
						//   p    u
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}

			}
			else
			{
				Node* uncle = grandfather->_left;
				// 情况一:叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}

				else
				{
					// 情况二:叔叔不存在或者存在且为黑
					// 旋转+变色
					//      g
					//   u     p
					//            c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}

					else {
						//      g
						//   u     p
						//       c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

三、红黑树的验证

红黑树的检测分为两步:

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

2. 检测其是否满足红黑树的性质:根节点是否为黑色,各路径黑色节点个数是否相同,红色节点是否连续出现。

bool IsBalance()
	{
		if (_root && _root->_col == RED)
			return false;

		int refBlackNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				refBlackNum++;

			cur = cur->_left;
		}

		return Check(_root, 0, refBlackNum);
	}

先判断根节点,根节点为空或者根节点为红色,直接返回false。按照中序遍历,找到最左路径,遇到黑色节点refBlackNum++,最后得到最左路径的黑色节点个数。调用Check函数,传入根节点和refBlackNum。

bool Check(Node* cur, int blackNum, int refBlackNum)
	{//传blackNum,每次走到黑色节点++,为nullptr回到上一层调用走右子树,此时blackNum还是上一层的值
		if (cur == nullptr) {
			if (refBlackNum != blackNum) {
				cout << "黑色节点的数量不相等" << endl;
				return false;
			}
			return true;
		
	}
	if (cur->_col == RED && cur->_parent->_col == RED) {
		cout << "存在连续的红色节点" << endl;
		return false;
	}
	if (cur->_col == BLACK)
		++blackNum;

	return Check(cur->_left, blackNum, refBlackNum) && Check(cur->_right, blackNum, refBlackNum);
}

cur==nullptr,说明当前路径已走完,判断这条路径黑色节点个数blackNum是否和refBlackNum(标准值)是否相等。不为空时,判断当前节点是否为红色,如果cur为红色,再判断其父亲是否为红色(&&避免判断根节点的parent)。如果是黑色节点,blackNum++,最后递归左子树与右子树。blackNum为传值,每次遇到黑色节点++,为nullptr回到上一层调用遍历右子树,此时blackNum还是上一层的值文章来源地址https://www.toymoban.com/news/detail-849599.html

四、红黑树的模拟实现

#define  _CRT_SECURE_NO_WARNINGS
#pragma once
#include<vector>
#include<iostream>
#include<time.h>
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* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (cur->_kv.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv); // 在cur位置插入红色节点
		if (parent->_kv.first < kv.first) {//连接cur节点到红黑树
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//1:当叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}

				else
				{
					//2:叔叔不存在或者存在且为黑,由第一种情况调整而来
					//旋转+变色
					if (cur == parent->_left)
					{
						//     g
						//   p    u
						// c
						//此时路径上黑色节点不相同,且有连续的红色节点,不满足最长路径是最短路径的两倍
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else {
						//     g
						//   p    u
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}

			}
			else
			{
				Node* uncle = grandfather->_left;
				// 情况一:叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}

				else
				{
					// 情况二:叔叔不存在或者存在且为黑
					// 旋转+变色
					//      g
					//   u     p
					//            c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}

					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)//左单旋
	{
		++rotateSize;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL) {
			subRL->_parent = parent;
		}
		subR->_left = parent;
		Node* ppnode = parent->_parent;//记录parent的父节点
		parent->_parent = subR;
		if (parent == _root)//考虑parent是该树的根节点
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
	}



	void RotateR(Node* parent)//右单旋
	{
		++rotateSize;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR) {
			subLR->_parent = parent;
		}
		subL->_right = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subL;
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}

	size_t Size()
	{
		return _Size(_root);
	}

	size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;

		return _Size(root->_left)
			+ _Size(root->_right) + 1;
	}

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

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

	void InOrder()
	{
		_InOrder(_root);
	}

	int GetRotateSize()
	{
		return rotateSize;
	}

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

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

	Node* Find(const k& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return NULL;
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
			return false;

		int refBlackNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				refBlackNum++;

			cur = cur->_left;
		}

		return Check(_root, 0, refBlackNum);
	}

	bool Check(Node* cur, int blackNum, int refBlackNum)
	{//传blackNum,每次走到黑色节点++,为nullptr回到上一层调用走右子树,此时blackNum还是上一层的值
		if (cur == nullptr) {
			if (refBlackNum != blackNum) {
				cout << "黑色节点的数量不相等" << endl;
				return false;
			}
			return true;
		
	}
	if (cur->_col == RED && cur->_parent->_col == RED) {
		cout << "存在连续的红色节点" << endl;
		return false;
	}
	if (cur->_col == BLACK)
		++blackNum;

	return Check(cur->_left, blackNum, refBlackNum) && Check(cur->_right, blackNum, refBlackNum);
}
	private:
		Node* _root = nullptr;
		int rotateSize = 0;
	
};

五、红黑树和AVL树的比较

  1. AVL树的时间复杂度虽然优于红黑树,但是对于现在的计算机,cpu太快,可以忽略性能差异。
  2. 红黑树的插入删除比AVL树更便于控制操作。
  3. 红黑树整体性能略优于AVL树(红黑树旋转情况少于AVL树)。

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

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

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

相关文章

  • 数据结构 | 红黑树

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

    2024年01月21日
    浏览(44)
  • [数据结构]-红黑树

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

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

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

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

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

    2023年04月09日
    浏览(46)
  • 【数据结构-树】红黑树

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

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

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

    2024年02月01日
    浏览(40)
  • C++数据结构--红黑树

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

    2024年02月09日
    浏览(49)
  • 数据结构入门-11-红黑树

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

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

    数据结构可视化演示链接,也就是图片演示的网址 数据结构之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

领取红包

二维码2

领红包