C++之红黑树

红黑树的概念

红黑树是一种二叉搜索树，在每个节点上增加一个储存位代表节点的颜色，可以是黑色或者是红色。通过对任何一条从根节点到叶子节点的路径上节点颜色的限制，红黑树可以保证没有一条路径会比其他路径长两倍，由此接近平衡。

红黑树的性质

1.每个节点不是红色就是黑色

2.根节点是黑色的

3.如果一个节点是红色，那么它的孩子节点是黑色

4.对于每个节点，从该节点到其所有后代节点的简单路径上，均包含相同数目的黑色节点

5.每个叶子节点都是黑色的(在这里叶子节点指根节点)

红黑树节点的定义

包含左孩子，右孩子，双亲，值域，节点

红黑树的结构

在红黑树钟增加一个头节点，将头节点给成黑色，让头节点的pParent指向红黑树的根节点，pLeft指向红黑树的最小节点，pRight指向红黑树的最大节点

红黑树的插入操作

红黑树实在二叉搜索树的基础上加上限制平衡的条件，所以可以分为两步

1.按照二叉搜索树的规则插入新的节点

2.检测新节点插入后，红黑树的性质是否被破坏

1）新节点默认颜色为红色，如果双亲的颜色是黑色，就没有违反红黑树的规则，不需要进行调整

2）新节点插入节点的双亲为红色时，就违反了红色节点的孩子节点只能为黑色的规则

这个时候，就要分三种情况进行讨论

->第一种情况，cur为红，p为红，g为黑，u存在且为红

解决方式是将p，u改为黑色，g改为红色，然后把g当作cur，继续向上调整

->cur为红，p为红，g为黑，u不存在或者u存在且为黑

u的情况有两种

【1】u节点不存在，cur一定是新插入节点

【2】u节点存在，它一定是黑色的，cur节点原来的颜色一定是黑色的

解决方式

p为g的左孩子，cur为p的左孩子，则进行右单旋；

p为g的右孩子，cur为p的右孩子，则进行左单旋；

p变黑，g变红

->cur为红，p为红，g为黑，u不存在或者u存在且为黑

p为g的左孩子，cur为p的右孩子，则对p进行左单旋；

p为g的右孩子，cur为p的左孩子，则对p进行右单旋；

操作以后就转化为了情况二

红黑树的验证

验证分为两个部分

1.是否满足搜索二叉树性质

2.是否满足红黑树的性质

红黑树的删除

。。。

红黑树与AVL树的比较

红黑树与AVL的增删查改的时间复杂度都是O(log(N)),红黑树不追求绝对的平衡，所以性能更优

红黑树的应用

1.C++的STL（比如map/set，multiset/multimap）

2.。。。

红黑树的迭代器

1.begin()与end()

begin可以是红黑树的最小节点，end是红黑树最大节点的下一个位置

由于end不能为空（因为进行--操作要找点最大节点），所以让end为红黑树的头节点

2.operator++与operator--

->关于operator++，分两种情况，若右子树存在，找右子树的最左节点。若右子树不存在，继续向上查找，直到该节点不为双亲节点的右节点

->关于operator--，分三种情况

pNode在head节点的位置，那么--操作后，指向树中的最大节点；

pNode的左子树存在，--操作后为左子树的最右节点

pNode的左子树不存在，就一直向上找

改造红黑树

1.valuetype：如果是map，就是pair<k,v>类型，如果是set，就是k类型

2.keyOfvalue：通过value来获取key的一个仿函数类

map的模拟实现

在map中封装红黑树

set的模拟实现

在set中封装红黑树