当前位置： 首页 > article >正文

红黑树源代码（进阶与细节解释）

article 2024/10/8 20:07:57

目录

对于结点的修改

红黑树模板参数的控制

红黑树结点当中存储的数据

 对于insert函数的细节修改

 迭代器的代码

迭代器类的添加

迭代器的++

迭代器的--

正向迭代器的代码

红黑树代码全部展示：

看完前两篇的文章，相信对于红黑树有了一定的了解，知道红黑树是怎么样子进行插入的，是怎么样进行查找的，知道了底层是怎么样子的，知道了其与AVL树，二叉搜索树有什么区别了。

但是对于set，map的底层又全是红黑树，set与map的区别就是其键值对一个是k，k型，一个是k，v型的，所以就有了封装，（对于封装后面会讲解什么是封装）二者底层全是同一份的红黑树，但是前面两篇文章的红黑树要不只能使用与k，k型，要不就是k，v型，所以就要对红黑树的源代码进行修改，进行细节上的修饰与进阶。

对于结点的修改

对于此其实不需要进行特别的修改，但是要注意这里的T，如果要是对应的set，那么他就是K，如果是map那么他就是pair<k,v>。

enum Colour
{
	RED,
	BLACK,
};

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

	RBTreeNode(const T& data)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

红黑树模板参数的控制

我们都知道，set是KK模型的容器，而map是KV模型的容器，那我们如何用一棵KV模型的红黑树同时实现map和set呢？

 这里我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。

template<class K, class T>
class RBTree

这里的T也就是对应的结点设置的T，上面也说了，set对应的是K，map是pair<k,v>。

那么下面就看看set容器与map容器中的传的模板参数吧。

set

template<class K>
class set
{
public:
	//...
private:
	RBTree<K, K> _t;
};

map

template<class K, class V>
class map
{
public:
	//...
private:
	RBTree<K, pair<K, V>> _t;
};

那能不能不要红黑树的第一个模板参数，只保留第二个模板参数呢？

乍眼一看好像是可以的，因为此时红黑树的第二个模板参数当中也是有键值Key的，但实际上红黑树的第一个模板参数是不能省略的。

对于set容器来说，省略红黑树的第一个参数当然没问题，因为set传入红黑树的第二个参数与第一个参数是一样的。但是对于map容器来说就不行了，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find和erase。

红黑树结点当中存储的数据

现在红黑树的模板参数变成了K和T，那么红黑树结点当中存储的应该是什么呢？

 前面说到，由于上层容器的不同，底层红黑树当中的K和T也是不同的：

  • set容器：K和T都代表键值Key。
  • map容器：K代表键值Key，T代表由Key和Value构成的键值对。

对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了。

这样一来，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是<Key, Value>键值对。

所以说其实结点的设置其实没有太大的修改，还是与原本还差不多。

 对于insert函数的细节修改

在做完上面的修改后，原本的代码如果在运行下，是会有些问题的，（问题是在封装出现）这里问题是什么就不多说了，

修改起来也是很简单

只需要把其返回值修改为如此就可以。

然后第一个参数就是结点指针，第二个是bool值，插入成功返回true，失败false。 

 迭代器的代码

对于解决迭代器的问题，首先就是要添加一个迭代器类，然后再解决迭代器的++/--，对于红黑树的++，--。用语言来说是很简便的。

迭代器类的添加

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> Self;
	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
};
template<class K, class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator <T, T&, T*> iterator;
	typedef __TreeIterator <T, const T&, const T*> const_iterator;
//......
private:
	Node* _root = nullptr;
};

迭代器的++

核心：中序的下一个

  1. it指向的节点，右子树不为空，下一个就是右子树的最左节点。
  2. it指向的节点，右子树为空，it所在的子树全已访问完了，那么需要往上找孩子是父亲做节点的那个祖先。

迭代器的--

  1. it的左子树不为空，下一个就为左子树的最有节点。
  2. it的左子树为空，沿着根找孩子是父亲右节点的那个祖先。

