扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++ STL容器详解之红黑树部分模拟实现
  • 289

0
分享到

C++ STL容器详解之红黑树部分模拟实现

2024-04-02 19:04:59 289人浏览 泡泡鱼
摘要

目录一、红黑树的概念二、红黑树的性质三、红黑树节点的定义四、红黑树结构 五、 红黑树的插入操作六、代码总结一、红黑树的概念 红黑树（Red Black Tree），是在计算机科学中用

一、红黑树的概念

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

二、红黑树的性质

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

2. 根节点是黑色的；

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

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

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

满足上面的性质，红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍。

三、红黑树节点的定义


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

插入时默认为红色节点，因为红色可能会破坏规则3，黑色一定会破坏规则4，所以默认红色。

四、红黑树结构 

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 parent 域指向红黑树的根节点，left域指向红黑树中最小的节点，right域指向红黑树中最大的节点，如下:

五、 红黑树的插入操作

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

1. 按照二叉搜索的树规则插入新节点：


	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->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}
 
		Node* newNode = new Node(kv);
		newNode->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = newNode;
			newNode->_parent = parent;
		}
		else
		{
			parent->_right = newNode;
			newNode->_parent = parent;
		}
		cur = newNode;
 
		while (parent && parent->_col == RED)		//违反规则三
		{
 
		}
 
		_root->_col = BLACK;		//插入结束再次将根变为黑
 
		return make_pair(cur, true);
	}

2. 检测新节点插入后，红黑树的性质是否造到破坏

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

cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红

如果g是根节点，调整完成后，需要将g改为黑色，如果g是子树，g一定有父节点，且如果为红色呃，继续向上调整。

将p,u改为黑，g改为红，然后把g当成cur，继续向上调整 。

情况二: cur为红，p为红，g为黑，u不存在/u为黑

u的情况有两种：

1.如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点个数相同。

2.如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

p为g的左孩子，cur为p的左孩子，则进行右单旋转；

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

p变黑，g变红。

情况三: cur为红，p为红，g为黑，u不存在/u为黑

需要进行双旋。

代码实现：


while (parent && parent->_col == RED)		//违反规则三
		{
			Node* grandfather = parent->_parent;
 
			if (parent == grandfather->_left)			//左半边
			{
				Node* uncle = parent->_right;
 
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_left)		//单侧
					{
						RotateR(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateL(parent);
						RotateR(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;		//黑色数量无变化，不需要向上
				}
			}
			else         // parent == grandfather->_right
			{
				Node* uncle = parent->_left;
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_right)		//单侧
					{
						RotateL(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateR(parent);
						RotateL(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;
				}
			}
		}

六、代码


#pragma once
#include<iOStream>
#include<assert.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;
private:
	Node* _root;
 
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentP = parent->_parent;
 
		if (subLR)							//左子树的右子树连接到父的右
			subLR->_parent = parent;
 
		parent->_left = subLR;
		subL->_right = parent;
		parent->_parent = subL;
 
		// 如果parent是根节点，根新指向根节点的指针
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			// 如果parent是子树，可能是其双亲的左子树，也可能是右子树
			if (parentP->_left == parent)
				parentP->_left = subL;
			else
				parentP->_right = subL;
 
			subL->_parent = parentP;
		}
	}
 
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentP = parent->_parent;
 
		if (subRL)
			subRL->_parent = parent;
 
		parent->_right = subRL;
		subR->_left = parent;
		parent->_parent = subR;
 
		// 如果parent是根节点，根新指向根节点的指针
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			// 如果parent是子树，可能是其双亲的左子树，也可能是右子树
			if (parentP->_left == parent)
				parentP->_left = subR;
			else
				parentP->_right = subR;
 
			subR->_parent = parentP;
		}
	}
 
	void _Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
 
		_Destory(root->_left);
		_Destory(root->_right);
 
		delete root;
	}
 
public:
	RBTree()
		:_root(nullptr)
	{}
 
	~RBTree()
	{
		_Destory(_root);
		_root = nullptr;
	}
 
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
 
		return nullptr;
	}
 
	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->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}
 
		Node* newNode = new Node(kv);
		newNode->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = newNode;
			newNode->_parent = parent;
		}
		else
		{
			parent->_right = newNode;
			newNode->_parent = parent;
		}
		cur = newNode;
 
		while (parent && parent->_col == RED)		//违反规则三
		{
			Node* grandfather = parent->_parent;
 
			if (parent == grandfather->_left)			//左半边
			{
				Node* uncle = parent->_right;
 
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_left)		//单侧
					{
						RotateR(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateL(parent);
						RotateR(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;		//黑色数量无变化，不需要向上
				}
			}
			else         // parent == grandfather->_right
			{
				Node* uncle = parent->_left;
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_right)		//单侧
					{
						RotateL(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateR(parent);
						RotateL(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;
				}
			}
		}
 
		_root->_col = BLACK;		//插入结束再次将根变为黑
 
		return make_pair(newNode, true);
	}
};

总结

本文对红黑树进行了介绍，并对构造，插入，查找进行了模拟实现。

