【C++】用红黑树封装map、set
创始人
2025-01-15 16:36:27
0

用红黑树封装map、set

  • 1. 红黑树
    • 1.1 模板参数的控制
      • 1.1.1 Value
      • 1.1.2 KeyOfValue
    • 1.2 正向迭代器
      • 1.2.1 构造函数
      • 1.2.2 begin()+end()
      • 1.2.3 operator++()
      • 1.2.4 operator--()
      • 1.2.5 operator*()
      • 1.2.6 operator->()
      • 1.2.7 operator==()
      • 1.2.8 operator!=()
      • 1.2.9 总代码
    • 1.3 反向迭代器
      • 1.3.1 rbegin()+rend()
      • 1.3.2 总代码
    • 1.4 find()
    • 1.5 insert()
  • 2. Map
    • 2.1 operator[]
  • 3. typename作用
  • 4. 完整代码
    • 4.1 Map.h
    • 4.2 Set.h
    • 4.3 RBTree.h

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//红黑树的节点 struct RBTreeNode { 	typedef RBTreeNode 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 RBTree {   public: 	typedef RBTreeNode Node; }; 
template class set{   //K模型 public:            private:  //set中的key不允许被修改 		RBTree _t;  //红黑树对象 	}; } 
template class map {   //KV模型   public:  private:   //map中的key不允许被修改 		RBTree, MapKeyOfT> _t;  //红黑树对象 	};  }; 

1.1.2 KeyOfValue

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

image.png

// KeyOfT : 取出Value对象中的key template  class RBTree {  }; 
struct SetKeyOfT{    	const K& operator()(const K& key) 	{ 		return key;  //key 	} }; 
struct MapKeyOfT { 	const K& operator()(const pair& 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  struct RBTreeIterator   //红黑树的正向迭代器 { 	typedef RBTreeNode Node; 	typedef RBTreeIterator 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 struct ReverseIterator  //红黑树的反向迭代器——适配器 begin = rend、end = rbegin { 	typedef ReverseIterator 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 insert(const T& data) ;

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

image.png

  • insert返回值为pair,若key(set的key、map的pair的first)在树中存在,因为搜索树中不能出现重复的键值key,所以pair::first指向在树中与key值相等的迭代器,pair::second为false。若key在树中不存在,pair::first指向在树中新插入元素的迭代器,pair::second为true。insert相当于查找。
pair 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 ret = _t.insert(make_pair(key, V())); 	return ret.first->second; } 

3. typename作用

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

4. 完整代码

4.1 Map.h

#pragma once #define _CRT_SECURE_NO_WARNINGS 1  #include"RBTree.h" #include  namespace zzx { 	template 	class map {   //KV模型   	public:  		struct MapKeyOfT { 			const K& operator()(const pair& kv) 			{ 				return kv.first;  //pair中的key 			} 		};  		//使用::两种情况:静态变量、类中typedef的类型  typename表示::前面为类型,不是静态成员 		typedef typename RBTree, MapKeyOfT>::iterator iterator;   //正向迭代器 		typedef typename RBTree, 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 insert(pair& kv)  //插入 		{ 			return _t.insert(kv); 		}  		V& operator[](const K& key) //功能:查找+修改、插入+修改 		{ 			pair ret = _t.insert(make_pair(key, V())); 			return ret.first->second; 		}  	private:   //map中的key不允许被修改 		RBTree, MapKeyOfT> _t;  //红黑树对象 	};  }; 

4.2 Set.h

#pragma once #define _CRT_SECURE_NO_WARNINGS 1  #include"RBTree.h"  namespace zzx{ 	template 	class set{   //K模型 	public:   //仿函数类:比较对象大小,获取对象中的元素—自己手动传递比较逻辑 		struct SetKeyOfT{    			const K& operator()(const K& key) 			{ 				return key;  //key 			} 		};  		//使用::两种情况:静态变量、类中typedef的类型  typename表示::后面为类型,不是静态成员 		typedef typename RBTree::iterator iterator;   //正向迭代器 		typedef typename RBTree::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 insert(const K& key)  //插入 		{ 			return _t.insert(key); 		}  	private:  //set中的key不允许被修改 		RBTree _t;  //红黑树对象 	}; } 

4.3 RBTree.h

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include  using namespace std;  enum Color {  //枚举,一一列举出事物具有的所有可能 	Red,  //枚举常量,给枚举变量进行赋值 	Black, };  template//红黑树的节点 struct RBTreeNode { 	typedef RBTreeNode 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  struct RBTreeIterator   //红黑树的正向迭代器 { 	typedef RBTreeNode Node; 	typedef RBTreeIterator 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 struct ReverseIterator  //红黑树的反向迭代器——适配器 begin = rend、end = rbegin { 	typedef ReverseIterator 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 RBTree {   public: 	typedef RBTreeNode Node;  	//正向迭代器 	typedef RBTreeIterator iterator;  //普通迭代器 	typedef RBTreeIterator const_iterator; //const迭代器  	//反向迭代器 	typedef ReverseIterator reverse_iterator; 	typedef ReverseIterator 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 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; }; 

相关内容

热门资讯

专业讨论!德扑之星真破解套路(... 专业讨论!德扑之星真破解套路(辅助挂)软件透明挂(有挂了解)-哔哩哔哩;人气非常高,ai更新快且高清...
每日必看!智星德州菠萝外挂检测... 每日必看!智星德州菠萝外挂检测(辅助挂)软件透明挂(有挂教学)-哔哩哔哩1、玩家可以在智星德州菠萝外...
透视透明挂!轰趴十三水有后台(... 轰趴十三水有后台赢率提升策略‌;透视透明挂!轰趴十三水有后台(辅助挂)软件透明挂(有挂详情)-哔哩哔...
发现玩家!德扑ai助手软件(辅... 发现玩家!德扑ai助手软件(辅助挂)透视辅助(有挂教学)-哔哩哔哩;玩家在德扑ai助手软件中需先进行...
一分钟了解!x-poker辅助... 一分钟了解!x-poker辅助软件(辅助挂)辅助透视(有挂攻略)-哔哩哔哩1、每一步都需要思考,不同...
一分钟揭秘!德州最新辅助器(辅... 一分钟揭秘!德州最新辅助器(辅助挂)透视辅助(有挂攻略)-哔哩哔哩;德州最新辅助器最新版本免费下载安...
玩家攻略推荐!德州辅助(辅助挂... 玩家攻略推荐!德州辅助(辅助挂)辅助透视(有挂了解)-哔哩哔哩是由北京得德州辅助黑科技有限公司精心研...
揭秘真相!pokernow德州... 《揭秘真相!pokernow德州(辅助挂)辅助透视(有挂介绍)-哔哩哔哩》 pokernow德州软件...
五分钟了解!德州之星辅助器(辅... 五分钟了解!德州之星辅助器(辅助挂)辅助透视(有挂透明)-哔哩哔哩1、很好的工具软件,可以解锁游戏的...
推荐一款!pokermaste... 1、推荐一款!pokermaster有外挂(辅助挂)透视辅助(有挂教学)-哔哩哔哩;详细教程。2、p...