代码展示：

	Self& operator--()
	{
		//走的是中序  左 根 右
		if (_node->_left)
		{
			//左不为空，下一个就是左子树的最右
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}

		else
		{
			//左为空，没根找孩子是父亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}

		return *this;
	}
	Self& operator++()
	{
		//走的是中序  左 根 右
		if (_node->_right)
		{
			//右子树不为空，下一个就是右子树的最左结点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		
		else
		{
			//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

正向迭代器的代码

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> Self;
	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	Self& operator--()
	{
		//走的是中序  左 根 右
		if (_node->_left)
		{
			//左不为空，下一个就是左子树的最右
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}

		else
		{
			//左为空，没根找孩子是父亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}

		return *this;
	}
	Self& operator++()
	{
		//走的是中序  左 根 右
		if (_node->_right)
		{
			//右子树不为空，下一个就是右子树的最左结点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		
		else
		{
			//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};

对于迭代器的最后一步就是添加上begin（），end（）函数。

红黑树代码全部展示：

#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
enum Colour
{
	RED,
	BLACK,
};

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

	RBTreeNode(const T& data)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> Self;
	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	Self& operator--()
	{
		//走的是中序  左 根 右
		if (_node->_left)
		{
			//左不为空，下一个就是左子树的最右
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}

		else
		{
			//左为空，没根找孩子是父亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}

		return *this;
	}
	Self& operator++()
	{
		//走的是中序  左 根 右
		if (_node->_right)
		{
			//右子树不为空，下一个就是右子树的最左结点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		
		else
		{
			//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};


template<class K,class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator <T, T&, T*> iterator;
	typedef __TreeIterator <T,const T&,const T*> const_iterator;
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return iterator(cur);
	}	
	iterator end()
	{
		return iterator(nullptr);
	}
	const_iterator begin() const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return const_iterator(cur);
	}
	const_iterator end() const
	{
		return const_iterator(nullptr);
	}
	pair<Node*, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);

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

		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;

		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur, false);;
			}
		}

		cur = new Node(data);
		Node* newnode = cur;
		//默认结点颜色为红色

		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			//大前提
			//parent在左
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//Node* uncle = parent->_right;//错误二
				if (uncle && uncle->_col == RED)
				{
					//情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红
						//     g
						//   p   u
						// c
						// 
						//解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						//情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
							//     g
							//   p   u
							// c
							// 
						// 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接break
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
							//       g
							//   p      u
							//     c
						// 解决：对p左单旋，后变为情景二。
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else//情景大概反着来
			{
				//1  uncle
				Node* uncle = grandfather->_left;//错误一
				//Node* uncle = parent->_right;//错误一
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}

				else
				{
					if (cur == parent->_right)//2
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//3
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		//最后
		_root->_col = BLACK;

		return make_pair(newnode, true);;
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;

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

			subR->_parent = parentParent;
		}
	}

	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 (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}
	}

	iterator Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return iterator(cur);
			}
		}
		return end();
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << kof(root->_data) << " ";
		_InOrder(root->_right);
	}
	bool Check(Node* root, int blacknum, const int refVal)
	{
		if (root == nullptr)
		{
			if (refVal != blacknum)
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED)
		{
			if (root->_parent->_col == RED)
			{
				cout << "有连续的红色节点" << endl;
				return false;
			}
		}
		if (root->_col == BLACK)
		{
			++blacknum;
		}
		return Check(root->_left, blacknum, refVal)
			&& Check(root->_right, blacknum, refVal);

	}
	bool IsBalance()
	{
		//1:是否存在 红-红 
	   //每条路径黑色结点是否相同个数
	   //最长的不超过最短的二倍
	   //根，叶子为黑
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
			return false;
		int refVal = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refVal;
			}
			cur = cur->_left;
		}
		int blacknum = 0;
		return Check(_root, blacknum, refVal);
	}
private:
	Node* _root = nullptr;
};

下一篇文章就开始进行封装的解释。


http://www.kler.cn/news/338842.html

相关文章：

  • rockylinux9安装软件报错
  • 哭晕，腾讯的面试太难了。。。
  • MATLAB|基于多主体主从博弈的区域综合能源系统低碳经济优化调度
  • 《2024 国庆旅游数据洞察：活力与新趋势》
  • python中字符串操作
  • 与ZoomEye功能类似的搜索引擎还有哪些？（渗透课作业）
  • 华为 ModelArts：AI开发者的一站式开发平台深度解析
  • 深度解析内网横向移动及防御策略
  • Windows Ubuntu下搭建深度学习Pytorch训练框架与转换环境TensorRT
  • OJ在线评测系统 后端微服务架构 注册中心 Nacos入门到启动
  • Redis: 集群测试和集群原理
  • MySQL连接：内连接
  • COMSOL 声学多物理场仿真技术与应用
  • SQL进阶技巧：如何优化NULL值引发的数据倾斜问题？
  • 【时间盒子】-【9.任务设置项】自定义任务名称、任务时长等设置项组件
  • 函数编程：让开发完全专注于代码
  • 深度学习——生成对抗网络（GAN）
  • 多文件并发多线程MD5工具（相对快速的MD5一批文件），适配自定义MD5 Hash I/O缓存。
  • PCL 计算点云的平均曲率
  • win11远程连接MySQL(linux版)，不需安装docker容器