红黑树

传统二叉树的问题

  通过实现二叉树，了解了二叉树的主要特点：数据查询的时候可以提供更好的查询性能，但是这种原始的二叉树结构是有明显缺陷的，例如，当二叉树结构发生改变时（新增或删除）就有可能出现不平衡的问题。

传统二叉树问题

  之前解决二叉树性能问题的方式最终全部都失效了，因此想要达到性能良好的二叉树，那么它首先得是一个均衡二叉树，同时所有节点的层次深度都应该相同。

均衡二叉树
  如果所有的数据都按照以上的结构进行保存，那么二叉树的检索操作执行效率一定是最高的，可是这棵树就需要经受住频繁的新增或者是删除操作，所以针对于二叉树有了进一步的要求 。

红黑树介绍

  红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为“O(logn)”。
  红黑树是在1972年由Rudolf Bayer（鲁道夫·拜尔(Rudolf Bayer, 1939-)计算机学家，慕尼黑工业大学教授）发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被Leo J.Guibas和Robert Sedgewick修改为如今的“红黑树”。
  红黑树的本质就是在节点上追加了一个表示颜色的操作信息而已。

private class Node {
    private Comparable<T> data;//存放Comparable,可以比较大小
    private Node parent;//父节点
    private Node left;//左子树
    private Node right;//右子树
//    private boolean isRed;//节点颜色，true为红色，false为黑色
    private Color color;//节点颜色
}
enum Color{
    RED,BLACK;
}

  对于Node节点中的颜色标记可以使用枚举或boolean值来实现。一个标准的红黑树的结构如下所示：

红黑树基本结构示意图

红黑树特点（规则）

1、任意一个节点不是黑色就是红色；
2、根节点必须是黑色；
3、每个叶子节点必须是黑色；
  - Java实现的红黑树将使用null来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的；
4、如果一个节点时红色的，则它的子节点必须是黑色的，黑色节点的子节点可以为黑色；
  - 从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。若给定黑色节点的个数N，最短路径情况是连续的N个黑色，树的高度为N-1；最长路径的情况为节点红黑相间，树的高度为2(N-1)；
5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点数量；
  - 成为红黑树最主要的条件，后续的插入、删除操作都是为了遵守这个规定；

  主要利用这个红色节点与黑色节点实现均衡控制，简单点理解红黑树的结构就是为了可以进行左旋和右旋控制以保证树的平衡性。

红黑存在的意义

  但是对于平衡性，还需要考虑数据增加的平衡以及数据删除的平衡，增加和删除时都需要对树结构进行平衡修复。

数据插入平衡修复

1、新增节点颜色初始默认为红色；
2、第一次插入，由于原树为空，所以只会违反红黑树的规则2，所以只要把根节点变为黑色即可；
3、插入节点的父节点是黑色的，那不会违背红黑树的规则，不需要变色；
4、插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的，则父节点和叔叔节点都需要变为黑色，祖父节点要变为红色；

规则4局部分析示意图

5、插入节点的父节点是红色，叔叔节点时黑色，且插入节点是其父节点的左子节点，则将父节点和祖父节点颜色互换，随后将祖父节点修改为父节点的右子节点（右旋）；

规则5局部分析示意图
6、插入节点的父节点是红色，叔叔节点时黑色，且插入节点是其父节点的右子节点，则将父节点设置为的左子节点，插入节点将代替父节点的原始节点位置（左旋），然后使用规则4完成插入修复。
规则6局部分析示意图

案例分析：插入操作完整分析
  在红黑树进行修复处理之中，它需要根据当前节点以及当前节点的父节点和叔叔节点之间来推断树结构是否需要进行修复。

数据删除平衡修复

1、删除操作后，如果当前节点（删除后重新保存的节点）是黑色的根节点，则无法操作；
2、如果当前节点为红色的，则标明刚刚移动的后继节点是黑色的，不管后继节点的父节点是什么颜色，只要将当前节点变黑即可；
3、当前节点是黑色的，且兄弟节点是红色的（父节点和兄弟节点的子节点肯定为黑色的）；

规则3局部分析示意图

4、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的两个子节点均为黑色的；

规则4局部分析示意图
5、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的左子节点是红色的，右子节点是黑色的；
规则5局部分析示意图
6、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的右子节点是红色的，左子节点是任意颜色；
规则6局部分析示意图

案例分析：数据删除与平衡处理分析
  在红黑树之中，修复的目的是为了保证树结构中的黑色节点数量平衡，已达到“O(logn)”的执行性能，但是修复的过程一方面是红与黑的处理，另一方面就是子节点的保存层次。