红黑树是一种特殊的B树是B树种2-3-4树的一种特殊实现,红黑树保证了每个节点只会有两个子节点,通过对每个节点进行染色,然后通过不同颜色的节点组合来分别代表2-3-4的2节点、3节点、4节点树的情况。在学习红黑树之前,我们需要先去了解2-3-4树。
那么如果想要对红黑树有一个较为深刻的理解,我认为首先去理解其根源,也就是B树是必不可少的
树形结构首先可以分为等叉树和不等叉树,等叉树是每个节点的键值个数都相同、子节点个数也都相同,不等叉树是每个节点的键值个数不一定相同、子节点个数也不一定相同。
最简单的等叉树是二叉树,直接二叉树的作用并不大,我们一般会要求二叉树所有的节点按照一定的顺序排列,这样我们进行插入、删除、查找时效率就会非常高,我们把这样的树叫做二叉搜索树或者二叉查找树。它的具体定义是这样的,二叉搜索树,要么是个空树,要么符合以下几个条件:
经过这样定义之后,二叉树就变成了二叉搜索树,它的插入、删除、查找效率一般情况下都是O(logn)。
相较于等叉树,我们可以对不等叉树的节点键数值数和插入、删除逻辑添加一些特殊的要求使其能达到绝对平衡的效果,我们把这种树叫做 B树,全称Balance Tree,是一种自平衡树,它和等叉树最大的不同首先表现在存储结构上,等叉树上每个几点的键值数和分叉数都是相同的,而B树不是。如果某个B树上所有节点的分叉数最大值是m,则把这个B数叫做m阶B数。下面我们来看一下B树的具体定义:
B树看似5条定义很复杂,但实际上自己分析一下理解后会发现还是蛮简单的。第一条,对子节点数进行限制,这也是m阶B树m的由来,第二条,是用来限制树的紧凑性,避免树又高又长。第三条没什么好说的。第四条规定了B树是一个绝对平衡树不会退化为线性结构,所以B树的效率永远是O(logn)。第5条保证了B树的元素的有序,以便高效率的查找。
2-3-4树其实就是4阶的B树,目前网上讲的红黑树大多数就是2-3树或者是2-3-4树转化而成的。这里仅对2-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节点了,这个时候父节点就需要继续分裂,在往上的情况一次类推,进行递归分裂
相对于插入,B树的删除就相对复杂,需要分情况讨论
当删除节点是叶子节点的时候,又分为以下情况
直接删除即可,因为从一个非2节点中删除一个键值以后,并不违反B树的定义
这种情况又要分多种情况
当兄弟节点是非2节点,我们可以直接从兄弟节点借一个元素过来,让当前删除节点形成非2节点,这样情况就转换为了2.3.3.1的情况,直接删除要删除的节点既可
如果兄弟节点是2节点,那么此时就需要从父节点借元素了,待删除结点和父节点、兄弟节点构成一个4节点,然后将待删除节点删。
如果父节点是非2节点,那么借走就接走了,如果是2节点,借走了当前位置就空了,所以需要再从这个节点的兄弟或父节点借一个元素,如果直到根节点也没有找到一个非2节点,那么这个B树的高度就会减一。
通过上一节,我们了解了红黑树的前身或者说是其本源B树之后我们再来看红黑树,相信你能够更容易理解红黑树,看出其操作的底层逻辑
在讲解之前我先讲红黑树的类结构放出来
public class RedBlackBST<Key extends Comparable<Key>, Value> {
//很明显,这个常量用来代指红或黑
private static final boolean Red = true;
private static final boolean Black = false;
//根节点
private Node root;
//节点类结构
private class Node {
Key key;
Value value;
Node left, right, parent;
int N;
boolean color;
public Node(Key key, Value value, Node parent, int n, boolean color) {
this.key = key;
this.value = value;
N = n;
this.color = color;
this.parent = parent;
}
}
public RedBlackBST() {
}
//用来判断一个节点是还是黑色
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == Red;
}
}
红黑树,本质上其实就是将一个B树(我们这里讨论2-3-4树)转化为一个二叉树。那么如何去转化的同时又能继承B树绝对平衡性呢?答案就是通过染色和旋转,到这里打住,让我们先来看红黑树的定义
在解释这几个定义之前我们需要先来开2-3-4树中节点转化到红黑树中的形式是怎样的
首先我们要明白的是,在红黑树中,只有黑色节点才计入高度,红色节点代表着其和父节点的链接是红色的。
非2节点由黑色节点+红色节点组合的形式表示,红黑树对应到2-3-4树的节点组合中只会存在一个黑色节点。
3节点转换成红黑树就是一个黑色节点带着红色子节点的树,这个树可以是左倾的也可以是右倾的,根据节点的key来决定,在以2-3树为基础实现的红黑树中,我们一般只允许左倾或则右倾树存在,如果出现不允许的倾斜树情况,一般会通过旋转变色来调整。
先在我们再来来挨个看这5条定义
我们在对红黑树进行添加的时候,一开始按照二叉树的方式添加,每个新节点的初始元素为红色(root节点为黑色),当我们继续进行添加,发现当前的红黑树结构不符合定义时,我们就需要通过旋转和对节点变色来重新平衡红黑树。
先说旋转,红黑树的旋转分为左旋和右旋,我们先通过左旋来进行详细讲解。左旋就是一个节点绕着他的右子节点逆时针旋转,变成右子节点的左子节点,我们以下图为例
A进行左旋,变成B的左子节点,于此同时,B原先的左子树变成A的右子树,A的父节点变为B的父节点。
A的左子树依旧是A的左子树,B的右子树也依旧是B的右子树,不做变化。
这样,我们就完成了一次左旋,右旋则是绕则操作节点自身的子节点顺时针旋转,变成左子节点的右子树,左子节点的右子树迁移到操作节点的左子树,操作节点的父节点变成左子节点的父节点。原理一模一样。
当然,我们在旋转以后,如果不变色,结果肯定是不正确的,只有进行变色之后的红黑树才是正确的,由于变色有很多种情况,所以我们这里只举一个简单的例子,后面在讲解添加和删除的时候再进行细致列举。
首先我们这里有一个两个节点的二叉树,现在他是正确的,这个时候我们再插入一个新的节点3,那么根据二叉树的性质,插入后这个树会变成这个样子
当然,这个结果明显是错误的,其结构明显不符合我们我们在2.2.2中展示的任何一种形式,所以我们要通过旋转和变色变换为2.2.2中的哪几种形式。
首先这个组合在2-3-4树种是一个4节点,但是他的形态并不符合红黑树的节点,所以我们需要将它转换为已个合法的形态,先进行旋转,1节点左旋,这个时候结构对了,但是颜色不对,需要将2变色为黑色,而1变色为红色,这样我们的这个红黑树就完全符合定义了。
这就是一个最简单的旋转变色的红黑树自动平衡过程。
下面是左旋和右旋的JAVA代码实现,并没有添加变色,因为变色的逻辑并不是固定的故而我们将其解耦到其他方法中
//左旋
Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
if(h.right!=null){
h.right.parent = h;
}
x.parent = h.parent;
h.parent = x;
x.left = h;
if(x.left!=null){
x.left.parent = x;
}
if(x.parent!=null){
int cmp = x.parent.key.compareTo(x.key);
if(cmp>0) x.parent.left = x;
else x.parent.right = x;
}
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
show();
return x;
}
//右旋
Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
if(h.left!=null){
h.left.parent = h;
}
x.parent = h.parent;
h.parent = x;
x.right = h;
if(x.right!=null){
x.right.parent = x;
}
if(x.parent!=null){
int cmp = x.parent.key.compareTo(x.key);
if(cmp>0) x.parent.left = x;
else x.parent.right = x;
}
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
show();
return x;
}
红黑树的添加分为以下几种情况
这种情况无论是插入在左还是右,都可以直接插入,红黑树的正确性不会受到影响
在右侧插入
操作步骤:
1.节点1左旋在左侧插入
这种情况会比上面那种多一个步骤
1.节点3右旋,无需变色,这个操作主要是为了将情况转换为上面在右侧插入的情况,然后下面按照在右侧的情况处理即可其实这种情况和上面的处理逻辑是一样的,只不过左右是反过来的,就不再赘述了,大家自己举一反三即可。
这种时候,我们需要先进行变色,再插入,如下图(这里,我们默认,1节点是有父节点的,1节点非根节点)
2和3节点变黑色,1节点变红色,这个变化其实对应着2-3-4树的4节点插入,其实就是将一个4节点拆分开来,中间的节点向上和父节点组合,左右两边的节点分裂为两个单独的节点,然后再正常插入一个新的节点。红黑树也是这么个道理。
2、3节点变黑,形成单独的节点,而1节点则变红和父节点结合,那么这里我们要注意的是,1节点和父节点结合的时候,也相当于一次新的插入,相当于在1的父节点新插入一个红色,所以这个过程是递归的,一直向上传递,直到红黑树的结构符合定义为止。
到这里,红黑树的插入操作就结束了,以上的操作,只是单纯的一步操作,这些操作只是在插入之后对被插入节点红黑树的一个平衡,我们在进行旋转变色之后,很有可能上层的节点就又不符合定义了,这个时候我们就需要进行递归的旋转变色, 直到最后整个红黑树平衡。
下面扔代码
if (cmp < 0) h.left = put(h.left, h, key, val);
else if (cmp > 0) h.right = put(h.right, h, key, val);
else h.value = val;
//判断红黑,进行旋转,调整树的平衡
if (isRed(h.right) && isRed(h.right.right)) {
h.right.color = h.color;
h.color = Red;
h = rotateLeft(h);
}
if (isRed(h.right) && isRed(h.right.left)) {
//RL问题,先右旋,将问题转换为RR
h.right = rotateRight(h.right);
//变色
h.right.color = h.color;
h.color = Red;
//再左旋
h = rotateLeft(h);
}
if (isRed(h.left) && isRed(h.left.left)) {
h.left.color = h.color;
h.color = Red;
h = rotateRight(h);
}
if (isRed(h.left) && isRed(h.left.right)) {
//LR问题,先左旋,将问题转换为LL问题
h.left = rotateLeft(h.left);
//变色
h.left.color = h.color;
h.color = Red;
//再右旋
h = rotateRight(h);
}
h.N = size(h.left) + size(h.right) + 1;
return h;
}
欢迎点赞关注+转发!