一.为什么要封装？

以前写的红黑树：

节点存：10 20 30 

只能实现：

但是 STL 中还有：

节点存的是：

如果分别写：

代码会重复很多。

因此 STL 采用：一棵红黑树+模板+仿函数

实现代码复用

二.红黑树模板如何设计

原来：

现在：

参数	作用
K	用来查找比较的 key
T	节点真正存储的数据
KeyOfT	从 T 中提取 key

set实例化

map实例化

1.为什么需要 KeyOfT

set：

直接比较即可。

map：

不能比较整个 pair。

因为pair默认比较first+second一起比较。

而 map 要求只比较 key，即first所以需要一个KeyOfT专门从 T 中取 key

2.SetKeyOfT

set里面：

直接返回自己。

3.MapKeyOfT

map里面：

只取first

三.Insert如何统一

插入时：

统一取 key：

对于 set：

得到：10

对于 map：

得到：

所以同一套Insert即可支持：map set

四.迭代器实现

1.begin()和end()

begin()

返回中序第一个节点：最左节点

end()

2.++it

找中序下一个节点

情况1：

右子树存在

现在it 指向 30

++it;

直接找：右子树最左

此时：

最终：

情况2：

右子树不存在

向祖先找：

it 指向 25

++it;

因为：

执行：

此时：

判断25 是 20 的右孩子成立。

进入循环。

再次判断：20 是 30 的右孩子吗？

不是，退出循环。

当前节点没有右子树，就去祖先里面找第一个把当前节点放在左边的祖先

3.--it

情况1：

左子树存在

找：左子树最右

it 指向 30

--it;

因为：

所以：

情况2：

左子树不存在

向祖先找：孩子是父亲右的那个祖先。

it 指向 25

--it

因为：

所以：

25 是 20 的右孩子

所以：

情况3：一路向上找祖先

it指向10

--it;

10没有左子树。

10 是 20 的左

20 是 30 的左

30 是 50 的左

50 没父亲

所以最终：

说明10已经是最小节点了。

再减非法。

情况5：--end()

此时：

--it;

寻找整棵树最右节点

五.operator[]实现

如果 key 存在，返回 value 的引用；如果 key 不存在，先插入，再返回 value 的引用。

执行：

其实分两步：

首先执行：

必须返回一个东西。

因为后面还有：

所以返回的必须是：

即：

key不存在怎么办？

此时为空

执行：

树里没有apple

那返回谁的引用？

根本没东西可返回。

所以 STL 规定，发现不存在时：

先插入
再返回

所以：

变成：

这里修改了insert的返回值

返回：

第一个：

表示：

Iterator指向节点。

第二个：

是：

表示：