【C++】红黑树的概念与模拟实现

这篇具有很好参考价值的文章主要介绍了【C++】红黑树的概念与模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

红黑树的概念

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

红黑树的性质

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

红黑树节点的定义

enum Color
{
	RED, BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;
	Color _color;

	RBTreeNode(const T& data = T(), Color color = RED)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_color(color)
	{}
};

红黑树的迭代器

首先我们来看下红黑树中的迭代器应该是在什么位置
【C++】红黑树的概念与模拟实现

红黑树的结构中,有一个根节点,也有一个头节点,头节点是不负责存储数据的,而根节点才是常规意义上的二叉树的根节点,而红黑树中,begin()在头节点的左子树,也就是最左侧的节点(因为红黑树也是二叉平衡树),最左侧的节点就是最小的节点,end()在头节点的位置,因为如果对end()减减时,需要让迭代器走到最后一个节点的位置,也就意味着end应该指向最后一个节点的下一个位置。

首先,不关注红黑树节点中的值,因为作为迭代器,并不会对红黑树的结构进行修改,也就不会破坏红黑树,所以可以忽略红黑树的性质,只去关注它作为一棵二叉平衡树的特点。

核心的代码就变成了如何对迭代器实现Increment和Decrement操作,也就是加加减减操作

红黑树的插入

红黑树的插入实际上是分两个步骤的: 第一步,先用插入二叉搜索树的方式进行插入: 先拿到当前树的根节点,判断当前树是否为空
1.若为空,则创建一个根节点,作为头节点的parent,根节点和头节点互为parent
2.若不为空,从根节点开始,找待插入的节点位置
3.找到插入位置后,插入节点(默认的插入颜色是红色)
4.需要检测插入节点后,红黑树的性质是否被破坏了
5.检测完毕,并且进行修改
6.修改根节点的颜色,并且修改头节点的左右指向

对于步骤4是最重要的一步,因为涉及到红黑树的性质被破坏后,如何进行修改
我们可以分几种情况来进行讨论:
注意:cur为当前节点,p为父节点, g为祖父节点,u为叔叔节点

情况1.cur为红,p为红,g为黑,u存在且为红

【C++】红黑树的概念与模拟实现

那么就需要将p和u的颜色改为黑,同时将g的颜色改为红。
1.这时候就需要看g是否是根节点了,如果是根节点,只需要将根节点修改为黑即可。
2.如果g不是根节点,那么就需要继续向上判断,如果g的双亲是黑,也不需要进行任何修改,但是如果g的双亲是红,就违反了性质3,需要继续向上修改----->相当于将g作为cur,继续向上调整

情况2.cur为红,p为红,g为黑,u不存在/u存在且为黑

对于第一种:u不存在的情况
【C++】红黑树的概念与模拟实现

可以推断出,cur一定是新插入的节点,因为如果cur不是新插入的节点,那么cur和p一定要有一个是黑色,不然就违反了性质4
对于第二种:u存在的情况
【C++】红黑树的概念与模拟实现
u一定是黑色的,cur节点原来的颜色也是黑色的,现在看到是红色是由于cur的子树在调整时将cur的颜色由黑色改为红色了。

对于这两种场景的解决方案是:
p为g的左孩子,cur为p的左孩子,则进行右单旋;
p为g的右孩子,cur为p的右孩子,则进行左单旋。

旋转完成后,p变黑,g变红。
【C++】红黑树的概念与模拟实现

【C++】红黑树的概念与模拟实现

场景3:cur为红,p为红,g为黑,u不存在/u存在且为黑 和场景2相似,区别在于场景3中cur的位置,
如果p在g的左侧,cur在p的右侧,也就是内侧。
如果p在g的右侧,cur在p的左侧,也就是内侧。

【C++】红黑树的概念与模拟实现

p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;
p为g的右孩子,cur为p的左孩子,则针对p做右单旋转
通过这样的旋转之后,情况3就变成了情况2,再对情况2进行处理

当然,上述的三种情况是指parent在祖父节点的左,还有三种情况是可能在祖父节点的右。和上述的情况刚好相反。

红黑树和AVL树的比较

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

红黑树的模拟实现

#pragma once

#include <iostream>
using namespace std;
#include <functional>


enum Color
{
	RED, BLACK
};


