【C++】用红黑树封装map、set

1. 红黑树

  • set是K模型,map是KV模型,二者底层都是使用红黑树来实现的,所以我们可以将红黑树设置为模板,即:set、map复用同一个类模板的红黑树。

1.1 模板参数的控制

1.1.1 Value

  • Value决定你是k模型的set、还是KV模型的map。

map、set的模板参数value.png

enum Color {  //枚举,一一列举出事物具有的所有可能
	Red,  //枚举常量,给枚举变量进行赋值
	Black,
};

template<class T>//红黑树的节点
struct RBTreeNode {
	typedef RBTreeNode<T> Node;

	//三叉链-》优点:便于查找孩子、父亲节点
	Node* _left;      //该节点的左孩子
	Node* _right;    //该节点的右孩子
	Node* _parent;  //该节点的父亲,便于向上更新
	T _data;
	Color _col;

	RBTreeNode(const T& data, Color col = Red)  //构造函数
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(col)  //默认新插入节点的颜色为红色
	{ }
};

//Value决定你是k模型的set、还是KV模型的map
template<class K, class T, class KeyOfT> 
class RBTree {  
public:
	typedef RBTreeNode<T> Node;
};
template<class K>
class set{   //K模型
public:   
       
private:  //set中的key不允许被修改
		RBTree<K, const K, SetKeyOfT> _t;  //红黑树对象
	};
}
template<class K, class V>
class map {   //KV模型  
public:

private:   //map中的key不允许被修改
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;  //红黑树对象
	};

};

1.1.2 KeyOfValue

  • KeyOfT : 取出Value对象中的key。

image.png

// KeyOfT : 取出Value对象中的key
template<class K, class T, class KeyOfT> 
class RBTree {  };
struct SetKeyOfT{   
	const K& operator()(const K& key)
	{
		return key;  //key
	}
};
struct MapKeyOfT {
	const K& operator()(const pair<K, V>& kv)
	{
		return kv.first;  //pair中的key
	}
};

1.2 正向迭代器

1.2.1 构造函数

💡RBTreeIterator(Node* node) ;

RBTreeIterator(Node* node) //构造函数,单参数构造函数支持隐式类型转化
		:_node(node)
	{ }
  • Tips : 单参数构造函数支持隐式类型转换 Node*->iterator 。

1.2.2 begin()+end()

💡iterator begin( ) ;

  • 功能:返回红黑树中最左节点(左孩子必为空)的迭代器。
  • Tips:set、map对象为非const对象,就调用begin()、end()。
iterator begin()  //红黑树最左节点
{ 
	Node* subLeft = _root;   
	while (subLeft && subLeft->_left)
		subLeft = subLeft->_left;

	return iterator(subLeft);
}	

💡iterator end( ) ;

  • 功能:返回最后一个元素的下一个的迭代器(空指针)。
iterator end()  //空指针 左闭右开[begin,end)
{
	return iterator(nullptr);
}

image.png

1.2.3 operator++()

/*1.右不为空,下一个为该节点右子树的最左节点 ;
	* 2.右为空,说明该节点所在的子树已经访问完了,若该节点为父亲的右,说明该父亲所在的子树也访问完了,继续往上找,
	* 直到该节点为父亲的左,则要访问的下一个节点是它的父亲,即:找祖先里面的孩纸 = 父亲左*/
Self& operator++()  //中序 左、根、右
{
	if (_node->_right)  //1
	{
		Node* subLeft = _node->_right;
		while (subLeft->_left)
			subLeft = subLeft->_left;

		_node = subLeft;
	}
	else  //2
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && parent->_left != cur)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}
  • 中序遍历,左、根、右。
    情况一:右不为空,下一个为该节点右子树的最左节点 ;
    情况二:右为空,说明该节点所在的子树已经访问完了,若该节点为父亲的右,说明该父亲所在的子树也访问完了,继续往上找,直到该节点为父亲的左,则要访问的下一个节点是它的父亲,即:找祖先里面的孩纸 = 父亲左。

image.png

1.2.4 operator–()

/*1.左不为空,下一个为该节点左子树的最右节点 ;
	* 2.左为空,说明该节点所在的子树已经访问完了,若该节点为父亲的左,说明该父亲所在的子树也访问完了,继续往上找,
	* 直到该节点为父亲的右,则要访问的下一个节点是它的父亲,即:找祖先里面的孩纸 = 父亲右*/
