由红黑树原理到 java中 tree的原理

2019-05-11 本文已影响0人输入昵称就行

在java语言中，TreeMap TreeSet 等都是基于红黑树的原理实现的，主要是用它来存储有序的数据，时间复杂度是O(lgn)，效率非常之高，在学习这些数据集合的时候，了解到红黑树，由此对红黑树进行了深入的学习。

1、文中提到的给一个节点到兄弟，或者拿一个节点过来，其实都是很多文章中提到了左旋与右旋的目的；
2、我这里面画的图真的不如维基百科的图，主要是传递一些我总结的的理解方式

红黑树是基于二叉排序树的:

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点（no duplicate nodes）

红黑树的有效条件：

节点是红色或黑色
根节点是黑色
每个叶子节点(NIL , NULL) 是黑色的
每个红色节点的两个子节点是黑色，也就是没有两个相连节点都是红色的
从任何一个节点到其下面的每个叶子节点的路径上都包含相同数目的黑色节点

推论：
    - 每个路径上的 黑节点>=红节点 数量；
    - 从根到叶子的最长路径 max <= min 从根到叶子的最短路径

一、红黑数新增元素

红黑树新增节点有可能破坏的规则是:不能有相连2个红点！！！！！！

新增节点的需要遵循2个条件：
- 红黑树是基于二叉排序树的，新增元素必然在叶子上,且按照排序添加到应该的节点下，这是最基本的
- 红黑树的新增的元素必须是红色的，这是为了不破坏红黑树第5个有效条件
- 基于上面基本条件，新增节点只有两种情况，
①：树的第一个元素，成为根
②：加到黑点下面，没有破坏特性
③：加到红色点的下面，破坏了红黑树特性（这才是最需要修复树的）

①.树的第一个元素，成为根

situation1.jpg

②.加到黑点下面，没有破坏特性

situation2.jpg

③.加到红色点的下面

这种情况，我的理解就是，如果加到父节点红点下面，那如果需要保持红黑树特性,爷爷节点一定是黑色的，也就只有叔节点是红色与黑色两种情况了；
既然父节点这边有2个红色的相连，那我就给一个红色点给叔节点那边就行了,兄弟有难同担嘛。
如果叔叔是红色，我给一个红色的过去，那又会造成叔节点那边有2个红点相连了，叔节点就有麻烦了，那怎么办呢？老爸和叔叔都搞不定了那就让爷爷去搞定吧。
如果叔叔是黑色，那给一个红色的给叔节点，不会给叔节点造成麻烦，那就不需要爷爷插手了，就搞定了。

以下的所有的例子都可以归于以上的情况

1)如果新增的元素存在父元素，父元素是红色，叔元素是红色的

situation3.jpg

2)如果新增的元素存在父元素，父元素是红色，叔元素是黑色的

此处需要说明：由于二叉树的特性，新增的节点一定替代了原有的叶子节点位置，所以第一次出现当前的情况时，为了保证第五个条件成立，叔节点一定是NiL，
只有之后尾部递归到上面去才会出现叔节点可能存在不是叶子的情况，处理方法都是一样的)
维基百科给的例子没有特殊说明，我开始误解了

situation4.jpg

3)在第四种情况中，只举例说明了右旋，左旋如图

situation5.jpg

4)前面的2种情况都是 N-P-G在一条直线上，实际上会存在不在条直线上的情况

situation6.jpg

situation7.jpg

5)执行了上面的操作之后，就N,P的身份调换， P理解为新增的N'，N理解为'，则N', P', G 在一条直线上，就可以按照之前的逻辑进行处理了

二、红黑数删除元素

红黑树删除可能破坏的红黑树规则是：任意节点到叶子点的所有路径上黑点数量相同！！！！！！！

在确定最终删除节点位置前，需要做如下操作:
1. 在树中找到需要删除的点,如果不存在,则直接结束
2. 如果存在的话,则可以执行删除操作。

用图来说明删除前预处理方法:

图中说明了2种预处理方法
1. 用左子树最大值顶替删除点的值，删除左子树最大值位置的点
2. 用右子树最小值顶替删除点的值，删除右子树最小值位置的点
  
  pre_sulotion.jpg
当做完这些预处理的之后，会发现一个有趣的现象,新的要删除的点的位置，不可能有同时有2个子节点，必然至少有一个儿子是叶子(nil)节点
1. 其中就只有两种情况: ① 2个叶子(null)儿子； ② 一个儿子,一个叶子(nil),这一种又更有趣了, 儿子必然是红色的，删除点必然是黑色的
  
  pre_se.jpg

仔细看之后，发现只有①的情况需要做如下处理
第②种就简单了，直接用其中的存在的儿子节点替换到要删除的位置并且颜色变为黑色就行了；再删除掉需要删除的点
所以这下面的逻辑都是第①种的情况下进行处理

1.删除点是红色

没啥可说明了的，删除红色的，不影响红黑树结构，直接删除就行了

2.删除点是黑色

删除黑色点，经过该黑色点的路径上的黑色点必然少一个，就会造成整棵树不平衡，那有什么办法呢；
- （1）第一种办法就是让其他的路径上的黑色点也减少一个黑色点，那样所有的路径就平衡了；
- （2）第二种办法就是从兄弟节点上拿一个红色的过来，放到删除点的路径上，并且设置为黑色，
 这样的花即没有减少兄弟节点路径的黑点数量，也填补了删除黑点的数量，同样达到了红黑树平衡

2.1.删除点是黑色，兄弟节点没有红点可拿

兄弟没有红点可拿，那没关系，那就继续往上去找找叔叔节点分支拿红点，还没有的话，继续往上找....
- 每一次找不到，也要保证每个子树平衡，按下图的方式修复树,最终如果找到了根，修复之后，就是上面的（1）的结果
- 如果找到了，那就转到2.2的处理方法了 ===>2.2

delete_case1.jpg

2.2.删除点是黑色，兄弟节点有红点可拿

兄弟节点有红点拿，虽然排列的可能性很多，但是最终的效果就是兄弟分支少了一个红色的，当前删除的分支多了一个黑色的，不需要往上递归了，
直接就搞定了,修复之后，就是上面的（2）的结果
唯一要考虑的就是从兄弟那里拿走一个红色，怎么让树仍然保持二叉排序树的性质
下图中举例了一些例子

delete-case2.jpg

三、java代码实现

RBTree项目地址

总结

java 中红黑树的应用非常多，treeMap treeSet 就连java8中的HashMap节点也在特殊条件下使用红黑树存储，而java7中还是链式存储，这是一个非常大的改变

由红黑树原理到 java中 tree的原理