一.红黑树的特征
- 红黑树是二叉搜索树
- 红黑树分为内部结点和外部结点,将空指针视为外部结点,其它结点视为内部结点
- 根结点和外部结点都是黑色
- 从根结点到外部结点的路径上不能有连续的红结点
- 从根结点到外部结点的路径上黑结点的数目相同
- 从根结点到外部结点的最长路径的长度不超过最短路径长度的两倍
说明:
引入外部结点的目的是为了说明第5条规则,以上图为例,13->8->1->NULL就是一条从根结点到外部结点的路径,黑色结点数目为3。有多少个外部结点，就有多少条路径，这样判断一棵树是否是红黑树时就不容易遗漏。外部结点只在定义的时候有意义，后续我们将不再讨论外部结点。
二.红黑树的搜索
时间复杂度O(logn)
这主要得益于红黑树的第6条规则：从根结点到外部结点的最长路径的长度不超过最短路径长度的两倍。
而只需遵守前5条规则即遵守了它。换句话说，什么红结点，黑结点的，设计一大堆规则就是为了实现这一条性质。
1.为什么遵守前5条规则就能保证从根结点到外部结点的最长路径的长度不超过最短路径长度的两倍？
证明：假设根结点的黑高位r(黑高是从任意节点出发(不包含该结点)，到外部结点的任一路径上黑色结点的数目)
最短路径：全是黑结点，路径长度为r
最长路径：红结点和黑结点交替出现，路径长度为2r
2.设红黑树的高度为h(不包含外部结点)，内部结点的个数位n，则h<=2log(n+1)
证明：
设r是根结点的黑高
红黑树的高度是所有从根结点到叶节点路径中最长路径的结点数目
故从根结点到外部结点的最长路径长度为h
故h<=2r
又因为根结点黑高位r，故1~r层没有外部结点（没有空结点）
所以n>=2^r-1，即r<=log(n+1)
综上，h<=2log(n+1),故搜索的时间复杂度为O(logn)
三.红黑树的插入
首先按照二叉搜索树的插入方法将结点插入到合适的叶结点，然后赋予结点颜色。
给新插入结点赋予什么颜色？
假设赋黑色，导致新增结点所在路径黑色结点增多，影响所有路径，调整难度非常大
假设赋红色，只会影响本条路径，影响相对较小
所以选择赋红色
1.parent为黑色
此时不用作任何调整，直接结束。
2.parent为红色
此时可以肯定的是，parent的父结点肯定是红色，reparent的兄弟结点颜色不确定。
当parent为红色时，如何调整取决于parent的兄弟，也就是cur的uncle
(1)uncle为红色
调整后grandpa变成了红色，而grandpa的paren颜色不确定，所以需要以grandpa为cur，继续向上调整
(2)uncle不存在/uncle为黑（单旋的情况）
调整后原grandpa结点处的颜色不变，还是黑色，所以不用向上调整了
(3)uncle不存在/uncle为黑（双旋的情况）
调整后原grandpa结点处的颜色不变，还是黑色，所以不用向上调整了
tips：
- parent为红色时才需要调整
- uncle为红，则”两黑夹一红“
- uncle为黑，则先旋转，再“两红夹一黑”