Self& operator--() //中序 左、根、右  --与++逻辑相反
{
	if (_node->_left)  //1
	{
		Node* subRight = _node->_left;
		while (subRight->_right)
			subRight = subRight->_right;

		_node = subRight;
	}
	else  //2
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && parent->_right != cur)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

image.png

1.2.5 operator*()

Ref operator*()
{
	return _node->_data;
}

1.2.6 operator->()

Ptr operator->() //结构体指针,data为结构体
{
	return &_node->_data;
}

1.2.7 operator==()

bool operator==(const Self& rb)
{
	return _node == rb._node;
}

1.2.8 operator!=()

bool operator!=(const Self& rb)
{
	return _node != rb._node;
}

1.2.9 总代码

template<class T, class Ref, class Ptr> 
struct RBTreeIterator   //红黑树的正向迭代器
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;

	RBTreeIterator(Node* node) //构造函数,单参数构造函数支持隐式类型转化
		:_node(node)
	{ }

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->() //结构体指针,data为结构体
	{
		return &_node->_data;
	}

	/*1.右不为空,下一个为该节点右子树的最左节点 ;
	* 2.右为空,说明该节点所在的子树已经访问完了,若该节点为父亲的右,说明该父亲所在的子树也访问完了,继续往上找,
	* 直到该节点为父亲的左,则要访问的下一个节点是它的父亲,即:找祖先里面的孩纸 = 父亲左*/
	Self& operator++()  //中序 左、根、右
	{
		if (_node->_right)  //1
		{
			Node* subLeft = _node->_right;
			while (subLeft->_left)
				subLeft = subLeft->_left;

			_node = subLeft;
		}
		else  //2
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_left != cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	/*1.左不为空,下一个为该节点左子树的最右节点 ;
	* 2.左为空,说明该节点所在的子树已经访问完了,若该节点为父亲的左,说明该父亲所在的子树也访问完了,继续往上找,
	* 直到该节点为父亲的右,则要访问的下一个节点是它的父亲,即:找祖先里面的孩纸 = 父亲右*/
	Self& operator--() //中序 左、根、右  --与++逻辑相反
	{
		if (_node->_left)  //1
		{
			Node* subRight = _node->_left;
			while (subRight->_right)
				subRight = subRight->_right;

			_node = subRight;
		}
		else  //2
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right != cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& rb)
	{
		return _node != rb._node;
	}

	bool operator==(const Self& rb)
	{
		return _node == rb._node;
	}
};

1.3 反向迭代器

1.3.1 rbegin()+rend()

💡reverse_iterator rbegin( ) ;

  • 功能:返回红黑树中最右节点(右孩子必为空)的迭代器。
reverse_iterator rbegin()  //红黑树最右节点,因为此处反向迭代器*,是直接调用正向迭代器* [rbegin,erend)
{
	Node* subRight = _root;
	while (subRight && subRight->_right)
		subRight = subRight->_right;

	return reverse_iterator(subRight);
}

💡reverse_iterator rend( ) ;

  • 功能:返回第一个元素的前一个的迭代器(空指针)。
reverse_iterator rend()  
{
	return reverse_iterator(nullptr);
}

1.3.2 总代码

template<class iterator, class Ref, class Ptr>
struct ReverseIterator  //红黑树的反向迭代器——适配器 begin = rend、end = rbegin
{
	typedef ReverseIterator<iterator, Ref, Ptr> Self;  
	iterator _it;   //适配器

	ReverseIterator(iterator it)
		:_it(it)
	{ }

	Ref operator*()
	{
		return *_it;
	}

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

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

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

	bool operator==(const Self& rb)
	{
		return _it == rb._it;
	}

	bool operator!=(const Self& rb)
	{
		return _it != rb._it;
	}
};

1.4 find()

💡iterator find(const K& key) ;

  • 功能:查找。
  • 若key在红黑树中,则返回树中与key值相等元素的迭代器,否则,就返回end( )。
iterator find(const K& key)  //查找  模板参数K的作用
{
	KeyOfT kot;

	Node* cur = _root;
	while (cur)  //先按照二叉搜索树的方式插入
	{
		if (kot(cur->_data) < key)  //通仿函数对象调用operator()来获取T中的key
			cur = cur->_right;
		else if (kot(cur->_data) > key)
			cur = cur->_left;
		else
			return iterator(cur);  //找到了
	}
	return end();  //找不到
}

