【C++】红黑树_c++红黑树

红黑树概念

空树
非空树：二叉搜索树 + 平衡条件限制 （红黑树性质约束）
保证最长路径中节点个数不超过最短路径中结点个数的两倍，因此红黑树是一颗近似平衡的二叉搜索树

红黑树的性质
1、每个节点不是红色就是黑色；
2、根节点是黑色的；
3、若一个节点是红色的，则它的两个孩子节点是黑色的------即不可能有连在一起的红色节点；
4、对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；
5、每个叶子节点都是黑色的------此处叶子节点指空节点；

红黑树基本操作

红黑树的定义

红黑树是在节点信息中增加了颜色信息，因此定义节点的颜色信息：

//节点颜色信息定义为枚举类型
enum Color {
	RED,
	BLACK
};
1
2
3
4
5

红黑树结构：

红黑树其实也是一颗二叉搜索树

定义一个头节点 _head ，它的左指针域指向该树最左侧节点（节点值域最小节点），右指针域指向该树最右侧节点（节点值域最大节点）

//定义红黑树节点信息
template<class T>
struct RBTreeNode {
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Color _color;

	//将插入的新节点的颜色默认为红色
	RBTreeNode(const T*data = T(), Color color = Red)
	:_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_color(color)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Q：为什么新插入的节点默认定义为红色的？

假如我们在一颗已知的红黑树中插入一个新节点，并将新节点定义为黑色，则会破坏掉红黑树的性质4；

但若将新节点定义为红色，则不会破坏性质4，但有可能会破坏掉性质3；

分析一下：
（1）若插入新节点颜色定义为黑色，则一定会破坏红黑树的性质4–>每条路径上黑色节点个数要相等，则此时插入之后必定要对红黑树的结构进行调整；
（2）若插入新节点颜色定义为红色，则不会破坏红黑树的性质4，但是有可能会破坏性质3–>不存在连在一起的红色节点，则此时有可能需要对红黑树结构进行调整；

由此可见，将新插入的节点颜色默认设置为红色会更好一些。

然而对红黑树的调整，请看下文介绍咯~~

红黑树的插入**

在创建一颗红黑树时候，不论该树是否为空，我们都首先需要定义一个头节点 ：

typedef RBTreeNode<T> Node;

RBTree(){      //实现红黑树的构造函数
		//必须有头节点
		_head = new Node();        //头节点的左指针域指向红黑树最左侧节点（最小值），右指针域指向红黑树最右侧节点（最大值）
		_head->_parent = nullptr;
		_head->_left = _head;
		_head->_right = _head;     //类似于双向循环链表头部的定义
	}
1
2
3
4
5
6
7
8
9

插入的节点是根节点：

向红黑树中插入新节点时候，倘若该树中只有一个头节点，表明该红黑树为空树，需要插入的节点是根节点（根节点颜色为黑色—性质2）

Node*& root = _head->_parent;
		if (nullptr == root) {
			//红黑树中仅有头节点----空树,直接插入新节点--根
			root = new Node(data, BLACK);   //根节点必须是黑色
			root->_parent = _head;
			_head->_parent = root;
			_head->_left = root;
			_head->_right = root;
			return true;
		}
1
2
3
4
5
6
7
8
9
10

即图形化显示为：

插入的节点是普通节点：

若该红黑树非空，则在红黑树中插入新节点类似于在二叉搜索树中进行插入，首先需要找到要进行插入的位置然后在进行插入：（红黑树其实也就是一个二叉搜索树）

//非空树中插入------伪代码
		Node*& root = _head->_parent;
		Node*cur = root;
		Node*parent = _head;
		while (cur) {   //开始寻找要进行插入的位置
			parent = cur;
			if (data < cur->_data)
				cur = cur->_left;
			else if (data > cur->_data)
				cur = cur->_right;
			else
				return false;  //要插入的节点已经存在了
		}
		//插入新节点
		cur = new Node(data);
		if (data < parent->_data)
			parent->_left = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;
		
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

默认新插入的节点颜色为红色，则我们需要在插入之后判断是否破坏了红黑树的性质3–>不存在连在一起的红色节点，若存在则需要对该红黑树进行调整。

插入新节点之后，判断红黑树性质3是否遭到破坏

因为新插入的节点 cur 颜色为红色，若此时 cur 的双亲结点为黑色，则此时没有违反红黑树的性质3，不需要对该红黑树结构进行调整；
但若插入的新节点 cur 的双亲结点颜色也是红色，则违反了红黑树的性质3–>红色节点不能连在一起，此时需要分情况来进行讨论：

新插入的节点为 cur ，其双亲节点为 p，祖父节点为 g，叔叔节点为 u

（1）情况一：cur 红，p 红，g 黑，u 存在且为红

此时，我们假设下方的节点 a,b,c,d,e 都是空来进行调整（因为 cur 位置破坏了红黑树性质，说明 cur 是新插入的节点 破坏了其原始结构，因此可以将 cur 的子树看作是空的）

但这又会存在一个问题----》假如根节点 gg 也是红色呢？

若 gg 节点是黑色，则调整没有任何问题，没有破坏其子树性质，但若 gg 节点是红色则又会破坏性质3 ，使得两个红色节点连在了一起

那么我们就需要逐步向上进行调整，将 cur 放在 g 的位置，p 放在 gg 节点位置，则当前的形式又回归到了此步调整最初的形式：

（2）情况二：cur 红，p 红，g 黑，u 不存在或 u 存在且为黑

u 存在且为黑

u 不存在

（3）情况三：cur 红，p 红，g 黑，u 不存在或 u 存在且为黑

情况二中 cur 是 p 的左孩子节点，情况三中 cur 是 p 的右孩子节点

u 不存在

u 存在且为黑

因此，我们考虑将情况三转换为情况二来进行处理：

注意，上述三种情况我们分析的都是 cur 在左侧的情况，则 cur 在右侧时也应该分为这三种情况来进行处理

上述图解对应的代码部分：

//红黑树首先是二叉搜索树
	bool Insert(const T& data)
	{
		Node*& root = _head->_parent;
		if (nullptr == root) {
			//红黑树中仅有头节点----空树,直接插入新节点--根
			root = new Node(data, BLACK);   //根节点必须是黑色
			root->_parent = _head;
			_head->_parent = root;
		}
		else {
			//非空树中插入
			Node*cur = root;
			Node*parent = _head;
			while (cur) {  //寻找要进行插入的位置
				parent = cur;
				if (data < cur->_data)
					cur = cur->_left;
				else if (data > cur->_data)
					cur = cur->_right;
				else
					return false;  //要插入的节点已经存在了
			}
			//插入新节点
			cur = new Node(data);
			if (data < parent->_data)
				parent->_left = cur;
			else
				parent->_right = cur;
			cur->_parent = parent;

			//默认插入新节点的颜色是红色-----因此要检测其双亲是否也是红色-->会违反性质：不存在连续的红色节点

			while (parent != _head && parent->_color == RED) {  //确保双亲不是根节点
				//调整:确保根节点是黑色的
				//且每条路径上黑色节点个数相等
				//不存在连续的红色节点
				Node* grandFather = parent->_parent;  //祖父节点

				//parent 是 grandFather 左孩子
				if (parent == grandFather->_left) {
					Node* unclue = grandFather->_right;  //叔叔节点
					if (unclue && RED == unclue->_color) {
						//情况一
						//叔叔节点存在且为红，需要将 unclue 与 parent 改为黑色
						parent->_color = BLACK;
						unclue->_color = BLACK;
						grandFather->_color = RED;
						//向上调整
						cur = grandFather;
						parent = cur->_parent;
					}
					else {
						//叔叔节点不存在/存在且为黑色---》情况二、三
						if (cur == parent->_right) {
							//情况三
							RotateLeft(parent);  //左单旋转化为情况二
							swap(parent, cur); //修改指针指向
						}
						//情况二
						parent->_color = BLACK;
						grandFather->_color = RED;
						//右单旋 
						RotateRight(grandFather);
					}
				}
				else {
					//双亲是祖父的右孩子
					Node* unclue = grandFather->_left;  //叔叔节点
					if (unclue && RED == unclue->_color) {
						//叔叔节点存在为红
						//情况一
						parent->_color = BLACK;
						unclue->_color = BLACK;
						grandFather->_color = RED;
						//向上调整
						cur = grandFather;
						parent = cur->_parent;
					}
					else {
						//叔叔节点不存在或存在为黑--->情况二、三
						if (cur == parent->_left) {
							//右单旋
							RotateRight(parent);
							//调整指针指向
							swap(cur, parent);
						}
						//情况三：
						parent->_color = BLACK;
						grandFather->_color = RED;
						//左单旋
						RotateLeft(grandFather);
					}
				}
			}
		
		}
		_head->_parent->_color = BLACK;  //根节点必须为黑
		//更新_head 左右指向
		_head->_left = LeftMost();
		_head->_right = RightMost();

		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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

在前边概念部分我们介绍到，红黑树中增加了一个头节点 _head ，其左指针指向该红黑树最左侧节点，右指针指向该红黑树最右侧节点，则获取这俩个节点的方法如下：

Node* LeftMost()  //获取最左侧节点（值域最小）
	{
		Node* root = _head->_parent;
		if (nullptr == root)
			return _head;
		
		Node*cur = root;
		while(cur->_left)
			cur = cur->_left;
		return cur;
	}

	Node* RightMost()  //获取最右侧节点（值域最大）
	{
		Node* root = _head->_parent;
		if (nullptr == root)
			return _head;

		Node*cur = root;
		while(cur->_right)
			cur = cur->_right;
		return cur;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二叉树的旋转方法可以参考 AVL 树中结构调整方式：添加链接描述

其对应的旋转代码：

void RotateLeft(Node* parent)   //左单旋----》 右子树高
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;  //可能为空

		//修改指针指向
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		subR->_left = parent;
		Node*pparent = parent->_parent;
		parent->_parent = subR;
		subR->_parent = pparent;
		if (pparent == _head) {  //原来的 parent 为根节点
			_head->_parent = subR;
		}
		else {  //原来的 parent 不是根节点，需要对其双亲的左右指向进行修改
			if (parent == pparent->_left)
				pparent->_left = subR;
			else
				pparent->_right = subR;
		}
	}

	void RotateRight(Node* parent)  //右单旋----》左子树高
	{
		Node* subL = parent->_left;
		Node*subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		Node*pparent = parent->_parent;
		parent->_parent = subL;
		subL->_parent = pparent;
		if (pparent == _head) {
			_head->_parent = subL;
		}
		else {
			if (parent == pparent->_left)
				pparent->_left = subL;
			else
				pparent->_right = subL;
		}
	}
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

红黑树相关代码参考：添加链接描述

红黑树的判断

要判断一颗树是否是红黑树，也就是判断树中条件是否满足红黑树的各个性质：

红黑树的性质
1、每个节点不是红色就是黑色；
2、根节点是黑色的；
3、若一个节点是红色的，则它的两个孩子节点是黑色的------即不可能有连在一起的红色节点；
4、对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；
5、每个叶子节点都是黑色的------此处叶子节点指空节点；

//判断是否是红黑树
	bool ISValidRBTree()
	{
		Node*root = _head->_parent;
		if (nullptr == root) {
			return true;  //空树也是红黑树
		}
		//非空树
		//验证性质二：根节点为黑色
		if (RED == root->_color) {
			cout << "不满足性质二：根节点颜色不是黑色" << endl;
			return false;
		}
		//验证性质4：获取单条路径中黑色节点个数
		size_t blackNodeCount = 0;  //最左侧路径中节点个数
		Node*cur = root;
		while (cur) {
			if (BLACK == cur->_color)
				blackNodeCount++;
			cur = cur->_left;
		}
		size_t pathBlackNode = 0;   //统计的单条路径中黑色节点个数---输出参数
		return _IsValidRBTree(root, pathBlackNode, blackNodeCount);
	}

bool _IsValidRBTree(Node* root, size_t pathBlackNode, const size_t blackNodeCount)
	{  //blackNodeCount 记录了该树最左侧路径中黑色节点的个数
		if (nullptr == root)
			return true;
		if (BLACK == root->_color) {
			pathBlackNode++;    //pathBlackNode 记录了某一条路径上黑色节点个数
		}
		Node*parent = root->_parent;
		if (parent != _head && RED == parent->_color && RED == root->_color) {
			cout << "不满足性质3：存在连在一起的红色节点" << endl;
			return false;
		}

		if (nullptr == root->_left && nullptr == root->_right)
		{
			//此时走到叶子位置，即当前路径中黑色节点个数统计完成
			if (pathBlackNode != blackNodeCount) {
				cout << "不满足性质4：路径中黑色节点个数不等" << endl;
				return false;
			}
		}

		return _IsValidRBTree(root->_left, pathBlackNode, blackNodeCount) && _IsValidRBTree(root->_right, pathBlackNode, blackNodeCount);
	}

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

红黑树与AVL树

红黑树与AVL树都是高效的平衡二叉树，都属于二叉搜索树，增删改查的时间复杂度都是 O(log2(n))；

红黑树不追求绝对的平衡，只要保证最长路径不超过最短路径的两倍，相对来说降低了插入与旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优。

AVL树存在平衡因子，要确保每个子树的平衡因子的绝对值不大于 1。

红黑树的应用

C++ STL库、map/set、multiset/multimap 底层实现都是使用的红黑树

迭代器的实现

（1）顺序结构

在顺序表结构中，迭代器可以看作是普通的指针类型，begin()位于第一个有效元素位置，end()位于最后一个有效元素的下一个位置；
对迭代器进行++操作，也就是对指针++，使其指向下一个元素的位置，解引用* 可以取出对应的元素值；
对迭代器进行–操作，也就是对指针 --，使其指向前一个元素的位置，解引用 * 可以取出元素值；
并且迭代器可以进行值信息的比较：== , != ;
但注意，若迭代器位于 begin() 位置，则进行 – 操作是不合法的，同理 end() ++ 也是不合法的；

（2）链式结构

由于链式结构中，元素并不一定是顺序存储的，因此对迭代的 ++ ， – ， * ， -> 等操作是需要我们自己进行封装的，具体可以回顾以下 STL 中所介绍的

红黑树的存储并不一定是连续的空间，因此我们同样也需要对迭代器的各个操作进行封装处理：

//封装迭代器对应的类
template<class T,class Ref,class Ptr>
class RBTreeIterator {
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	
public:
	RBTreeIterator(Node* pNode = nullptr) :_pNode(pNode)
	{}
	//迭代器必须具有指针类似操作

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

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

	//迭代器能够比较
	bool operator==(const Self& s)const
	{
		return _pNode == s._pNode;
	}

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

	//迭代器能够移动
	Self& operator++() //前置++
	{
		Increment();
		return *this;
	}

	Self operator++(int) //后置++
	{
		Self tmp(*this);
		Increment();
		return tmp;
	}

	Self& operator--() //前置--
	{
		Decrement();
		return *this;
	}

	Self operator--(int) //后置--
	{
		Self tmp(*this);
		Decrement();
		return tmp;
	}

	//移动
private:
	void Increment()
	{
		//向前移动--->找大元素--->右子树中寻找最小
		if (_pNode->_right) {
			_pNode = _pNode->_right;
			while (_pNode->_left)
				_pNode = _pNode->left;
		}
		else {
			//右子树不存在，再往双亲中查找
			//若此时节点是双亲的左子树，说明双亲比该节点大，找到；
			//若是双亲的右子树，则双亲比该节点小，需要向上继续查找
			Node* parent = _pNode->_parent;
			while (_pNode == parent->_right) {
				_pNode = parent;
				parent = _pNode->_parent;
			}
			//当 parent 恰好在 _head 时候，此时在进行调整 ： _pNode=parent; parent=_pNode->_parent;  会导致 _pNode 回到 parent 位置会出错
			if(_pNode->_right != parent)
				_pNode = parent;
		}
	}
	//迭代器在 begin() 时候不能进行--，非法操作；end()在最后一个元素的下一个位置，++非法
	//end() 可以 --，begin() 可以 ++
	void Decrement()
	{
		//向后移动--->找小元素----->左子树中寻找最大
		if (_pNode->_parent->_parent==_pNode && RED == _pNode->_color)  //当前位于头节点位置，--返回最右一个节点
			_pNode = _pNode->_right;
		else if (_pNode->_left) {
			_pNode = _pNode->_left;
			while (_pNode->_right) {
				_pNode = _pNode->_right;
			}
		}
		else {
			//左子树不存在，则需要在双亲中查找
			//若是双亲的左子树，则双亲值大于该节点，需要向上继续查找；
			//若是双亲右孩子，则双亲值小于该节点，找到
			Node*parent = _pNode->_parent;
			while (_pNode == parent->_left) {
				_pNode = parent;
				parent = _pNode->_parent;
			}
			_pNode = parent;
		}
	}

private:
	Node* _pNode;
};
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

//迭代器使用
	iterator Begin()
	{
		//迭代器起始位置位于最左侧节点位置--->最小值
		return iterator(_head->_left);   //创建一个匿名对象返回
	}
	iterator End()
	{
		//迭代器结束位置位置最后一个节点的下一个位置---头节点位置
		return iterator(_head);
	}

1
2
3
4
5
6
7
8
9
10
11
12

红黑树封装实现 map set

set 中存储的 V 模型，即只有值类型数据进行存储，因此可以直接使用红黑树来进行封装 set ；

但是 map 中存储的是 KV 模型，也就是一个键值对类型，而红黑树中进行节点插入时候需要按照二叉搜索树的插入规则来进行值的比较来寻找插入的位置，map 中是按照 key 值来进行比较，因此我们需要自己封装一个类来获取 KV 模型中的 K 部分来实现插入时候的比较。

但是 set 与 map 都是在红黑树基础上进行的封装，因此我们需要给 红黑树中增加一个获取键值对中值的一个对象，以确保在红黑树中进行插入时候比较的是键值对中 key 的内容：

//红黑树中相应修改部分代码：
//T 要插入的元素类型，可以是键值对，也可以是K
//KOFT 主要是从 T 中将 K 提取出来------>插入时候比较的是 K 值

template<class T,class KOFT>    //KOFT 从键值对中提取T值
class RBTree {
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> iterator;
	//红黑树首先是二叉搜索树
	//map 插入之后返回值是键值对形式
public:
	pair<iterator,bool> Insert(const T& data)
	{
		Node*newnode = nullptr;
		Node*& root = _head->_parent;
		if (nullptr == root) {
			//红黑树中仅有头节点----空树,直接插入新节点--根
			newnode = root = new Node(data, BLACK);   //根节点必须是黑色
			root->_parent = _head;
			_head->_parent = root;
		}
		else {
			//非空树中插入
			Node*cur = root;
			Node*parent = _head;
			KOFT kOfT;     //获取键值对中的 key ---> 结构体对象

			while (cur) {  //寻找要进行插入的位置
				parent = cur;
				if (kOfT(data) < kOfT(cur->_data))
					cur = cur->_left;
				else if (kOfT(data) > kOfT(cur->_data))
					cur = cur->_right;
				else
					return make_pair(iterator(cur), false);  //要插入的节点已经存在了
			}


			//while (cur) {  //寻找要进行插入的位置
			//	parent = cur;
			//	if (data < cur->_data)
			//		cur = cur->_left;
			//	else if (data > cur->_data)
			//		cur = cur->_right;
			//	else
			//		return make_pair(iterator(cur), false);  //要插入的节点已经存在了
			//}

			newnode = cur = new Node(data);
			if (kOfT(data) < kOfT(parent->_data))  //比较的是 key 值
				parent->_left = cur;
			else
				parent->_right = cur;
			cur->_parent = parent;


			//插入新节点
			/*newnode = cur = new Node(data);
			if (data < parent->_data)
				parent->_left = cur;
			else
				parent->_right = cur;
			cur->_parent = parent;*/




			//默认插入新节点的颜色是红色-----因此要检测其双亲是否也是红色-->会违反性质：不存在连续的红色节点

			while (parent != _head && parent->_color == RED) {  //确保双亲不是根节点
				//调整:确保根节点是黑色的
				//且每条路径上黑色节点个数相等
				//不存在连续的红色节点
				Node* grandFather = parent->_parent;  //祖父节点

				//parent 是 grandFather 左孩子
				if (parent == grandFather->_left) {
					Node* unclue = grandFather->_right;  //叔叔节点
					if (unclue && RED == unclue->_color) {
						//情况一
						//叔叔节点存在且为红，需要将 unclue 与 parent 改为黑色
						parent->_color = BLACK;
						unclue->_color = BLACK;
						grandFather->_color = RED;
						//向上调整
						cur = grandFather;
						parent = cur->_parent;
					}
					else {
						//叔叔节点不存在/存在且为黑色---》情况二、三
						if (cur == parent->_right) {
							//情况三
							RotateLeft(parent);  //左单旋转化为情况二
							swap(parent, cur); //修改指针指向
						}
						//情况二
						parent->_color = BLACK;
						grandFather->_color = RED;
						//右单旋 
						RotateRight(grandFather);
					}
				}
				else {
					//双亲是祖父的右孩子
					Node* unclue = grandFather->_left;  //叔叔节点
					if (unclue && RED == unclue->_color) {
						//叔叔节点存在为红
						//情况一
						parent->_color = BLACK;
						unclue->_color = BLACK;
						grandFather->_color = RED;
						//向上调整
						cur = grandFather;
						parent = cur->_parent;
					}
					else {
						//叔叔节点不存在或存在为黑--->情况二、三
						if (cur == parent->_left) {
							//右单旋
							RotateRight(parent);
							//调整指针指向
							swap(cur, parent);
						}
						//情况三：
						parent->_color = BLACK;
						grandFather->_color = RED;
						//左单旋
						RotateLeft(grandFather);
					}
				}
			}
		
		}
		_head->_parent->_color = BLACK;  //根节点必须为黑
		//更新_head 左右指向
		_head->_left = LeftMost();
		_head->_right = RightMost();
		_size++;
		return make_pair(iterator(newnode), true);
	}

	iterator Find(const T& data)
	{
		Node*cur = _head->_parent;
		KOFT kOfT;   //键值对中的 key 
		while (cur) {
			if (kOfT(data) == kOfT(cur->_data))    //比较的是键值对中的 key 值
				return iterator(cur);
			else if (kOfT(data) < kOfT(cur->_data))
				cur = cur->_left;
			else
				cur = cur->_right;
		}
		return End();  //没找到
	}
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

博客所有代码请戳—> 添加链接描述

走过路过，请留个赞呀~~