纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

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

TT在长大   2021-12-07 我要评论
想了解C++ STL容器详解之红黑树部分模拟实现的相关内容吗,TT在长大在本文为您仔细讲解C++ STL红黑树实现的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++ 红黑树,C++ STL红黑树,C++ STL红黑树实现,下面大家一起来学习吧。

一、红黑树的概念

红黑树(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);
	}
};

总结

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


相关文章

猜您喜欢

  • JavaScript BOM对象 JavaScript的三种BOM对象

    想了解JavaScript的三种BOM对象的相关内容吗,bear*6在本文为您仔细讲解JavaScript BOM对象的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:JavaScript 对象,JavaScript BOM对象,下面大家一起来学习吧。..
  • C++ 编译与链接 C++中的编译与链接

    想了解C++中的编译与链接的相关内容吗,一个热爱学习的深度渣渣在本文为您仔细讲解C++编译与链接的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++编译,C++链接,下面大家一起来学习吧。..

网友评论

Copyright 2020 www.orsoft.cn 【OR下载站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式