后台-插件-广告管理-内容页广告位一(手机)

您现在的位置是:首页 > 新兴行业 > 云计算云计算

红黑树特性和实现详解——C++进阶数据结构

2021-06-07 21:00:43云计算人已围观

简介1.红黑树的概念红黑树是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。2.红黑树的性质每个结点不是红色就是黑色根结点是黑色的如果一个结点是红色的,则它的两个孩子结点是黑色的对于每个结点,每条路径上都有相同数量的黑结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点,上图的NIL结点)思考:为什么满足上面的性质,红黑树就能保证:

文章目录

    • 1.红黑树的概念
    • 2.红黑树的性质
    • 3.与AVL树进行效率比较
    • 4.红黑树结点的定义
    • 5.红黑树的插入
    • 5.1.cur为红,p为红,u存在且为红
    • 5.2 cur为红,p为红,u不存在或者存在且为黑色
      • 5.2.1直线情况:单旋处理
      • 5.2.2曲线情况:双旋处理
      • 5.2.3 小结
    • 代码实现

1.红黑树的概念

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

2.红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根结点是黑色的
  3. 如果一个结点是红色的,则它的两个孩子结点是黑色的
  4. 对于每个结点,每条路径上都有相同数量的黑结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点,上图的NIL结点)

思考一个问题:为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?
在这里插入图片描述

3.与AVL树进行效率比较

设红黑树的黑色节点数为x个,任意一颗红黑树中,总结点的个数N为[x,2x],即查找的效率为 logN~log2N -> logN~log2N 即O(logN)

但是在底层实现之中,AVL是严格的平衡二叉树,红黑树只是近似平衡二叉树,即AVL树要进行更多的旋转操作,因此红黑树的性能更优于AVL树。我们常用的set和map在底层用的就是红黑树。

4.红黑树结点的定义

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;

	enum Colour _col;

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

5.红黑树的插入

因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不
需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:

约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点

5.1.cur为红,p为红,u存在且为红

在这里插入图片描述

5.2 cur为红,p为红,u不存在或者存在且为黑色

在这里插入图片描述
在这里插入图片描述

5.2.1直线情况:单旋处理

在这里插入图片描述

5.2.2曲线情况:双旋处理

在这里插入图片描述

5.2.3 小结

由上述分析可知,红黑树的构建主要分为如下情况:

  1. 父亲节点为黑色,插入的节点为红色,不需要进行操作

  2. 父亲节点和叔叔节点为红色,插入一个红色的节点后,父亲节点和叔叔节点变为黑色,祖父节点变为红色

  3. 父亲节点为红色、叔叔节点不存在或者为黑色:

  • parent在grandfather左侧时:
    cur在parent左侧 -> 以g为中心,进行右旋,并且g变为红色,p变为黑色(右旋)
    cur在parent右侧 -> 先以p为中心进行左旋,再以g为中心进行右旋(左右双旋)

  • parent在grandfather右侧时:
    cur在parent右侧 -> 以g为中心,进行左旋,并且g变为红色,p变为黑色(左旋)
    cur在parent左侧 -> 先以p为中心进行右旋,再以g为中心进行左旋(右左双旋)

代码实现

#pragma once

#include <iostream>
#include <vector>
#include <assert.h>
#include <math.h>

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;

	enum Colour _col;

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

template<class K, class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);

			_root->_col = BLACK;//根结点是黑色
			return make_pair(_root, 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 make_pair(cur, false);
			}
		}

		cur = new Node(kv); //此时进行节点的插入 RED

		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		Node* newnode = cur;保存一份,返回用

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;//祖父

			if (grandfather->_left == parent)//判断左子树还是右子树
			{
				Node* uncle = grandfather->_right;
				// 情况1:u存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else //  情况2+3:u不存在或存在且为黑
				{
					//        g
					//      p
					//   c
					//
					if (cur == parent->_left)  // 
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//        g
						//      p
						//         c
						//
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // grandfather->_right == parent 
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else //  情况2+3:u不存在或存在且为黑
				{
					//  g
					//		p
					//			c
					//
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						//   g
						//       p
						//   c
						//
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}


		_root->_col = BLACK;
		return make_pair(newnode, true);
	}


	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		};
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		subR->_left = parent;

		Node* parentParent = parent->_parent;
		parent->_parent = subR;

		if (_root == parent)
		{
			_root = subR;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
		}

		subR->_parent = parentParent;
	}

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

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

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

	bool _CheckRedCol(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		if (root->_col == RED)
		{
			Node* parent = root->_parent;
			if (parent->_col == RED)
			{
				cout << "违反规则2:存在连续的红色节点" << endl;
				return false;
			}
		}

		return _CheckRedCol(root->_left) && _CheckRedCol(root->_right);
	}

	bool _CheckBlackNum(Node* root, int blackNum, int trueNum)
	{
		if (root == nullptr)
		{
			// 当走到NULL时, blackNum 这条路径黑色节点的数量
			return trueNum == blackNum;
		}

		if (root->_col == BLACK)
		{
			blackNum++;
		}

		return  _CheckBlackNum(root->_left, blackNum, trueNum)
			&& _CheckBlackNum(root->_right, blackNum, trueNum);
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "违反规则1:根节点是红色的" << endl;
			return false;
		}

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

		int blackNum = 0;
		return _CheckRedCol(_root) && _CheckBlackNum(_root, blackNum, trueNum);
	}

private:
	Node* _root = nullptr;
};

文章来源:https://blog.csdn.net/weixin_50843868/article/details/117597996

Tags:数据结构 二叉树 

很赞哦! ()

上一篇:钉钉APP配置自动告警

下一篇:返回列表

后台-插件-广告管理-内容页广告位二(手机)

相关文章

后台-插件-广告管理-内容页广告位三(手机)

随机图文

后台-插件-广告管理-内容页广告位四(手机)

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计60260篇文章
  • 浏览统计4607次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们