template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Color _color;

	RBTreeNode(const T& data = T(), Color color = RED)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _color(color)
	{}
};

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
public:
	RBTreeIterator(Node* pNode = nullptr)
		: _pNode(pNode)
	{}

	// 具有指针类似的操作
	Ref operator*()
	{
		return _pNode->_data;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	// 能够移动
	Self& operator++()
	{
		Increment();
		return *this;
	}

	Self operator++(int)
	{
		Self temp(*this);
		Increment();
		return temp;
	}

	Self& operator--()
	{
		Decrement();
		return *this;
	}

	Self operator--(int)
	{
		Self temp(*this);
		Decrement();
		return temp;
	}

	// 迭代器可以比较
	bool operator!=(const Self& s)const
	{
		return _pNode != s._pNode;
	}

	bool operator==(const Self& s)const
	{
		return _pNode == s._pNode;
	}

private:
	void Increment()
	{
		if (_pNode->_right)
		{
			_pNode = _pNode->_right;
			while (_pNode->_left)
			{
				_pNode = _pNode->_left;
			}
		}
		else
		{
			Node* parent = _pNode->_parent;
			while (_pNode == parent->_right)
			{
				_pNode = parent;
				parent = _pNode->_parent;
			}

			// 注意特殊情况:根没有右孩子场景
			if(_pNode->_right != parent)
				_pNode = parent;
		}
	}

	void Decrement()
	{
		if (_pNode->_parent->_parent == _pNode && RED == _pNode->_color)
		{
			_pNode = _pNode->_right;
		}
		else if (_pNode->_left)
		{
			_pNode = _pNode->_left;
			while (_pNode->_right)
			{
				_pNode = _pNode->_right;
			}
		}
		else
		{
			Node* parent = _pNode->_parent;
			while (_pNode == parent->_left)
			{
				_pNode = parent;
				parent = _pNode->_parent;
			}

			_pNode = parent;
		}

	}
private:
	Node* _pNode;
};

// 假设:key唯一
template<class T, class KOFD, class Compare = less<T>>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
	typedef RBTreeIterator<T, T&, T*> iterator;

public:
	RBTree()
		: _size(0)
	{
		_head = new Node();
		_head->_left = _head;
		_head->_right = _head;
	}

	~RBTree()
	{
		_DestroyRBTree(GetRoot());
		delete _head;
		_head = nullptr;
	}

	iterator begin()
	{
		return iterator(_head->_left);
	}

	iterator end()
	{
		return iterator(_head);
	}

	pair<iterator, bool> Insert(const T& data)
	{
		// 1. 二叉搜索树
		// 按照二叉搜索树的规则插入新节点
		// 空树
		Node*& root = GetRoot();
		Node* newNode = nullptr;
		if (nullptr == root)
		{
			newNode = root = new Node(data, BLACK);
			root->_parent = _head;
		}
		else
		{
			// 非空:
		// 找待插入节点在红黑树中的位置并保存其双亲
			Node* cur = root;
			Node* parent = _head;
			KOFD kofD;
			while (cur)
			{
				parent = cur;
				if (_com(kofD(data), kofD(cur->_data)))
					cur = cur->_left;
				else if (_com(kofD(cur->_data), kofD(data)))
					cur = cur->_right;
				else
					return make_pair(iterator(cur), false);
			}

			// 插入新节点
			newNode = cur = new Node(data);
			if (_com(kofD(data), kofD(parent->_data)))
				parent->_left = cur;
			else
				parent->_right = cur;
			cur->_parent = parent;


			// 2. 节点添加颜色 + 性质约束平衡性
			// 检测新节点插入后,红黑树的性质是否造到破坏
			while (_head != parent && RED == parent->_color)
			{
				// 违反性质三
				Node* grandFather = parent->_parent;
				if (parent == grandFather->_left)
				{
					// 课件中的三个场景:
					Node* uncle = grandFather->_right;
					if (uncle && RED == uncle->_color)
					{
						// 情况一:叔叔节点存在且为红
						parent->_color = BLACK;
						uncle->_color = BLACK;
						grandFather->_color = RED;
						cur = grandFather;
						parent = cur->_parent;
					}
					else
					{
						// 叔叔节点不存在 || 叔叔节点存在且为黑
						// 情况二和情况三
						if (cur == parent->_right)
						{
							// 情况三
							RotateLeft(parent);
							std::swap(cur, parent);
						}

						// 情况二
						parent->_color = BLACK;
						grandFather->_color = RED;
						RotateRight(grandFather);
					}
				}
				else
				{
					// 课件中三个场景的反情况:
					Node* uncle = grandFather->_left;
					if (uncle && RED == uncle->_color)
					{
						parent->_color = BLACK;
						uncle->_color = BLACK;
						grandFather->_color = RED;
						cur = grandFather;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_left)
						{
							RotateRight(parent);
							std::swap(cur, parent);
						}

						parent->_color = BLACK;
						grandFather->_color = RED;
						RotateLeft(grandFather);
					}
				}
			}
		}

		root->_color = BLACK;
		_head->_left = MostLeft();
		_head->_right = MostRight();
		++_size;
		return make_pair(iterator(newNode), true);
	}

	size_t Size()const
	{
		return _size;
	}

	bool Empty()const
	{
		return 0 == _size;
	}

	void Clear()
	{
		_DestroyRBTree(GetRoot());
		_head->_left = _head;
		_head->_right = _head;
		_size = 0;
	}

	void Swap(RBTree<T, KOFD, Compare>& t)
	{
		std::swap(_head, t._head);
		std::swap(_size, t._size);
		std::swap(_com, t._com);
	}

	void InOrder()
	{
		cout << "中序遍历: ";
		_InOrder(GetRoot());
		cout << endl;
	}

	iterator Find(const T& data)
	{
		Node* cur = GetRoot();
		KOFD kofD;
		while (cur)
		{
			if (_com(kofD(data), kofD(cur->_data)))
				cur = cur->_left;
			else if (_com(kofD(cur->_data), kofD(data)))
				cur = cur->_right;
			else
				return iterator(cur);
		}

		return end();
	}

	bool IsVAlidTree()
	{
		Node* root = GetRoot();
		if (nullptr == root)
			return true;

		if (root->_color == RED)
		{
			cout << "违反性质2:根是红色的" << endl;
			return false;
		}

		// 获取单条路径中黑色节点的个数
		size_t blackCount = 0;
		Node* cur = root;
		while (cur)
		{
			if (BLACK == cur->_color)
				blackCount++;

			cur = cur->_left;
		}

		// 递归检测性质4
		return IsVAlidTree(root, blackCount, 0);
	}