1.5 insert()

💡pair<iterator,bool> insert(const T& data) ;

  • 功能:向红黑树中插入data。

image.png

  • insert返回值为pair<iterator, bool>,若key(set的key、map的pair的first)在树中存在,因为搜索树中不能出现重复的键值key,所以pair::first指向在树中与key值相等的迭代器,pair::second为false。若key在树中不存在,pair::first指向在树中新插入元素的迭代器,pair::second为true。insert相当于查找。
pair<iterator, bool> insert(const T& data)  //插入  
{   //不能使用引用放回,因为返回值作用域为栈区,传值返回
	KeyOfT kot;  //仿函数类创建的对象,对象去调用operator()

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)  //先按照二叉搜索树的方式插入
    {
    	if (kot(cur->_data) < kot(data))  //通仿函数对象调用operator()来获取T中的key值
    	{
    		parent = cur;
    		cur = cur->_right;
    	}
    	else if (kot(cur->_data) > kot(data))
    	{
    		parent = cur;
    		cur = cur->_left;
    	}
    	else
    	{
    		return make_pair(iterator(cur), false);  //插入节点已存在,插入失败,返回在树中与该节点值相同的迭代器
    	}
    }

    cur = new Node(data);  //注意 insert
		
	Node* newnode = cur;  //非空树,插入成功,因为要做旋转处理,会导致cur值发生改变,需提前将新节点的位置存储起来

	if (parent == nullptr) //空树
	{
		_root = cur;
		_root->_col = Black;  //跟节点为黑
		return make_pair(iterator(_root), true);  //空树,插入成功,返回新插入节点在树中的迭代器
	}

	if (kot(parent->_data) < kot(cur->_data))
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;  //记录当前节点的父亲

	//更新颜色
	//插入结束:1.插入节点的父亲是黑色,因为插入前该树就为红黑树 2.情况一处理完后,cur为根节点,且为黑色
	while (parent && parent->_col == Red)
	{ //爷爷一定存在,因为c为红,p为红,所以p一定不是根节点,且一定有父节点
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)  //旋转需要确定方向
		{
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == Red) //情况一:叔叔存在且为红->无方向(p、u为g的任意边,c为p的任一边)
			{  //cur可能为新增节点,也可能一开始为黑色,cur的子树(下一层为红,下一层为新插入节点)在调整过程中将cur由黑变为红
				parent->_col = uncle->_col = Black; //p、u变为黑,g变为红
				grandfather->_col = Red;

				//g可能为根节点(更新结束),也可能为子树(继续向上更新)
				cur = grandfather;
				parent = cur->_parent;
			}
			else  //情况二:叔叔不存在 或者 叔叔存在且为黑
			{  //叔叔不存在,cur为新增节点 或 cur原来为黑,经子树调整由黑变红
				if (parent->_left == cur)  //左左——右单旋
				{
					RotateR(grandfather);
					parent->_col = Black; //p变为黑,g变为红
					grandfather->_col = Red;
				}
				else    //左右——左右单旋 
				{
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = Black;  //c变黑,g变红
					grandfather->_col = Red;
				}
				break;  //更新结束:3.旋转+颜色处理后就是红黑树了
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == Red)
			{
				parent->_col = uncle->_col = Black;
				grandfather->_col = Red;

				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (parent->_right == cur)  //右右——左单旋
				{
					RotateL(grandfather);
					parent->_col = Black;
					grandfather->_col = Red;
				}
				else   //右左——右左单旋
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = Black;
					grandfather->_col = Red;
				}
				break;
			}
		}
	}
	_root->_col = Black;  //g为根,颜色变为黑,更新结束
	return make_pair(iterator(newnode), true);  //情况一,插入节点的父亲为黑,插入结束
}

2. Map

2.1 operator[]

💡V& operator[ ](const K& key) ;

  • 功能:访问与key相对应的value值。即可读又可写。
  • 原理:operator[ ]底层是通过调用insert( )将键值队插入到map中。如果key存在,插入失败,insert返回与map中key值相同元素的迭代器。如果key不存在,插入成功,insert返回在map中新插入元素的迭代器。operator[ ]最后返回与key值相对应的value值的引用。
  • operator[ ] 具有插入、查找、插入+修改、查找+修改功能。
