数据结构：红黑树原理与TreeMap、TreeSet

一、相关概念及性质

全文参考自《算法导论》

1.1 二叉搜索树

二叉搜索树(Binary Search Tree)又名二叉排序树、二叉查找树，
相比于普通二叉树，二叉搜索树的数据结构多一个双亲指针指向双亲结点，其结构为：

public static class BSTnode<E>{
   
    E data;     //数据域
    BSTnode<E> lchild;   //左指针
    BSTnode<E> rchild;   //右指针
    BSTnode<E> parent;   //双亲指针
}
1
2
3
4
5
6
7

二叉搜索树有着如下特点：
设x是二叉搜索树的一个结点。若y是x左子树中的一个结点，有y.data <= x.data;若y是x右子树中的一个结点，有y.data >= x.data。
通俗来说就是：左子树任意节点值小于根结点，右子树任意节点值大于根结点。
详见 二叉搜索树详解

1.2 平衡二叉(搜索)树

1）平衡二叉树是具有以下性质的二叉树：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
狭义上说的平衡二叉树是满足二叉搜索树性质的，也即叫做"平衡二叉搜索树"。
2）为何要平衡?
二叉搜索树的插入、删除、查找等几乎所有操作均依赖于树高$h$而非结点树$n$，为了让搜索树的效率提高，需要尽可能地让树的高度减小，这便是平衡的目的。

1.3 什么是红黑树

红黑树相比于二叉搜索树多了一个存储位置来表示结点颜色（RED或BLACK），但通过对红黑树中根结点到任一叶结点的简单路径上结点的颜色限制来保证红黑树是近似平衡的。
也可以说红黑树是一颗"弱平衡的二叉搜索树"

1.4 红黑树五条性质

红黑树需要保持"近似平衡"，则需要对红黑树进行一些定义与约束：
(1)每个结点是红色或者黑色
(2)根结点是黑色
(3)空结点是黑色
(4)若某结点是红色，则该结点两个子结点都是黑色
(5)对于某个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（这个数目称为树的"黑高"-BlackHigh）
如下图所示的红黑树是不允许出现的：

1.5 红黑树保证树高至多为$2\lg (n+1)$

根据4中的五条性质，可以保证红黑树的树高至多为$2\lg (n+1)$，也就保证了红黑树的各个操作时间复杂度是$\lg n$级别的，证明如下：
1）首先归纳法证明 -> 以x为根的结点至少有$2^{BlackHigh(x)}-1$个内部结点
$step1：$空结点包含$2^{BlackHigh(x)}-1=2^0-1$