开发者学堂课程【Java 高级编程：红黑树原理简介】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/20/detail/366
红黑树原理简介
内容介绍:
1. 二叉树的主要特点及介绍
2. 均衡二叉树
3. 红黑树
4. 数据插入平衡原则
5. 插入操作分析
6. 数据删除平衡修复
7. 红黑树的数据删除处理
一、二叉树的主要特点及介绍
通过整个的二叉树的实现相信已经可以清楚二叉树的主要特点:数据查询的时候可以提供更好的查询性能。但是，二叉树的结构是有明显缺陷的，例如:当二叉树结构改变的时候（增加或删除）就有可能出现不平衡的问题。
之前所谓的解决二叉树性能问题的方式最终全部都变为了 null，也就是说如果要想达到最良好效果的查询结果是一个平衡二叉树，同时所有的节点的层次深度应该相同
二、均衡二叉树
如果所有的数据按照以上的结构进行保存，那么二叉树的检索操作执行效率一定是最高的，可是你的树需要可以忍受频繁的增加或者是删除操作。所以针对于二叉树有了进一步的设计要求
三、红黑树
红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 o(logn)。
红黑树是在 1972 年由 Rudolf Bayer 发明的，当时被称为平衡二叉 B 树( symmetric binary B-trees )。后来，在1978年被 Leo J.Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树的本质就是在节点上追加了一个表示颜色的操作信息。
package cn.mldn . demo;
enum Color {
RED,BLACK ;
}
class BinaryTree{
private class Nbde {
private T data ;
private Node parent ;
private Node left ;
Node right ;
private color colo ;
}
}
public class avaAPIDemo {
public static void main(String[ ] args) {
{
}
|
|
|
对于 Node 节点中的颜色标记也可以使用 true 或 false 来实现，不一定非要使用枚举类。一个标准的红黑树的结构如下所示:
红黑树特点
l 每个节点或者是黑色，或者是红色
l 根根节点必须是黑色﹔
l 每个叶子节点是黑色﹔
l Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不
l 到黑色的叶子节点，反而看到每个叶子节点都是红色的;
l 如果一个节点是红色的，则它的子节点必须是黑色的;
l 从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以
l 连续的。若给定黑色节点的个数N，最短路径情况是连续的 N 个黑色，树的高度为 N一1;最长路径的情况为节点红黑相间，树的高度为 2(N - 1);
l 一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点数量;
l 成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定;
红色节点之后绝对不可能是红色节点，但是没有说黑色节点之后不允许是黑色节点，允许黑-黑连接，主要是利用这个红色节点与黑色节点实现均衡的控制。简单点理解红黑树的结构就是为了可以进行右旋的控制,以保证树的平衡性.
但是对于平衡性，还需要考虑数据增加的平衡以及数据删除的平衡，增加和删除都是需要对这棵树进行平衡修复的.
四、数据插入平衡原则
l 第一次插入，由于原树为空，所以只会违反红-黑树的规则所以只要把根节点涂黑即可;
l 如果插入节点的父节点是黑色的，那不会违背红-黑树的规则什么也不需要做﹔但是遇到如下三种情况时，就要开始变色和旋转了∶
l 插入节点的父节点和其叔叔节点(祖父节点的另一个子节点)均为红色的;
l 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。
l 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点;
在进行红黑树处理的时候为了方便操作都会将新的节点使用红色来进行描述，于是当设置根数据插入平衡处理规则节点的时候就会违反规则二,那么这个时候只需要将节点的颜色涂黑即可.
数据插入平衡处理规则1
插入节点的父节点和其叔叔节点（祖父节点的另一个子节点)均为红色的;
将当前节点【10节点】父节点【30节点】与叔叔节点【70节点】涂黑
数据插入平衡处理规则 2
插入节点的父节点和其叔叔节点（祖父节点的另一个子节点)均为红色的;
将当前节点【10节点】父节点【30节点】与叔叔节点【70节点】涂黑
数据插入平衡处理规则3
插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点，此时新节点为左节点，这样就可以按照情况二进行处理。
将新增节点【40节点】与父节点【30节点】进行左旋处理，将新节点变为左节点，随后参考规则2
五、插入操作分析
插入操作完整分析1（原始二叉树)
插入操作完整分析2(变色)
插入操作完整分析（右旋)
在红黑树进行修复处理之中，它需要根据当前节点以及当前节点的父节点和叔叔节点之间的颜色来判断树是否需要进行修复处理
六、数据删除平衡修复
（1）二叉搜索树的数据删除
1、如果待删除节点没有子节点，那么直接删掉即可;
2、如果待删除节点只有一个子节点，那么直接删掉，并用其子节点去顶替它;
3、如果待删除节点有两个子节点，这种情况比较复杂︰首选找出它的后继节点，然后处理“后继节点”和“被删除节点的父节点”之间的关系，最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。
七、红黑树的数据删除处理
l 删除操作后，如果当前节点是黑色的根节点，那么不用任何操作，因为并没有破坏树的平衡性，即没有违背红-黑树的规则。
l 如果当前节点是红色的，说明刚刚移走的后继节点是黑色的，那么不管后继节点的父节点是啥颜色，只要将当前节点涂黑就可以了，红-黑树的平衡性就可以恢复。
l 但是如果遇到以下四种情况，就需要通过变色或旋转来恢复红-黑树的平衡了∶
n 当前节点是黑色的，且兄弟节点是红色的（那么父节点和兄弟节点的子节点肯定是黑色的) ;
n 当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的两个子节点均为黑色的;当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的左子节点是红色，右子节点时黑色的;
n 当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的右子节点是红色，左子节点任意颜色。
红黑树数据删除修复情况四
当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的右子节点是红色，左子节点任意颜色。
将当前节点【30节点】的兄弟节点【70节点】涂成与父节点【50节点】相同的颜色，再把父节点【50节点】涂成黑色，把兄弟节点【70节点】的右子节点【80节点】涂黑，然后以当前节点的父节点【50节点】为支点进行左旋。
数据删除与平衡处理分析4（删除6节点)
在红黑树之中修复的目的是为了保证树结构中的黑色节点的数量平衡，黑色节点的数量平衡了,那么才可能达到 O(logn) 的执行性能,但是修复的过程一方面是红黑的处理,另一方面就是黑色节点的保存层次.