以上就是c++ STL容器详解之红黑树部分模拟实现的详细内容，更多关于C++ STL红黑树实现的资料请关注编程网其它相关文章！

--结束END--

本文标题: C++ STL容器详解之红黑树部分模拟实现

本文链接: https://lsjlt.com/news/159367.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C++ STL容器详解之红黑树部分模拟实现
    目录一、红黑树的概念二、红黑树的性质三、红黑树节点的定义四、红黑树结构 五、 红黑树的插入操作六、代码总结一、红黑树的概念 红黑树（Red Black Tree），是在计算机科学中用...
    99+
    2024-04-02
  • C++ STL容器中红黑树部分模拟实现的示例分析
    这篇文章主要介绍了C++ STL容器中红黑树部分模拟实现的示例分析，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。一、红黑树的概念红黑树（Red Black Tree...
    99+
    2023-06-21
  • C++详细实现红黑树流程详解
    目录红黑树的概念红黑树的性质红黑树的定义与树结构插入新增结点插入后维护红黑树性质的主逻辑旋转验证红黑树与AVl树的比较红黑树的应用红黑树的概念 红黑树，是一种二叉搜索树，但在每个结点...
    99+
    2024-04-02
  • 详解C++ STL模拟实现list
    目录list 概述接口总览list 的节点默认成员函数默认构造函数析构函数拷贝构造函数复制赋值函数list 的迭代器构造函数operator==operator!=operator*...
    99+
    2023-01-11
    C++ STL实现list C++ STL list
  • 详解C++STL模拟实现forward_list
    目录forward_list 概述接口总览forward_list 的节点默认成员函数默认构造函数析构函数forward_list 的迭代器构造函数operator==operato...
    99+
    2023-01-13
    C++ STL实现forward_list C++ STL forward_list
  • 利用C++模拟实现STL容器:list
    目录一、list的介绍二、list的排序三、迭代器1、list的迭代器失效问题2、迭代器的功能分类3、list迭代器的模拟实现4、迭代器价值5、迭代器operator->的重载...
    99+
    2022-12-08
    C++实现STL容器list C++ STL容器list C++ STL容器
  • 怎么用C++模拟实现STL容器
    这篇文章主要介绍了怎么用C++模拟实现STL容器的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇怎么用C++模拟实现STL容器文章都会有所收获，下面我们一起来看看吧。一、list的介绍列表是一种顺序容器，它允许在...
    99+
    2023-07-04
  • C++String部分成员模拟实现流程详解
    目录string类的成员设计普通构造函数的模拟拷贝构造函数的模拟赋值重载函数的模拟String的析构函数模拟补全上述的成员函数迭代器的简单模拟其他成员函数的模拟string类的成员设...
    99+
    2024-04-02
  • C++之list容器模拟怎么实现
    这篇“C++之list容器模拟怎么实现”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C++之list容器模拟怎么实现”文章吧...
    99+
    2023-07-05
  • C++之list容器模拟实现方式
    目录总述一、节点类二、迭代器类成员变量构造函数*重载->重载“++”“==“和”!=”三、反向迭代器类成...
    99+
    2023-02-05
    C++ list容器 list容器模拟实现 模拟实现list
  • C++模拟实现List迭代器详解
    目录概念迭代器使用迭代器模拟实现迭代器的大体结构构造函数解引用重载重载自增实现自减实现运算符重载迭代器失效模拟List概念 迭代器是一种抽象的设计概念，其定义为：提供一种方法，使他能...
    99+
    2024-04-02
  • C++初阶之list的模拟实现过程详解
    list的介绍 list的优点： list头部、中间插入不再需要挪动数据，O(1)效率高 list插入数据是新增节点，不需要增容 list的缺点： ...
    99+
    2024-04-02
  • C++哈希表之闭散列方法的模拟实现详解
    目录哈希概念冲突闭散列线性探测哈希表闭散列的模拟实现模拟实现的闭散列中的问题与改进哈希 概念 可以不经过任何比较，直接从表中得到要搜索的元素。 关键在于通过某种函数，使元素的存储位置...
    99+
    2022-11-13
    C++哈希表实现闭散列 C++ 闭散列 C++哈希表
  • C++日期类计算器的模拟实现举例详解
    目录日期类计算器的模拟实现：：1.获取某年某月的天数2.构造函数3.拷贝构造函数4.赋值运算符重载5.析构函数6.日期+=天数7.日期+天数8.日期-天数9.日期-=天数10.前置+...
    99+
    2023-05-18
    C++日期类计算器 c++ 计算日期 c++计算日期对应的天数
  • C语言 数据结构之数组模拟实现顺序表流程详解
    目录线性表和顺序表线性表顺序表静态顺序表动态顺序表代码已经放在Gitee上，需要可以小伙伴可以去看看 用C语言数组模拟实现顺序表 Gitee 线性表和顺序表 线性表 线性表（line...
    99+
    2024-04-02
  • C++详细讲解模拟实现位图和布隆过滤器的方法
    目录位图引论概念解决引论位图的模拟实现铺垫结构构造函数存储set,reset,testflip,size,countany,none,all重载流运算符测试位图简单应用位图代码汇总布...
    99+
    2024-04-02
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作