数据结构——红黑树详解

admin2024-04-03  0

一、红黑树的定义

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

数据结构——红黑树详解,第1张

 红黑树的性质:

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)存在且为红。

数据结构——红黑树详解,第2张

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

数据结构——红黑树详解,第3张

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

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

数据结构——红黑树详解,第4张

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

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

数据结构——红黑树详解,第5张

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

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

数据结构——红黑树详解,第6张

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

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

数据结构——红黑树详解,第7张

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

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

数据结构——红黑树详解,第8张

旋转后将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还是上一层的值

四、红黑树的模拟实现

#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树)。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!