private:
	bool IsVAlidTree(Node* root, const size_t blackCount, size_t pathBlackCount)
	{
		if (nullptr == root)
			return true;

		Node* parent = root->_parent;
		if (parent != _head && 
			(RED == root->_color && RED == parent->_color))
		{
			cout << "违反了性质三:存在连在一起的红色节点!!!" << endl;
			return false;
		}

		if (BLACK == root->_color)
			pathBlackCount++;

		if (nullptr == root->_left && nullptr == root->_right)
		{
			if (pathBlackCount != blackCount)
			{
				cout << "违反了性质4:路径中黑色节点个数不一样!!!" << endl;
				return false;
			}
		}

		return IsVAlidTree(root->_left, blackCount, pathBlackCount) &&
			   IsVAlidTree(root->_right, blackCount, pathBlackCount);
	}
	void RotateLeft(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		// 注意:右单支
		if (subRL)
			subRL = subRL->_parent = parent;

		subR->_left = parent;

		// 更新subR和parent的双亲
		Node* pparent = parent->_parent;
		parent->_parent = subR;
		subR->_parent = pparent;

		// 需要向上考虑pparent
		if (_head == pparent)
			GetRoot() = subR;
		else
		{
			if (parent == pparent->_left)
				pparent->_left = subR;
			else
				pparent->_right = subR;
		}
	}

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

		parent->_left = subLR;
		// 左单支
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		// 更新suL和parent的双亲
		Node* pparent = parent->_parent;
		subL->_parent = pparent;
		parent->_parent = subL;

		// 向上考虑pparent的情况
		if (_head == pparent)
			GetRoot() = subL;
		else
		{
			if (parent == pparent->_left)
				pparent->_left = subL;
			else
				pparent->_right = subL;
		}
	}

	void _DestroyRBTree(Node*& root)
	{
		if (root)
		{
			_DestroyRBTree(root->_left);
			_DestroyRBTree(root->_right);
			delete root;
			root = nullptr;
		}
	}
	void _InOrder(Node* root)
	{
		if (root)
		{
			_InOrder(root->_left);
			cout << root->_data << " ";
			_InOrder(root->_right);
		}
	}

	Node*& GetRoot()
	{
		return _head->_parent;
	}

	Node* MostLeft()
	{
		Node* root = GetRoot();
		if (nullptr == root)
			return _head;

		Node* cur = root;
		while (cur->_left)
		{
			cur = cur->_left;
		}

		return cur;
	}

	Node* MostRight()
	{
		Node* root = GetRoot();
		if (nullptr == root)
			return _head;

		Node* cur = root;
		while (cur->_right)
		{
			cur = cur->_right;
		}

		return cur;
	}