V& operator[](const K& key) //功能:查找+修改、插入+修改
{
	pair<iterator, bool> ret = _t.insert(make_pair(key, V()));
	return ret.first->second;
}

3. typename作用

  1. 使用域作用限定符(: : )的两种情况:静态变量、类中typedef的类型。
  2. 使用typename表示: :后面为类型,不是静态成员
//使用::两种情况:静态变量、类中typedef的类型  typename表示::前面为类型,不是静态成员
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; 

4. 完整代码

4.1 Map.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

#include"RBTree.h"
#include<string>

namespace zzx {
	template<class K, class V>
	class map {   //KV模型  
	public:

		struct MapKeyOfT {
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;  //pair中的key
			}
		};

		//使用::两种情况:静态变量、类中typedef的类型  typename表示::前面为类型,不是静态成员
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;   //正向迭代器
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;  //反向迭代器

		iterator begin()  
		{
			return _t.begin();
		}

		iterator end()  
		{
			return _t.end();
		}

		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}

		reverse_iterator rend()
		{
			return _t.rend();
		}

		iterator find(const K& key)  //查找
		{
			return _t.find(key);
		}

		pair<iterator, bool> insert(pair<const K, V>& kv)  //插入
		{
			return _t.insert(kv);
		}

		V& operator[](const K& key) //功能:查找+修改、插入+修改
		{
			pair<iterator, bool> ret = _t.insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:   //map中的key不允许被修改
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;  //红黑树对象
	};

};

4.2 Set.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

#include"RBTree.h"

namespace zzx{
	template<class K>
	class set{   //K模型
	public:   //仿函数类:比较对象大小,获取对象中的元素—自己手动传递比较逻辑
		struct SetKeyOfT{   
			const K& operator()(const K& key)
			{
				return key;  //key
			}
		};

		//使用::两种情况:静态变量、类中typedef的类型  typename表示::后面为类型,不是静态成员
		typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;   //正向迭代器
		typedef typename RBTree<K, const K, SetKeyOfT>::reverse_iterator reverse_iterator;  //反向迭代器

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}

		reverse_iterator rend()
		{
			return _t.rend();
		}

		iterator find(const K& key)  //查找
		{
			return _t.find(key);
		}

		pair<iterator, bool> insert(const K& key)  //插入
		{
			return _t.insert(key);
		}

	private:  //set中的key不允许被修改
		RBTree<K, const K, SetKeyOfT> _t;  //红黑树对象
	};
}

4.3 RBTree.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

using namespace std;

enum Color {  //枚举,一一列举出事物具有的所有可能
	Red,  //枚举常量,给枚举变量进行赋值
	Black,
};

template<class T>//红黑树的节点
struct RBTreeNode {
	typedef RBTreeNode<T> Node;

	//三叉链-》优点:便于查找孩子、父亲节点
	Node* _left;      //该节点的左孩子
	Node* _right;    //该节点的右孩子
	Node* _parent;  //该节点的父亲,便于向上更新
	T _data;
	Color _col;

	RBTreeNode(const T& data, Color col = Red)  //构造函数
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(col)  //默认新插入节点的颜色为红色
	{ }
};

template<class T, class Ref, class Ptr> 
struct RBTreeIterator   //红黑树的正向迭代器
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;

	RBTreeIterator(Node* node) //构造函数,单参数构造函数支持隐式类型转化
		:_node(node)
	{ }

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->() //结构体指针,data为结构体
	{
		return &_node->_data;
	}

	/*1.右不为空,下一个为该节点右子树的最左节点 ;
	* 2.右为空,说明该节点所在的子树已经访问完了,若该节点为父亲的右,说明该父亲所在的子树也访问完了,继续往上找,
	* 直到该节点为父亲的左,则要访问的下一个节点是它的父亲,即:找祖先里面的孩纸 = 父亲左*/
	Self& operator++()  //中序 左、根、右
	{
		if (_node->_right)  //1
		{
			Node* subLeft = _node->_right;
			while (subLeft->_left)
				subLeft = subLeft->_left;

			_node = subLeft;
		}
		else  //2
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_left != cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	/*1.左不为空,下一个为该节点左子树的最右节点 ;
	* 2.左为空,说明该节点所在的子树已经访问完了,若该节点为父亲的左,说明该父亲所在的子树也访问完了,继续往上找,
	* 直到该节点为父亲的右,则要访问的下一个节点是它的父亲,即:找祖先里面的孩纸 = 父亲右*/
	Self& operator--() //中序 左、根、右  --与++逻辑相反
	{
		if (_node->_left)  //1
		{
			Node* subRight = _node->_left;
			while (subRight->_right)
				subRight = subRight->_right;

			_node = subRight;
		}
		else  //2
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right != cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& rb)
	{
		return _node != rb._node;
	}

	bool operator==(const Self& rb)
	{
		return _node == rb._node;
	}
};

