红黑树以及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树的插入

节点分类

• 2节点：一个节点中有1个键值，2条链接
  
• 3节点：一个节点中有2个键值，3条链接
  
• 4节点：一个节点中有3个键值，4条链接
  

首先是2节点的插入，由于2-3-4树是4阶B树，最多可以有4条连接，一个节点最多有3个键值，所以这里直接添加即可

然后是3节点的插入，2节点插入之后，转化为4节点，仍保持一个节点的状态

4节点插入,由于2-3-4树是4阶B树，所以当对4节点插入的时候，就需要对4节点进行分裂，首先将中间的节点上升，然后,根据B树定义，将新增的节点和叶子的其中一个节点结合，形成一个3节点，比如，下图中要插入4,首先123分裂，之后4根据大小顺序，放在3的右边，和3形成一个3节点。

之后如果继续插入，第二层节点如果再形成4节点的情况下插入，那么分裂之后出来的节点，应该和父节点再构成节点

如果向上和父节点构成节点，但是父节点已经是4节点了，这个时候父节点就需要继续分裂，在往上的情况一次类推，进行递归分裂

1.4 2-3-4树的删除

相对于插入，B树的删除就相对复杂，需要分情况讨论
1.4.1 当删除节点是叶子节点

当删除节点是叶子节点的时候，又分为以下情况
1.4.1.1 当删除节点为非2节点

直接删除即可，因为从一个非2节点中删除一个键值以后，并不违反B树的定义
1.4.1.2 当删除节点为2节点

这种情况又要分多种情况
1.4.1.2.1 兄弟节点是非2节点

当兄弟节点是非2节点，我们可以直接从兄弟节点借一个元素过来，让当前删除节点形成非2节点，这样情况就转换为了2.3.3.1的情况，直接删除要删除的节点既可

1.4.1.2.2 兄弟节点是2节点

如果兄弟节点是2节点，那么此时就需要从父节点借元素了，待删除结点和父节点、兄弟节点构成一个4节点，然后将待删除节点删。
如果父节点是非2节点，那么借走就接走了，如果是2节点，借走了当前位置就空了，所以需要再从这个节点的兄弟或父节点借一个元素，如果直到根节点也没有找到一个非2节点，那么这个B树的高度就会减一。

1.4.2 如果删除节点是非叶子节点

• 如果被删除节点是非叶子节点，那么我们就需要找到他的后继元素，然后将后继元素的值覆盖被删除元素，再将后继元素删除即可
  
• 那么如何寻找后继节点呢？一般来说就是key大小最接近被删除元素的叶子节点中的元素，这个元素可以大于key也可以小于key，这个是我们可以自己定义，这里我们选小于被删除元素的那个。也就是左子树节点中最大的元素。
  

二、 红黑树

通过上一节，我们了解了红黑树的前身或者说是其本源B树之后我们再来看红黑树，相信你能够更容易理解红黑树，看出其操作的底层逻辑
在讲解之前我先讲红黑树的类结构放出来

1. public class RedBlackBST<Key extends Comparable<Key>, Value> {
3.     //很明显，这个常量用来代指红或黑
4.     private static final boolean Red = true;
6.     private static final boolean Black = false;
8.     //根节点
9.     private Node root;
12.     //节点类结构
13.     private class Node {
14.         Key key;
15.         Value value;
16.         Node left, right, parent;
17.         int N;
18.         boolean color;
20.         public Node(Key key, Value value, Node parent, int n, boolean color) {
21.             this.key = key;
22.             this.value = value;
23.             N = n;
24.             this.color = color;
25.             this.parent = parent;
26.         }
28.     }
30.     public RedBlackBST() {
32.     }
34.     //用来判断一个节点是还是黑色
35.     private boolean isRed(Node x) {
36.         if (x == null) return false;
37.         return x.color == Red;
38.     }
40. }

复制代码

2.1 红黑树的定义

红黑树，本质上其实就是将一个B树（我们这里讨论2-3-4树）转化为一个二叉树。那么如何去转化的同时又能继承B树绝对平衡性呢？答案就是通过染色和旋转，到这里打住，让我们先来看红黑树的定义

• 所有的节点不是黑色就是红色
  
• 根节点是黑色的
  
• 所有叶子节点是黑色的
  
• 从每个叶子到跟的所有路径上不能有两个连续的红色节点
  
• 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点
  

2.2 2-3-4树节点到红黑树的转换

在解释这几个定义之前我们需要先来开2-3-4树中节点转化到红黑树中的形式是怎样的
首先我们要明白的是，在红黑树中，只有黑色节点才计入高度，红色节点代表着其和父节点的链接是红色的。
非2节点由黑色节点+红色节点组合的形式表示，红黑树对应到2-3-4树的节点组合中只会存在一个黑色节点。
2.2.1 2节点转换