private:
	Node* _head;
	size_t _size;
	Compare _com;
};

到了这里,关于【C++】红黑树的概念与模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【C++】红黑树的原理与实现

      文章目录 一、引言 二、红黑树的概念与性质 2、1 红黑树的概念 2、2 红黑树的性质 三、红黑树的定义与实现 3、1 红黑树的定义 3、2 插入新节点 3、2、1 默认插入红色节点 3、3 插入情况分类 3、3、1 情况一(根据颜色向上调整) 3、3、2 情况二(单次旋转+变色) 3、3、3 情

    2024年02月13日
    浏览(43)
  • 【C++进阶06】红黑树图文详解及C++模拟实现红黑树

    1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点着色方式的限制 红黑

    2024年01月21日
    浏览(45)
  • 数据结构之进阶二叉树(二叉搜索树和AVL树、红黑树的实现)超详细解析,附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧,愈被敲打,愈能发出火花。——伽利略”;本章主要是数据结构 二叉树的进阶知识,若之前没学过二叉树建议看看这篇文章一篇掌握二叉树,本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ,希望能对你有所

    2024年02月04日
    浏览(46)
  • 【C++】详解红黑树并模拟实现

    前言:        上篇文章我们一起学习了AVL树比模拟实现,我们发现AVL树成功地把时间复杂度降低到了O(logN)。但是同时我们不难发现一个问题,在构建AVL树中我们也付出了不小的代价,频繁的旋转操作导致效率变低。为了解决这个问题,我们本章将迎来更为实用的红黑树,他

    2024年02月09日
    浏览(40)
  • 【数据结构】红黑树的删除(抽丝剥茧,带你理清每一种情况)

     红黑树的删除,较AVL树的删除比较抽象,同时也跟红黑树的插入的区别较大,但大体上的思路还是基于普通二叉搜索树的基础上进行讨论的。 浅浅的铺垫一下: 需要清楚普通二叉树的删除,可见AVL树的删除文章开头。 四种旋转的操作(只需操作)得熟记于心,可见AVL树的插

    2024年04月27日
    浏览(32)
  • 【C++】红黑树模拟实现插入功能(包含旋转和变色)

    本篇主要讲解红黑树的模拟实现,实现之后再封装成map和set。 红黑树中所用到的旋转功能均源自我的上一篇博客,本篇中不会再详谈旋转,若对于旋转不了解的同学可以先看看上一篇博客:【C++】AVL树模拟实现插入功能 前一篇的AVL树,是严格平衡的一棵二叉搜索树,也就是

    2024年02月13日
    浏览(52)
  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

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

    2024年02月09日
    浏览(46)
  • 【C++】 使用红黑树模拟实现STL中的map与set

    前面的文章我们学习了红黑树,也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的(而map和set的使用我们前面也学过了)。 既然红黑树我们也学习过了,那这篇文章我们就用红黑树来简单实现一下STL中的map和set,重点是学习它的框架。 上一篇文章我们实现了红黑

    2024年02月12日
    浏览(29)
  • 二叉树、二叉查找树、平衡树和红黑树概念及其性质

      在所有的树结构,基本上都遵循左小右大的原则。本文分享二叉树、二叉查找树、平衡树和红黑树概念及其性质。   二叉树(Binary Tree)是指每个节点最多只有两个分支的树结构(即不存在分支大于 2 的节点),如下图所示:   这是一棵拥有 6 个节点深度为 2(深度

    2024年02月08日
    浏览(36)
  • 数据结构——常见二叉树的分类(完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树)

    专业术语 中文 描述 Root 根节点 一棵树的顶点 Child 孩子结点 一个结点含有的子树的根节点称为该结点的子节点 Leaf 叶子结点 没有孩子的节点 Degree 度 一个节点包含子树的数量 Edge 边 一个节点与另外一个节点的连接 Depth 深度 根节点到这个节点经过边的数量 Height 节点高度 从

    2024年02月03日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包