数据结构－红黑树

1.容器
容器用于容纳元素集合，并对元素集合进行管理和维护．
传统意义上的管理和维护就是：增，删，改，查．
我们分析每种类型容器时，主要分析其增，删，改，查动作实现，及复杂度．

2.红黑树
2.1.结构
2.1.1.图解
红黑树是容器类型．
其元素组织采用二叉树结构．

上图是一个包含五个元素的二叉树．
二叉树容器内元素间具备兄弟，父子关系．这种关系通过每个节点内三个指针来维护，它们是：
(1). 指向节点父节点指针
(2). 指向节点左孩子节点指针
(3). 指向节点右孩子节点指针

为了发挥出这类容器的优势，红黑树在二叉树基础上增加了多个一致性约束．这些一致性约束可分为两种类型．
一种类型为了元素有序，一种类型为了树中任意节点左子树，右子树的高度平衡．
(1). 服务于元素有序的一致性约束
对树中任意节点p．
若p的左孩子节点lp存在，则以lp为根子树中所有节点内元素均小于p节点内元素．
若p的右孩子节点rp存在，则rp为根子树中所有节点内元素均大于p节点内元素．

通过这个一致性约束，我们保证了二叉树的有序性，但这个性质给我们带来的好处是什么呢？
通过该性质，在二叉树中查找元素时候，我们可以运用二分查找加快查找速度．

上述二叉树满足有序的约束．我们若在其中查找值为5的元素．
二分查找过程如下：
(1). 初始查找节点为根节点
(2). 判断当前节点p和5关系．
a. p中元素小于5，由于有序性质，只能将当前节点p设置为p的右孩子继续查找．
b. p中元素大于5，由于有序性质，只能将当前节点p设置为p的左孩子继续查找．
c. p中元素等于5，则找到，停止迭代．
d. p为空指针，查找结束，树中不存在匹配节点．

(2). 服务于树中任意节点左子树，右子树高度平衡的一致性约束．
a. 任意节点需要携带颜色标记，颜色标记要么为红色，要么为黑色．
b. 树的根节点的颜色标记必须为黑色．
c. 对树中任意节点p，若p的父节点pp存在且颜色标记为红色，则p的颜色标记必须为黑色．
d. 对树中任意节点p，p的左子树的黑高和p的右子树的黑高必须一致．

上图是一个包含五个元素的红黑树．
首先，这棵树是一颗二叉树．
然后，这棵树满足有序的一致性约束．
最后，这棵树满足关于高度平衡的一致性约束．
如何确定树的黑高：
由于红黑树一致性约束规定了树中任意节点的左子树，右子树黑高一致．
为了得到树的黑高，我们只需确定一条从根节点到叶子节点的路径，然后统计此路径上颜色标记为黑色的节点个数即可．

通过平衡性的一致性约束，可以带给我们什么好处呢？
给定一个红黑树．
a. 其根节点为p，p的左孩子为lp，p的右孩子为rp．
b. 容器内元素总数为n．
c. 树的黑高为h．
对一个黑高为h的树来说，极端情况下，该树内所有节点颜色标记均为黑色下，该树中的节点数量最少．
由于任意节点左，右子树黑高一致的约束．此时，树中节点全黑的树，只能是一颗满二叉树．
满二叉树下，给定高度h，可以计算树中节点总数= $2^0$ + $2^1$ + … + $2^{h-1}$=$2^h$-1．

这样存在h和n之间存在下面的关系：$2^h$-1　<= n
可以简化为h <= log以2为底n+1的对数．

又因为父节点颜色标记为红色，子节点颜色标记必须为黑色的约束．
所以，给定一颗黑高为h的红黑树，从根节点到叶子节点理论上最长的一条路径只能是，路径上交替出现黑色－红色这样的情况．此情况下，理论上根节点到叶子节点最长路径的高度为：2h．

这样，当我们满足平衡约束时，我们获得的好处是：
可以确定根节点到叶子节点最长的一条路径高度小于等于2*log以2为底n+1的对数．

2.1.2.存在一致性约束容器特点
(1). 插入无需提供位置信息．
(2). 不支持直接原地修改．一般分解为移除，添加两个过程．
(3). 由于元素值决定其位置，这类容器一般插入元素时，一般以std::pair<key, value>形式插入．即元素包含键，值两部分．键用来实现一致性约束．值是此键关联的实际内容．