2.2.2 3节点转换

3节点转换成红黑树就是一个黑色节点带着红色子节点的树，这个树可以是左倾的也可以是右倾的，根据节点的key来决定，在以2-3树为基础实现的红黑树中，我们一般只允许左倾或则右倾树存在，如果出现不允许的倾斜树情况，一般会通过旋转变色来调整。

2.2.3 4节点转换


2.2.4 例子


2.3 红黑树定义解释

先在我们再来来挨个看这5条定义

• 第一条这个没什么好说的，红黑树红黑树，那肯定节点不是红色就是黑色
  
• 由于根节点必然是没有父节点的，而在上面我们所列举的转换形式中并没有红色节点为父节点的结构，所以根节点必然是黑色的
  
• 在红黑树中叶子节点会默认拥有两个为null的子节点，颜色自然是黑色
  
  
• 不允许又连续两个红色节点是为了限制红黑树的阶数为4，不允许出现2、3、4节点之外的节点类型
  
• 对应2-3-4树的第五条，保证了树的绝对平衡，对应到红黑树中只有黑色节点代表高度，所以只需要保证黑色节点的数目一致即可。
  

2.3.1 红黑树的旋转与变色

我们在对红黑树进行添加的时候，一开始按照二叉树的方式添加，每个新节点的初始元素为红色（root节点为黑色），当我们继续进行添加，发现当前的红黑树结构不符合定义时，我们就需要通过旋转和对节点变色来重新平衡红黑树。
2.3.2 红黑树的旋转

先说旋转，红黑树的旋转分为左旋和右旋，我们先通过左旋来进行详细讲解。左旋就是一个节点绕着他的右子节点逆时针旋转，变成右子节点的左子节点，我们以下图为例

A进行左旋，变成B的左子节点，于此同时，B原先的左子树变成A的右子树，A的父节点变为B的父节点。
A的左子树依旧是A的左子树，B的右子树也依旧是B的右子树，不做变化。
这样，我们就完成了一次左旋，右旋则是绕则操作节点自身的子节点顺时针旋转，变成左子节点的右子树，左子节点的右子树迁移到操作节点的左子树，操作节点的父节点变成左子节点的父节点。原理一模一样。
2.3.3 红黑树的变色

当然，我们在旋转以后，如果不变色，结果肯定是不正确的，只有进行变色之后的红黑树才是正确的，由于变色有很多种情况，所以我们这里只举一个简单的例子，后面在讲解添加和删除的时候再进行细致列举。

首先我们这里有一个两个节点的二叉树，现在他是正确的，这个时候我们再插入一个新的节点3，那么根据二叉树的性质，插入后这个树会变成这个样子

当然，这个结果明显是错误的，其结构明显不符合我们我们在2.2.2中展示的任何一种形式,所以我们要通过旋转和变色变换为2.2.2中的哪几种形式。

首先这个组合在2-3-4树种是一个4节点，但是他的形态并不符合红黑树的节点，所以我们需要将它转换为已个合法的形态，先进行旋转，1节点左旋，这个时候结构对了，但是颜色不对，需要将2变色为黑色，而1变色为红色，这样我们的这个红黑树就完全符合定义了。

这就是一个最简单的旋转变色的红黑树自动平衡过程。
下面是左旋和右旋的java代码实现，并没有添加变色，因为变色的逻辑并不是固定的故而我们将其解耦到其他方法中

1.     //左旋
2.     Node rotateLeft(Node h) {
3.         Node x = h.right;
4.         h.right = x.left;
5.         if(h.right!=null){
6.             h.right.parent = h;
7.         }
8.         x.parent = h.parent;
9.         h.parent = x;
10.         x.left = h;
11.         if(x.left!=null){
12.             x.left.parent = x;
13.         }
14.         if(x.parent!=null){
15.             int cmp = x.parent.key.compareTo(x.key);
16.             if(cmp>0) x.parent.left = x;
17.             else x.parent.right = x;
18.         }
19.         x.N = h.N;
20.         h.N = 1 + size(h.left) + size(h.right);
21.         show();
22.         return x;
23.     }
25.     //右旋
26.     Node rotateRight(Node h) {
27.         Node x = h.left;
28.         h.left = x.right;
29.         if(h.left!=null){
30.             h.left.parent = h;
31.         }
32.         x.parent = h.parent;
33.         h.parent = x;
34.         x.right = h;
35.         if(x.right!=null){
36.             x.right.parent = x;
37.         }
38.         if(x.parent!=null){
39.             int cmp = x.parent.key.compareTo(x.key);
40.             if(cmp>0) x.parent.left = x;
41.             else x.parent.right = x;
42.         }
43.         x.N = h.N;
44.         h.N = 1 + size(h.left) + size(h.right);
45.         show();
46.         return x;
47.     }

