红黑树以及JAVA实现 _红黑树

前言红黑树是一种特殊的B树是B树种2-3-4树的一种特殊实现，红黑树保证了每个节点只会有两个子节点，通过对每个节点进行染色，然后通过不同颜色的节点组合来分别代表2-3-4的2节点、3节点、4节点树的情况。在学习红黑树之前，我们需要先去了解2-3-4树。
一、 B树那么如果想要对红黑树有一个较为深刻的理解，我认为首先去理解其根源，也就是B树是必不可少的
1.1 概念树形结构首先可以分为等叉树和不等叉树，等叉树是每个节点的键值个数都相同、子节点个数也都相同，不等叉树是每个节点的键值个数不一定相同、子节点个数也不一定相同。
最简单的等叉树是二叉树，直接二叉树的作用并不大，我们一般会要求二叉树所有的节点按照一定的顺序排列，这样我们进行插入、删除、查找时效率就会非常高，我们把这样的树叫做二叉搜索树或者二叉查找树。它的具体定义是这样的，二叉搜索树，要么是个空树，要么符合以下几个条件:

左子树如果存在的话，左子树所有节点的键值都要小于根节点的键值
右子树如果存在的话，右子树所有节点的键值都要大于根节点的键值
它的所有子树也都要符合前面的两个条件(前面的小于同时换成大于也成立) 。

经过这样定义之后，二叉树就变成了二叉搜索树，它的插入、删除、查找效率一般情况下都是O(logn) 。
相较于等叉树，我们可以对不等叉树的节点键数值数和插入、删除逻辑添加一些特殊的要求使其能达到绝对平衡的效果，我们把这种树叫做 B树，全称Balance Tree，是一种自平衡树，它和等叉树最大的不同首先表现在存储结构上，等叉树上每个几点的键值数和分叉数都是相同的，而B树不是。如果某个B树上所有节点的分叉数最大值是m，则把这个B数叫做m阶B数。下面我们来看一下B树的具体定义：

所有节点最多有m个子节点
非根非叶子结点至少有m/2(向上取整)个子节点
根节点至少有两个子节点(除非总结点数不足3个)
所有叶子节点都在同一层
任意节点如果有k个键值，则有k+1个子节点指针，键值要按照从小到大排列，子节点数上所有的键值都要在对应的两个键值之间

B树看似5条定义很复杂，但实际上自己分析一下理解后会发现还是蛮简单的。第一条，对子节点数进行限制，这也是m阶B树m的由来，第二条，是用来限制树的紧凑性，避免树又高又长。第三条没什么好说的。第四条规定了B树是一个绝对平衡树不会退化为线性结构，所以B树的效率永远是O(logn) 。第5条保证了B树的元素的有序，以便高效率的查找。
1.2 2-3-4树2-3-4树其实就是4阶的B树，目前网上讲的红黑树大多数就是2-3树或者是2-3-4树转化而成的。这里仅对2-3-4树进行讲解
1.3 2-3-4树的插入节点分类