【C++----红黑树封装set / map底层大致封装】在C++的世界里，每一次编译都是对智慧的考验，每一次调试都是对耐心的磨砺。开发者们在这里不断学习、成长，用代码编织出一个个精彩纷呈的故事。

红黑树 set / map封装

在这里插入图片描述

1 封装红⿊树实现set和map

1.1对底层源码及框架分析

SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件
中。map和set的实现结构框架核⼼部分截取出来如下：

// set
#ifndef __SGI_STL_INTERNAL_TREE_H
#include 
#endif
#include 
#include 
// map
#ifndef __SGI_STL_INTERNAL_TREE_H
#include 
#endif
#include 
#include 
// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing set
};
// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
typedef Key key_type;
typedef T mapped_type;

typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
};
// stl_tree.h
struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
};
// stl_tree.h
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc
= alloc>
class rb_tree {
protected:
typedef void* void_pointer;
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
typedef rb_tree_node* link_type;
typedef Key key_type;
typedef Value value_type;
public:
// insert⽤的是第⼆个模板参数左形参
pair<iterator,bool> insert_unique(const value_type& x);
// erase和find⽤第⼀个模板参数做形参
size_type erase(const key_type& x);
iterator find(const key_type& x);
protected:
size_type node_count; // keeps track of size of tree
link_type header;
};
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75

• 通过下图对框架的分析，我们可以看到源码中rb_tree⽤了⼀个巧妙的泛型思想实现，rb_tree是实现key的搜索场景，还是key/value的搜索场景不是直接写死的，⽽是由第⼆个模板参数Value决定_rb_tree_node中存储的数据类型。

• set实例化rb_tree时第⼆个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是pair，这样⼀颗红⿊树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。

•源码⾥⾯模板参数是⽤T代表value，⽽内部写的value_type不是我们我们⽇常key/value场景中说的value，源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型。

•那么RBTree中的第一个Key是用来干什么的呢？特别是set都有了数据类型为什么还要传多一个相同的数据类型呢？要注意的是对于map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就完全不⼀样了，map insert的是pair对象，但是find和ease的是Key对象。

在这里插入图片描述

2. 模拟实现map和set

2.1 实现出复⽤红⿊树的框架，并⽀持insert

•参考源码框架，map和set复⽤之前我们实现的红⿊树。

• 我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，红⿊树中的 数据类型，我们使⽤T。

•其次因为RBTree实现了泛型不知道T参数导致是K，还是pair V>，那么insert内部进⾏插⼊逻辑⽐较时，就没办法进⾏⽐较，因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任何时候只⽐较key，所以我们在map和set层分别实现⼀个mapKeyofpair和SetKeyofpair的仿函数传给RBtree的Keyofpair，然后RBtree中通过Keyofpair仿函数取出T类型对象中的key，再进⾏⽐较，具体细节参考如下代码实现。

~map.h
MapKeyOfT
仿函数是为了红黑树比较时能够区分map和set，传MapKeyofpair时，用仿函数去比较就能够区分你到底是传Key过来、还是传pair过来

template <class T1, class T2>
bool operator< (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) &&
lhs.second<rhs.second); }
//pair支持的重载

//这里使用的重点不在pair，也可以直接用库函数来包含



//map.h
template<class K, class V>
  class map
 {
  struct MapKeyofpair
  {
    const K& operator()(const pair<K, V>& kv)
    {
    return kv.first;
    }
  };
public:
bool insert(const pair<K, V>& kv)
  {
   return _t.Insert(kv);底层是红黑树，调用红黑树的insert就行了
  }
private:
RBTree<K, pair<K, V>, MapKeyofpair> _t;
 };
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

~set.h
SetKeyofpair
仿函数是为了红黑树比较时能够区分map和set，传MapKeyofpair时，用仿函数去比较就能够区分你到底是传Key过来、还是传pair过来

template<class K>
 class set
{
  struct SetKeyofT
 {
   const K& operator()(const K& key)
   {
    return key;
   }
 };
public:
  bool insert(const K& key)
  {
    return _t.Insert(key);//底层是红黑树，调用红黑树的insert就行了
  }
private:
RBTree<K, K, SetKeyofpair> _t;
 };
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

~RBtree.h

enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
: _data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};

// 实现步骤：
// 1、实现红⿊树
// 2、封装map和set框架，解决Keyofpair
// 3、iterator
// 4、const_iterator
// 5、key不⽀持修改的问题
// 6、operator[]
template<class K, class T, class KeyOfT>
class RBtree
{
private:
typedef RBTreeNode<T> Node;
Node* _root = nullptr;
public:
bool Insert(const T& data)
{
 if (_root == nullptr)
 {
 _root = new Node(data);
 _root->_col = BLACK;
 return true;
 }
 KeyOfT kot;
 Node* parent = nullptr;
 Node* cur = _root;
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 false;
  }
 }
cur = new Node(data);
Node* newnode = cur;
// 新增结点。颜⾊给红⾊
cur->_col = RED;
 if (kot(parent->_data) < kot(data))
 {
  parent->_right = cur;
 }
 else
 {
  parent->_left = cur;
 }
 cur->_parent = parent;