复制代码

2.4 红黑树的添加

红黑树的添加分为以下几种情况
2.4.1 在黑色节点下面插入

这种情况无论是插入在左还是右，都可以直接插入，红黑树的正确性不会受到影响
2.4.2 在红色节点下插入且被插入节点无兄弟节点

2.4.2.1 当被插入的节点是右子节点


在右侧插入

操作步骤：

• 节点1左旋
  
  
• 变色，1变色为红色， 2变色为黑色
  
  

在左侧插入

这种情况会比上面那种多一个步骤

• 节点3右旋，无需变色，这个操作主要是为了将情况转换为上面在右侧插入的情况，然后下面按照在右侧的情况处理即可
  
  )
  
• 节点1左旋
  
  
• 变色，1变色为红色，2变色为黑色
  
  

2.4.2.2 当被插入节点是左子节点

其实这种情况和上面的处理逻辑是一样的，只不过左右是反过来的，就不再赘述了，大家自己举一反三即可。
2.4.3 在红色节点下插入且被插入节点有兄弟节点

这种时候，我们需要先进行变色，再插入，如下图（这里，我们默认，1节点是有父节点的，1节点非根节点）

2和3节点变黑色，1节点变红色，这个变化其实对应着2-3-4树的4节点插入，其实就是讲一个4节点拆分开来，中间的节点向上和父节点组合，左右两边的节点分裂为两个单独的节点，然后再正常插入一个新的节点。红黑树也是这么个道理。
2、3节点变黑，形成单独的节点，而1节点则变红和父节点结合，那么这里我们要注意的是，1节点和父节点结合的时候，也相当于一次新的插入，相当于在1的父节点新插入一个红色，所以这个过程是递归的，一直向上传递，直到红黑树的结构符合定义为止。

到这里，红黑树的插入操作就结束了，以上的操作，只是单纯的一步操作，这些操作只是在插入之后对被插入节点红黑树的一个平衡，我们在进行旋转变色之后，很有可能上层的节点就又不符合定义了，这个时候我们就需要进行递归的旋转变色， 直到最后整个红黑树平衡。
下面扔代码
代码

1.     private void put(Key key, Value val) {
2.         root = put(root, null, key, val); //进行插入，返回根节点作为查询遍历的起始节点保存
3.         root.color = Black; //根节点的颜色必然是黑色
4.     }
6.     private Node put(Node h, Node p, Key key, Value val) {
7.         if (h == null) {
8.             return new Node(key, val, p, 1, Red);
9.         }
10.         //当插入的时候，发现路径上有-4节点
11.         if (isRed(h.left) && isRed(h.right)) flipColors(h);
12.         //递归搜索树，直到找到相同的key，修改，或者搜索到底层，进行插入。
13.         int cmp = key.compareTo(h.key);
14.         if (cmp < 0) h.left = put(h.left, h, key, val);
15.         else if (cmp > 0) h.right = put(h.right, h, key, val);
16.         else h.value = val;
18.         //判断红黑，进行旋转，调整树的平衡
19.         if (isRed(h.right) && isRed(h.right.right)) {
20.             h.right.color = h.color;
21.             h.color = Red;
22.             h = rotateLeft(h);
23.         }
24.         if (isRed(h.right) && isRed(h.right.left)) {
25.             //RL问题，先右旋,将问题转换为RR
26.             h.right = rotateRight(h.right);
27.             //变色
28.             h.right.color = h.color;
29.             h.color = Red;
30.             //再左旋
31.             h = rotateLeft(h);
32.         }
33.         if (isRed(h.left) && isRed(h.left.left)) {
34.             h.left.color = h.color;
35.             h.color = Red;
36.             h = rotateRight(h);
37.         }
38.         if (isRed(h.left) && isRed(h.left.right)) {
39.             //LR问题，先左旋，将问题转换为LL问题
40.             h.left = rotateLeft(h.left);
41.             //变色
42.             h.left.color = h.color;
43.             h.color = Red;
44.             //再右旋
45.             h = rotateRight(h);
46.         }
48.         h.N = size(h.left) + size(h.right) + 1;
50.         return h;
51.     }

复制代码

结语

本章中我们学习了红黑树的起源，B树，然后学习了红黑树的插入。由于红黑树的删除较为复杂，我们放到下一章在进行讲解

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！