红黑树
目录
基本概念 #
二叉搜索树 #
二叉搜索树（又叫二叉查找树、二叉排序树），具有以下特点：
- 节点的左孩子的值小于节点本身；
- 节点的右孩子的值大于节点本身；
- 左右子树同样为二叉搜索树；
所以最终效果是:
- 节点左子树的所有节点的值都小于节点本身；
- 节点右子树的所有节点的值都大于节点本身；
- 对二叉搜素树的一次中序遍历就是一个递增有序序列
平衡二叉树(AVL) #
二叉平衡树是在二叉搜素树的基础上加上了限制：任意节点，左右子树的高度差不能超过1。这个约束常常借助左旋和右旋操作实现。
左旋 #
右旋 #
红黑树(带有自平衡功能的AVL树) #
底层的数据结构就是一个特殊的二叉排序树。
红黑树的规则特性 #
- 节点分为红色或者黑色
- 根节点必为黑色
- 叶子节点都为黑色，且为null
- 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）即不存在父子关系的两个红色节点
- 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点
- 新加入到红黑树的节点为红色节点
第3条的解释：叶子节点都为黑色，且都为null，我们在java中空置是null，所以我们能看到的都是红色的非叶子节点，但要知道它并不是叶子节点。
第6条的解释：新加入的节点为红色节点，为什么呢？从规则4中知道，当前红黑树中从根节点到每个叶子节点的黑色节点数量是一样的，此时假如新插入的是黑色节点的话，必然破坏规则(它所在的路径上会多出一个黑色节点)，但加入红色节点却不一定，除非其父节点就是红色节点才会破坏规则，因此加入红色节点，破坏规则的可能性小一些。
插入的情况分析 #
树为空的情况，直接插入
插入时父节点为黑色的情况，正常插入
插入时父节点为红色，且叔叔节点也为红色的时候。把父节点和叔叔节点设为黑色。把爷爷节点设为红色（爷爷节点为根节点的时候再设为黑色）。
插入时父节点是红色，叔叔节点不存在或是黑色时，且当前节点是右子树，以父节点做左旋，
父节点变成黑色，爷爷节点变为红色。
插入时父节点是红色，叔叔节点不存在或是黑色时，且当前节点是左子树，以父节点做右旋，
父节点变成黑色，爷爷节点变为红色。
删除情况分析 #
删除节点后，很可能会破坏这红黑树的特性，所以我们需要判断删除之后是否需要修复。
叶子节点的情况 #
删除的是红色节点：直接删除
删除的是黑色节点：
非叶子节点的情况 #
删除的是红色节点：
删除的是黑色节点：
与平衡二叉树的比较 #
RB-Tree和AVL树作为BBST，其实现的算法时间复杂度相同，AVL作为最先提出的BBST，貌似RB-tree实现的功能都可以用AVL树来代替，那么为什么还需要引入RB-Tree呢？
- 红黑树不追求"完全平衡"，即不像AVL那样要求节点的平衡因子达到平衡，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。
- 插入节点导致树失衡，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)
- 删除节点导致树失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！
- AVL的结构相较于RB-Tree更为平衡，插入和删除引起失衡，RB-Tree复衡效率更高；当然，由于AVL高度平衡，因此AVL的Search效率更高啦。
- 针对插入和删除节点导致失衡后的rebalance操作，红黑树能够提供一个比较"便宜"的解决方案，降低开销，是对search，insert ，以及delete效率的折衷，总体来说，RB-Tree的统计性能高于AVL.
总结：红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强。
红黑树的产生背景 #
从2-3树来看红黑树 #
一般我们接触最多的是二叉树，也就是一个父节点最多有两个子节点。2-3树与二叉树的不同之处在于，一个父节点可以有两个子节点，也可以有三个子节点，并且其也满足类似二叉搜索树的性质。还有最重要的，2-3树的所有叶子节点都在同一层，且最后一层不能有空节点，类似于满二叉树。
红黑树与2-3树的关系 #
现在我们对2-3树进行改造，改造成一个二叉树。怎么改造呢？对于2个节点的，保持不变；对于3个节点的，我们首先将3个节点的左侧的元素标记为红色
在2-3树中，根节点只能是2节点或者3节点，2节点与3节点在红黑树中的等价形式
理解：每个红色结点的两个子结点一定都是黑色。 从2-3树的角度来理解，红色节点对应2-3树中3节点左侧的元素，那么它的子节点要么是2节点，要么是3节点。无论是2节点还是3节点对应的节点颜色都是黑色的，这在性质2时已经讨论了。
理解：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。 性质5应该是红黑树最重要的一条性质了。2-3树是一颗绝对平衡的树，即2-3树中任意一个节点出发，到达叶子节点后所经过的节点数都是一样的。那么对应到红黑树呢？2-3树中2节点对应到红黑树便是一个黑色的节点，而3节点对应到红黑树是一个红色节点和一个黑色节点。所以，无论是2节点还是3节点，在红黑树中都会对应一个黑色节点。那么2-3树中的绝对平衡，在红黑树中自然就是任意一结点到每个叶子结点的路径都包含数量相同的黑结点了。