//...
return true;
 }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

2.2 ⽀持iterator的实现

红黑树的迭代器可不是++就能得到下一个结点的。
  • 1

terator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针再通过重载运算符实现，迭代器像指针⼀样访问的⾏为。

这⾥的难点是operator++和operator–的实现。之前使⽤部分，我们分析了，map和set的迭代器⾛的是中序遍历，左⼦树->根结点->右⼦树，那么begin()会返回中序第⼀个结点的iterator也就是10所在结点的迭代器。

2.2.1红黑树迭代器结构

template<class T, class Ref, class Ptr>
struct RBtreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBtreeIterator<T, Ref, Ptr> Self;

	Node* _node;
	Node* _root;


	RBtreeIterator(Node* node, Node* root)
		:_node(node)
		, _root(root)
	{}
	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

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

	bool operator== (const Self& s) const
	{
		return _node == s._node;
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

2.2.2 迭代器++

迭代器++的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点
【说明】:中序走法
------------左结点->根结点->右结点

情况一（右子树不为空）++：如果指向的结点的右⼦树不为空，代表当前结点已经访问完了，要访问下⼀个结点是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。

情况二（右子树为空）++：如果指向的结点的右⼦树空，代表当前结点已经访问完了且当前结点所在的⼦树也访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上找。

分析：
在这里插入图片描述
右子树为空又可以分成两种情况
情况一：结点是父亲的左
如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结点的⽗亲；如下图：如果it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。
情况二：结点是父亲的右
• 如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前当前结点所在的⼦树访问完了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。如下图：如果it指向15，15右为空，15是10的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个访问的结点就是18。

迭代器end()如何实现呢？
end()如何表⽰呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这是⽗亲为空了，那我们就把it中的结点指针置为nullptr，我们⽤nullptr去充当end。这里雨源码不同，我们是用nullptr来实现end()，而源码使用哨兵位头结点实现end()

stl源码实现迭代器end()
在这里插入图片描述
end()不为nullptr,为header(头结点)
在这里插入图片描述

iterator++代码实现

Self operator++() 
{
	if (_node->_right)
	{
		// 右不为空，中序下一个访问的节点是右子树的最左(最小)节点
		Node* min = _node->_right;
		while (min->_left)
		{
			min = min->_left;
		}

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

		_node = parent;
	}

	return *this;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

2.2.4 iterator–

迭代器–的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->左⼦树，具体参考下⾯代码实现。

特殊处理：
–end()的之后,是走到最后一个结点（最右结点）。

	Self operator--()
	{
		if (_node == nullptr)  // --end()
		{
			// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else if (_node->_left)
		{
			// 左子树不为空，中序左子树最后一个
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else
		{
			// 孩子是父亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}

		return *this;
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

3 注意须知 [实现map/set]

set的iterator也不⽀持修改，我们把set的第⼆个模板参数改成const K即可， RBTree _t;

• map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参数改成const K即可， RBTree, MapKeyOfT> _t;

3.1 map[]实现

map要⽀持[]主要需要修改insert返回值⽀持，修改RBtree中的insert返回值为

V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert({ key, V() });
			return ret.first->second;
		}
  • 1
  • 2
  • 3
  • 4
  • 5

3.2代码实现

//map.h
	template<class K, class V>
	class map
	{
		struct mapKeyofpair
		{
		   const K& operator()(const pair<K,V>& kv)
			    {
				return kv.first;
			    }
		};

	public:
		typedef typename RBtree<K, pair<const K, V>, mapKeyofpair>::Iterator iterator;
		typedef typename RBtree<K, pair<const K, V>, mapKeyofpair>::ConstIterator const_iterator;

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

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

		const_iterator begin() const
		{
			return _t.begin();
		}

		const_iterator end()  const
		{
			return _t.end();
		}

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

	private:
		RBtree<K, pair<const K, V>, mapKeyofpair> _t ;
	};
	//set.h
	template<class K>
	class set
	{
		struct setKeyofpair
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBtree<K, const K, setKeyofpair>::Iterator iterator; 
		typedef typename RBtree<K, const K, setKeyofpair>::ConstIterator const_iterator;
		iterator begin()
		{
		  return _t.begin();
		}

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

		const_iterator begin() const
		{
			return _t.begin();
	    }
		const_iterator end() const
		{
			return _t.end(); 
		}
		pair<iterator, bool>  insert(const K& data)
		{
			return _t.insert(data);
		}

	private:
		RBtree<K,const K, setKeyofpair> _t;
	};
	//RBtree.h
	enum Colour
{
	RED,
	BLACK
};




//红黑树结点
template<class T>
struct RBTreeNode
{
	// 这里更新控制平衡也要加入parent指针
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Colour _col;

	RBTreeNode(const T& data)
		: _data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};
template<class T, class Ref, class Ptr>
struct RBtreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBtreeIterator<T, Ref, Ptr> Self;

	Node* _node;
	Node* _root;


	RBtreeIterator(Node* node, Node* root)
		:_node(node)
		, _root(root)
	{}

	Self operator++() 
	{
		if (_node->_right)
		{
			// 右不为空，中序下一个访问的节点是右子树的最左(最小)节点
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}

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

			_node = parent;
		}

		return *this;
	}

	Self operator--()
	{
		if (_node == nullptr)  // --end()
		{
			// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else if (_node->_left)
		{
			// 左子树不为空，中序左子树最后一个
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else
		{
			// 孩子是父亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}

		return *this;
	}

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

	Ptr operator->()
	{
		return &_node->_data;
	}

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

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

	template<class K, class T,class Keyofpair>
class RBtree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBtreeIterator<T, T&, T*> Iterator; 
	typedef RBtreeIterator<T, const T&, const T*> ConstIterator;





	Iterator begin()
	{
		Node* node = _root;
		while (node && node->_left) 
		{
			node = node->_left;
		}

		return Iterator(node,_root);
	}
	ConstIterator begin() const
	{
		Node* node = _root;
		while (node && node->_left)
		{
			node = node->_left;
		}

		return ConstIterator(node,_root);
	}

	Iterator end()
	{
		return Iterator(nullptr,_root);
	}

	ConstIterator end() const
	{
		return ConstIterator(nullptr,_root); 
	}



	pair<Iterator, bool> insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return{ Iterator(_root, _root), true };
		}
		Keyofpair com; 
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (com(cur->_data) < com(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (com(cur->_data) > com(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return { Iterator(cur, _root), false }; 
			}
		}

		cur = new Node(data);
		Node* newnode = cur;  
		cur->_col = RED;
		if (com(parent->_data) < com(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;
			if (parent == grandparent->_left)
			{
				//   g
				// p   u
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					// 继续往上处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						//     g
						//   p    u
						// c
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						//      g
						//   p    u
						//     c
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED; 
					}

					break;
				}
			}
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					// 继续往上处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					//旋转+变色
					if (cur == parent->_right)
					{
						//     g
					   //   u      p
					  //               c
						RotateL(grandparent); 
						parent->_col = BLACK; 
						grandparent->_col = RED;
					}
					else
					{
						//    g
					   // u       p
					  //      c
					 //需双旋+变色
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;//旋转完后根或者部分根是黑色的不用在意根之前是黑或是红或是空
				}
			}
		}
		_root->_col = BLACK;
		return { Iterator(newnode, _root), true }; 
	}
void RotateR(Node * parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* pParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

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

			subL->_parent = pParent;
		}
	}

	void RotateL(Node * parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

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

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}

private:
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	int _Size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return _Size(root->_left) + _Size(root->_right) + 1;
	}

private:
	Node* _root = nullptr;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367
  • 368
  • 369
  • 370
  • 371
  • 372
  • 373
  • 374
  • 375
  • 376
  • 377
  • 378
  • 379
  • 380
  • 381
  • 382
  • 383
  • 384
  • 385
  • 386
  • 387
  • 388
  • 389
  • 390
  • 391
  • 392
  • 393
  • 394
  • 395
  • 396
  • 397
  • 398
  • 399
  • 400
  • 401
  • 402
  • 403
  • 404
  • 405
  • 406
  • 407
  • 408
  • 409
  • 410
  • 411
  • 412
  • 413
  • 414
  • 415
  • 416
  • 417
  • 418
  • 419
  • 420
  • 421
  • 422
  • 423
  • 424
  • 425
  • 426
  • 427
  • 428
  • 429
  • 430
  • 431
  • 432
  • 433
  • 434
  • 435
  • 436
  • 437
  • 438
  • 439
  • 440
  • 441
  • 442
  • 443
  • 444
  • 445
  • 446
  • 447
  • 448
  • 449
  • 450
  • 451
  • 452
  • 453
  • 454
  • 455
  • 456
  • 457
  • 458
  • 459
  • 460
  • 461
  • 462
  • 463
  • 464
  • 465
  • 466
  • 467
  • 468
  • 469
  • 470
  • 471
  • 472
  • 473
  • 474
  • 475
  • 476
  • 477
  • 478
  • 479
  • 480
  • 481
  • 482
  • 483
  • 484
  • 485
  • 486
  • 487
  • 488
  • 489
  • 490
  • 491
  • 492
  • 493
  • 494
  • 495
  • 496
  • 497
  • 498
  • 499
  • 500
  • 501
  • 502
  • 503
  • 504

最后在这悠长的叙述即将抵达彼岸之时，愿以一曲未了的旋律，轻拂你心灵的涟漪。我们共同走过的这段旅程，如同繁星点缀的夜空，每一颗星辰都承载着故事，每一缕光芒都映照着心迹。此刻，虽言尽而意未尽，但愿这份文字的余温，能伴你度过未来的每一个静！！！

注：本文转载自blog.csdn.net的sdzdwa的文章"https://blog.csdn.net/2301_80109683/article/details/145228408"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！