template<class iterator, class Ref, class Ptr>
struct ReverseIterator  //红黑树的反向迭代器——适配器 begin = rend、end = rbegin
{
	typedef ReverseIterator<iterator, Ref, Ptr> Self;  
	iterator _it;   //适配器

	ReverseIterator(iterator it)
		:_it(it)
	{ }

	Ref operator*()
	{
		return *_it;
	}

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

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

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

	bool operator==(const Self& rb)
	{
		return _it == rb._it;
	}

	bool operator!=(const Self& rb)
	{
		return _it != rb._it;
	}
};

//红黑树的模板参数:T决定你是k模型的set、还是KV模型的map ; KeyOfT:取出T对象中的key ; pair比较:先比较first,在比较second
template<class K, class T, class KeyOfT> 
class RBTree {  
public:
	typedef RBTreeNode<T> Node;

	//正向迭代器
	typedef RBTreeIterator<T, T&, T*> iterator;  //普通迭代器
	typedef RBTreeIterator<T,const T&, const T*> const_iterator; //const迭代器

	//反向迭代器
	typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
	typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

	iterator begin()  //红黑树最左节点
	{ 
		Node* subLeft = _root;   
		while (subLeft && subLeft->_left)
			subLeft = subLeft->_left;

		return iterator(subLeft);
	}

	iterator end()  //空指针 左闭右开[begin,end)
	{
		return iterator(nullptr);
	}

	const_iterator begin()const  
	{
		Node* subLeft = _root;
		while (subLeft && subLeft->_left)
			subLeft = subLeft->_left;

		return const_iterator(subLeft);
	}

	const_iterator end()const
	{
		return const_iterator(nullptr);
	}

	reverse_iterator rbegin()  //红黑树最右节点,因为此处反向迭代器*,是直接调用正向迭代器* [rbegin,erend)
	{
		Node* subRight = _root;
		while (subRight && subRight->_right)
			subRight = subRight->_right;

		return reverse_iterator(subRight);
	}

	reverse_iterator rend()  
	{
		return reverse_iterator(nullptr);
	}

	const_reverse_iterator rbegin()const
	{
		Node* subRight = _root;
		while (subRight && subRight->_right)
			subRight = subRight->_right;

		return const_reverse_iterator(subRight);
	}

	const_reverse_iterator rend()const
	{
		return const_reverse_iterator(nullptr);
	}

	iterator find(const K& key)  //查找  模板参数K的作用
	{
		KeyOfT kot;

		Node* cur = _root;
		while (cur)  //先按照二叉搜索树的方式插入
		{
			if (kot(cur->_data) < key)  //通仿函数对象调用operator()来获取T中的key
				cur = cur->_right;
			else if (kot(cur->_data) > key)
				cur = cur->_left;
			else
				return iterator(cur);  //找到了
		}

		return end();  //找不到
	}

	void RotateL(Node* parent)  //右右—左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		Node* pphead = parent->_parent;

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


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

