红黑树

二叉树 对比

+ 二叉搜索树

+ 优点：

• 可以快速地找到给定关键字的数据项并且可以快速地插入和删除数据项.

+ 缺点

• 如果插入的数据是==有序==的数据，树的深度会很大，反而影响效率；

+ 非平衡树

• 比较好的二叉搜索树数据应该是左右分布均匀的；

• 但是插入连续数据后，==分布的不均匀==，我称这种树为==非平衡树==；

• 对于一棵平衡二叉树来说，插入/查找等操作的效率是O(logN)；

• 对于一棵非平衡二叉树，相当于编写了—个链表，查找效率变成了O(N)。

+ 为了能以较快的时间O(logN)来操作一棵树，我们需要保证树总是平衡的:

• 至少大部分是平衡的那么时间复杂度也是接近O(logN)的；

• 也就是说树中每个==节点左边的子孙节点==的个数应该尽可能的==等于==，==右边的子孙节点==的个数；

• 常见的平衡树有哪些呢?

+ AVL树

AVL树是最早的—种平衡树.它有些办法保持树的平衡(每个节点多存储了一个额外的数据)；

因为AVL树是平衡的所以时间复杂度也是O(logN)；

但是，每次==插入/删除==操作相对于红黑树==效率都不高==，所以整体效率==不如红黑树==。

+ 红黑树

红黑树也通过一些特性来保持树的平衡；

因为是平衡树，所以时间复杂度也是在O(logN)；

另外插入/删除等操作，红黑树的性能要优于AVL树，所以现在平衡树的应用基本都是红黑树。

二、特性

+ 红黑树，除了符合二叉搜索树的基本规则外，还添加了一下特性

1. 节点是红色或黑色。
2. ==根节点是黑色==。
3. 每个==叶子节点==都是==黑色==的空节点(NIL节点)
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上==不能有两个连续==的==红色==节点)
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

+ 红黑树的关键特性:

1. 从根到叶子的==最长可能路径==，不会超过==最短可能路径==的==两倍长==;
2. 结果就是这个树基本是平衡的；
3. 虽然没有做到绝对的平衡，但是可以保证在最坏的情况下，依然是高效的；

+ 为什么可以做到 最长路径不超过最短路径的两倍 呢?

• 性质4决定了路径==不能==有两个==相连==的==红色节点==；
• 最短的可能路径都是黑色节点；
• 最长的可能路径是红色和黑色交替；
• 性质5==所有路径==都有==相同数目==的==黑色==节点；
• 这就表明了没有路径能多余任何其他路径的两倍长。

+ 插入一个新节点时，有可能树不再平衡，可以通过三种方式的变换，让树保持平衡

• 换色-左旋转一右旋转

1.变色

• 为了重新符合红黑树的规则，尝试把==红色==节点==变==为==黑色==，或者把==黑色==节点==变==为==红色==

+ 插入的 ==新的节点== 通常都是 ==红色==节点.

• 因为在插入节点为红色的时候，有可能插入一次是不违反红黑树任何规则的
• 而 插入黑色节点，必然会导致有一条路径上多了黑色节点这是很难调整的
• 红色节点 可能==导致==出现==红红相连== 的情况，但是这种情况可以通过 ==颜色调换==和==旋转== 来调整

2.旋转

旋转后，依然符合二叉搜索树的特性

• 左旋转：

  • ==逆时针==旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子

  • 

  • 图中，身为右孩子的Y取代了X的位置，而X变成了Y的左孩子。此为左旋转

  • 不影响子节点：b节点，旋转前后，都满足 x < b < y

• 右旋转：

  • ==顺时针==旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子
  • 
  • 图中，身为左孩子的Y取代了X的位置，而X变成了Y的右孩子。此为右旋转
  • 不影响子节点：c节点，旋转前后，都满足 y < c < x

• 接下来,讨论一下插入的情况:
  设要插入的节点为N,其父节点为P
  其祖父节点为G,其父亲的兄弟节点为U(即P和U是同一个节点的子节点)

• 情况一：(简单变色即可)
  新节点N位于树的根上,没有父节点
  这种情况下,我们直接将红色变换成黑色即可,这样满足性质2

• 情况二：(不用变)
  新节点的父节点P是黑色
  性质4没有失效(新节点是红色的),性质5也没有任何问题
  尽管新节点N有两个黑色的叶子节点nil但是新节点N是红色的,所以通过它的路径中黑色节点的个数依然相同,满足性质5

• 情况三：
  P为红色，U也是红色，G是黑色（父红叔红祖黑 =》 父黑叔黑 祖红）

• 操作方案
  将P和U变换为黑色,并且将G变换为红色
  现在新节点N有了一个黑色的父节点P，所以每条路径上黑色节点的数目没有改变；
  而从更高的路径上必然都会经过G节点所以那些路径的黑色节点数目也是不变的.符合性质5.

• 可能出现的问题
  但是，N的祖父节点G的父节点也可能是红色,这就违反了性质3,可以递归的调整颜色.
  但是如果递归调整颜色到了根节点,就需要进行旋转了,待会儿我们的例子中会遇到这个问题.

• 情况四：
  N的叔叔∪是黑节点,且N是左孩子；（父红，叔黑，祖父黑，N左）

• 操作方案
  对祖父节点G进行依次右旋转
  在旋转查收的树中,以前的父节点P现在是新节点以前祖父节点G的父节点
  交换以前的父节点P和祖父节点G的颜色(P为黑色,G变成红色——G原来一定是黑色,为什么?)
  B节点向右平移,成为G节点的左子节点

• 情况五
  N的叔叔U是黑色节点,且N是有孩子.（父红叔黑祖父黑，N右）

• 旋转
  以P为根，左旋转
  将P作为新插入的红色接地那考虑即可

• 操作方案
  对P节点进行依次左旋转,形成情况四的结果.
  对祖父节点G进行一次右旋转,并且改变颜色即可