			subR->_parent = pphead;
		}
	}

	void RotateR(Node* parent)  //左左—右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		Node* pphead = parent->_parent;

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

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

			subL->_parent = pphead;
		}
	}

	void RotateRL(Node* parent)  //右左—先右旋再左旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		RotateR(subR);
		RotateL(parent);
	}

	void RotateLR(Node* parent)  //左右—先左旋再右旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		RotateL(subL);
		RotateR(parent);
	}

	pair<iterator, bool> insert(const T& data)  //插入  
	{   //不能使用引用放回,因为返回值作用域为栈区,传值返回
		KeyOfT kot;  //仿函数类创建的对象,对象去调用operator()

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)  //先按照二叉搜索树的方式插入
		{
			if (kot(cur->_data) < kot(data))  //通仿函数对象调用operator()来获取T中的key值
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);  //插入节点已存在,插入失败,返回在树中与该节点值相同的迭代器
			}
		}

		cur = new Node(data);  //注意 insert
		
		Node* newnode = cur;  //非空树,插入成功,因为要做旋转处理,会导致cur值发生改变,需提前将新节点的位置存储起来

		if (parent == nullptr) //空树
		{
			_root = cur;
			_root->_col = Black;  //跟节点为黑
			return make_pair(iterator(_root), true);  //空树,插入成功,返回新插入节点在树中的迭代器
		}

		if (kot(parent->_data) < kot(cur->_data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;  //记录当前节点的父亲

		//更新颜色
		//插入结束:1.插入节点的父亲是黑色,因为插入前该树就为红黑树 2.情况一处理完后,cur为根节点,且为黑色
		while (parent && parent->_col == Red)
		{ //爷爷一定存在,因为c为红,p为红,所以p一定不是根节点,且一定有父节点
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)  //旋转需要确定方向
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == Red) //情况一:叔叔存在且为红->无方向(p、u为g的任意边,c为p的任一边)
				{  //cur可能为新增节点,也可能一开始为黑色,cur的子树(下一层为红,下一层为新插入节点)在调整过程中将cur由黑变为红
					parent->_col = uncle->_col = Black; //p、u变为黑,g变为红
					grandfather->_col = Red;

					//g可能为根节点(更新结束),也可能为子树(继续向上更新)
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //情况二:叔叔不存在 或者 叔叔存在且为黑
				{  //叔叔不存在,cur为新增节点 或 cur原来为黑,经子树调整由黑变红
					if (parent->_left == cur)  //左左——右单旋
					{
						RotateR(grandfather);
						parent->_col = Black; //p变为黑,g变为红
						grandfather->_col = Red;
					}
					else    //左右——左右单旋 
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = Black;  //c变黑,g变红
						grandfather->_col = Red;
					}
					break;  //更新结束:3.旋转+颜色处理后就是红黑树了
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == Red)
				{
					parent->_col = uncle->_col = Black;
					grandfather->_col = Red;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)  //右右——左单旋
					{
						RotateL(grandfather);
						parent->_col = Black;
						grandfather->_col = Red;
					}
					else   //右左——右左单旋
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = Black;
						grandfather->_col = Red;
					}
					break;
				}
			}
		}
		_root->_col = Black;  //g为根,颜色变为黑,更新结束
		return make_pair(iterator(newnode), true);  //情况一,插入节点的父亲为黑,插入结束
	}

private:
	Node* _root = nullptr;
};

相关推荐

最近更新

  1. 6.11 c语言

    2024-06-09 07:44:03       0 阅读
  2. DP专项训练

    2024-06-09 07:44:03       0 阅读
  3. uniapp面试题

    2024-06-09 07:44:03       0 阅读
  4. 【lesson3】服务端Json工具类的设计和实现

    2024-06-09 07:44:03       0 阅读
  5. 力扣475.供暖器

    2024-06-09 07:44:03       0 阅读
  6. 图片based64编码解码python代码

    2024-06-09 07:44:03       0 阅读

热门阅读

  1. 使用 LLaMA-Factory 实现对大模型函数调用功能

    2024-06-09 07:44:03       2 阅读
  2. 二叉树----7-3 列出叶结点

    2024-06-09 07:44:03       3 阅读
  3. bat指令踩坑记录

    2024-06-09 07:44:03       3 阅读
  4. Web Dart前端:探索、挑战与未来展望

    2024-06-09 07:44:03       3 阅读
  5. 计算机视觉中的low-level与 high-level任务

    2024-06-09 07:44:03       5 阅读
  6. python记录之字符串

    2024-06-09 07:44:03       3 阅读
  7. Playwright 这个强大的自动化测试工具

    2024-06-09 07:44:03       3 阅读
  8. 安装 hbase(伪分布式)

    2024-06-09 07:44:03       3 阅读
  9. 密码学基本概念

    2024-06-09 07:44:03       3 阅读
  10. Python为项目中添加上彩色日志

    2024-06-09 07:44:03       3 阅读
  11. perl use HTTP::Server::Simple 轻量级 http server

    2024-06-09 07:44:03       2 阅读
  12. 面试 Redis 八股文十问十答第二期

    2024-06-09 07:44:03       2 阅读
  13. ASP.NET Core 中使用基本消息的 RabbitMQ 消费者

    2024-06-09 07:44:03       3 阅读