B树和红黑树

大家好，我是讯享网，很高兴认识大家。

讯享网

给定一个假想出来的节点都是黑色节点

这是为了让这棵树变成真二叉树

即是要么度为0 要么度为2

懵逼了。。。。。。。。

先学B树：

解释一下：为什么说它拥有二叉搜索树的一些性质？

看3阶B树：

比23小的都在左边处于比23大但比30小的在中间

比30大的在右边

还有一点：

这个m的意思就是这个树的节点最多拥有m个子节点

向上取整和向下取整的符号：

1.这是向上取整

2.这是向下取整

数据库中的B树：一般是200到300阶左右

把二叉搜索树某些父子节点合并就可能会得到一颗B树

58比40大那么去右边比60小那么去左边

发现比50 55大那么排到55后面

我们前面性质可知：

4阶B树最多一个节点接入3个节点

当我们插入98时最后一个段变成了4个节点那么会导致上溢

当插入34发现满了之后上溢

那么我们把这一行节点的中间节点给它合并到父节点处

若当还是上溢的时候

同理把中间元素40与上面父节点合并即可

删除：

其实真正被删除的还是叶子节点中的节点

删除可能会产生下溢：

下溢的处理方法：

上溢会使B树高度增加

下溢会使B树变矮

4阶B树：

红黑树：

这棵不是红黑树：

因为不满足性质：因为我们红黑树会模拟一个虚拟节点是假设的是不存在的

但是我们在找路径的时候也要找这一条路径

红黑树代码基础架构：

package BinaryTree; import java.util.Comparator; public class RBTree<E> extends BST<E>{ / * 红黑树需要染色 */ private static final boolean RED=false; private static final boolean BLACK=true; public RBTree() { this(null); } public RBTree(Comparator<E> comparator) { super(comparator); } / * 创建一个染色的方法 封装起来 */ private Node<E> color(Node<E> node,boolean color){ if(node==null){ return null; } ((RBNode<E>)node).color=color; return node; } / *染色成红色 黑色 */ private Node<E> red(Node<E> node){ return color(node,RED); } private Node<E> black(Node<E> node){ return color(node,BLACK); } / * 传进来一个节点 判断是什么颜色 */ private boolean colorOf(Node<E> node){ //如果是null那么在红黑树中默认是BLACK颜色 //不为空 那么就看看它到底是什么颜色 return node==null?BLACK:((RBNode<E>)node).color; } / *你是否为黑色？ */ private boolean isBlack(Node<E> node){ return colorOf(node)==BLACK; } / *你是否为红色？ */ private boolean isRed(Node<E> node){ return colorOf(node)==RED; } / *开创一个内部类 */ private static class RBNode<E> extends Node<E> { boolean color; public RBNode(E elements, Node<E> parent) { super(elements, parent); } } }

讯享网

在BinaryTree中：

讯享网 / *为了写红黑树 * 我们要寻找它的兄弟节点 sibling */ public Node<E> sibling(){ //当前节点是父节点的左子树时 //兄弟节点一定是父节点的右子树 if(isLeftChild()){ return parent.right; } if(isRightChild()){ return parent.left; } return null; }

红黑树根节点必然是黑色

当我们添加一个元素的时候

把红黑树看成一个B树

B树中我们只能添加到叶子节点在红黑树中我们只可添加到最后一排

一共有2+2+1+2+2+1+2=12种情况

前面四种添加不用做任何处理也就是当父节点是黑色时

后面八种添加要进行相应的处理

这八种我们分类处理：

第一类：

当添加的是52 60这两个红色节点的时候

依照性质：不可以有两个节点连续是红色

举个实例：添加52这个节点：

第一步：把50染成黑色 46染成红色

第二步：对46进行左旋转操作因为增加的节点是RR

之后更新父关系让38指向50

这一种添加是LR 或RL

还是拿一个实例进行举例：

当我们添加节点48的时候：

首先把48染成黑色然后把46染成红色

为什么？因为在对parent进行单旋对grand也进行旋转之后 48会成为根节点与38相连

38为红色因此48为黑色

因此两个子节点应该是红色

uncle节点：叔父节点；即是父节点的兄弟节点

ok：

以上两类添加情况：叔父节点都不是红色即是黑色

举个例子：48的叔父节点是46左子节点为null

我们假设为是一个黑色的空结点

因此第三类与前一类的分界条件：叔父节点是否为红色

第二类：：uncle是RED

其实这里我们图省略了一开始的80这个红色节点

当25上去之后 25 38 55 80发生上溢

那么38先上去并且38染成黑色 38成为根节点

注意：

继承关系

我们再创建一个BBST存放旋转的操作并且让BBST继承BST

因为AVL和RBTree都存在旋转的操作并且让AVL RBTree继承BBST

核心代码：

重写addafter:

 / *重写添加之后的操作 */ @Override//node这里是添加的元素 protected void addafter(Node<E> node) { Node<E> parent = node.parent; //添加的是根节点 或者递归调用上溢到了根节点 if (parent == null) { black(node); return; } //如果父节点是黑色 那么直接返回即可 if (isBlack(parent)) { return; } //叔父节点 Node<E> uncle = parent.sibling(); //祖父节点 Node<E> grand = parent.parent; if (isRed(uncle)) { black(parent);//把parent染成黑色 black(uncle);//叔父同 red(grand);//祖父染成red色 染色完成之后当作新添加的节点向上合并 addafter(grand);//递归进行 直到添加完成 return; } //叔父节点不是红色 //一下注释的代码 表示是存在重复的 // 可以简洁写出来成一句放在前面即可 if (parent.isLeftChild()) {//L red(grand); if(node.isLeftChild()){//LL black(parent); //red(grand); //rotateright(grand); } else {//LR black(node); //red(grand); rotateleft(parent); //rotateright(grand); } rotateright(grand); } else {//R red(grand); if(node.isLeftChild()){//RL black(node); //red(grand); rotateright(parent); //rotateleft(grand); } else {//RR black(parent); //red(grand); //rotateleft(grand); } rotateleft(grand); } }

这个代码这样写更加清晰：

讯享网 //叔父节点不是红色 if (parent.isLeftChild()) {//L if(node.isLeftChild()){//LL black(parent); red(grand); rotateright(grand); } else {//LR black(node); red(grand); rotateleft(parent); rotateright(grand); } } else {//R if (node.isLeftChild()) {//RL black(node); red(grand); rotateright(parent); rotateleft(grand); } else {//RR black(parent); red(grand); rotateleft(grand); } } }

删除：

红色节点直接删除不用做任何处理：

这个是removeafter的代码也就是删除之后操作的代码

所以删除之后直接不用管了都已经继承了其他类中的删除了已经

删除黑色节点：

第一种有两个red红色节点的假如说删除25

那么就是相当于删除两边的红色节点但是红色节点的删除是不用考虑的

因此不用管这种情况

把第二种情况拉出来分析：

只需要把这个黑色节点旁边的红色节点染成黑色

然后让80指向这个被染成黑色的节点就相当于删除了这个拥有一个RED子节点的BLACK节点

因此我们删除之后的操作只需要把代替者染成黑色即可如代码所示

在红黑树用颜色作为判定条件：

当删除之后替代节点也是红色那么重复了

那么就要把替代节点染成黑色即可

ok：

我们现在开搞删除黑色叶子节点：

一：黑黑兄弟

——————————————————————————————————————————

重点;

我们删除的时候能借兄弟节点的基础是：

sibling(兄弟节点) 是一个黑色节点 并且至少有一个红色的子节点

不符合这个规定肯定不可以直接借

——————————————————————————————————————————

删除节点的兄弟是黑色的情况

sibling 表示兄弟节点

假如删除节点88 那么一定会导致B树节点下溢

如果兄弟节点有多的节点那么就可借走一个

重点;

我们删除的时候能借兄弟节点的基础是：

sibling(兄弟节点) 是一个黑色节点并且至少有一个红色的子节点

删除的是黑色叶子节点具体情况如下：

第一组：

当删除88时

产生下溢：那么78上去 80再下来

其实也就是一个旋转操作

先对76 左旋

再对 80右旋

中心节点这里是78 我们也要让中心节点继承parent的颜色

并且两个子节点的颜色要染成黑色

第二组：

同样删除88

这一次同样产生下溢

然后这种是LL 那么只需让80右旋转即可

那么中心节点即是76

中心节点继承parent节点的颜色

并且两个子节点的颜色要染成黑色

第三组：

当出现这种情况的时候删除88 依然会导致下溢

通过观察兄弟节点可知：LL或LR

我们有两种做法：

但是我们旋转较简单的LL

把80进行右旋转那么76就上去成为中心节点了

中心节点继承parent的颜色属性

红黑树只可以和四阶B树对应

不可以与其他阶的B树相提并论

情况一:

情况一：

当兄弟节点无法借的时候但一旦删除了88这个节点产生下溢

我们需要把父节点80下来与76进行合并

情况二：

但如果父节点只有一个元素的时候

不可以把父节点拿下来合并

这个时候直接套用之前的逻辑进行处理这种下溢情况

递归使用removeafter即可

ok 到这里删除节点的兄弟是黑色的情况已经说完了

二：红黑兄弟

删除的节点的兄弟是红色的情况

为了好办：

我们把兄弟的子节点强制变成我的兄弟

举个例子：

88的兄弟是55 55的子是76

我们强制把76变成88的兄弟

我们把80进行右旋w转之后55变成80的父节点

80指向76 这时候76成为了88的兄弟节点

那么哈哈哈哈

就变成了我们之前讲过的情况了黑兄弟回归！！

_____________________________________________________________________________

总结了一个旋转的规律超开心：我发现的哈哈哈哈哈：

当我们把88这个节点删除之后会发生下溢现象那么我们应该借用兄弟节点中的78

那么又为了维持平衡二叉树的性质

左子<父<右子因此我们最终应该保证78在中 76在左 80在右

第一步：

76到78是向右那么先76左旋

76左旋的意思就是成为没旋转之前的子节点78的左子节点

自己画一个图：此时：80指向78 78的左子树指向76

（注意树变化了下面也要根据这个变化的来）

第二步：

80到76向左

那么80右旋 80右旋的意思就是成为没旋转前的子节点78的右子节点

当我们进行第一步左旋转76之后我们让76成为78的左子节点

那么此时88的兄弟节点发生变化

变化成为了78而不是用来的76

重写删除之后的操作代码：

 / *重写删除之后的操作 * 因为我们在AVL树中已经写过了删除的操作 * 因此我们这里只要重写红黑树中特殊的删除后的操作即可 */ @Override protected void removeafter(Node<E> node, Node<E> replacement) { //如果删除的节点是红色 if(isRed(node)){ return; } //用以取代的node的节点是红色 if(isRed(replacement)){ black(replacement); return; } Node<E> parent=node.parent; if(parent==null){//删除的是根节点 return; } //删除的是黑色叶子节点 //判断被删除的node是左还是右 因为我们这个是删除之后的操作 //到这的都是叶子节点 删除时操作已经让我们无法知道兄弟节点的方向了 boolean left=parent.left==null||node.isLeftChild(); Node<E> sibling=left?parent.right:parent.left; if(left){//当被删除的节点在左边 兄弟节点在右边 if(isRed(sibling)){ black(sibling); red(parent); rotateleft(parent); sibling=parent.right; } if(isBlack(sibling.left)&&isBlack(sibling.right)){ boolean parentBlack=isBlack(parent); black(parent); red(sibling); if(parentBlack){ removeafter(parent,null); } else { color(sibling,colorOf(parent)); isBlack(parent); isBlack(sibling.left); rotateright(parent); } } } else {//当被删除的节点在右边 兄弟节点在左边 if(isRed(sibling)) {//兄弟节点是红色 black(sibling); red(parent); rotateright(parent); //更换兄弟即可 sibling=parent.left; } //到这里的情况肯定是兄弟节点必然是黑色 if(isBlack(sibling.left)&&isBlack(sibling.right)) { //这种情况就是兄弟节点没有子节点或者有红色子节点 // 即是它只有虚拟黑色节点或红色子节点 我们默认虚拟的不存在的节点是黑色的而已 //因为这是最后一层 这是B树的特性 boolean parentBlack = isBlack(parent); black(parent); red(sibling); if (parentBlack) { //如果parent是黑色的节点 我们需要做的就是把下溢后的空结点删除 removeafter(parent, null); } } else {//兄弟节点至少有一个红色子节点 那么就可以向兄弟节点借用元素了 //如果兄弟节点左边是黑色 那么先进行旋转 if(isBlack(sibling.left)){ rotateleft(sibling); //每一次旋转之后兄弟节点都会变化 sibling=parent.left; } //把中心节点的颜色染成和父节点颜色一致 color(sibling,colorOf(parent)); black(sibling.left); black(parent); rotateright(parent); } } }

RBTree：红黑树总代码：

讯享网package BinaryTree; import java.util.Comparator; public class RBTree<E> extends BBST<E>{ / * 红黑树需要染色 */ private static final boolean RED=false; private static final boolean BLACK=true; public RBTree() { this(null); } public RBTree(Comparator<E> comparator) { super(comparator); } / *重写添加之后的操作 */ @Override//node这里是添加的元素 protected void addafter(Node<E> node) { Node<E> parent = node.parent; //添加的是根节点 或者递归调用上溢到了根节点 if (parent == null) { black(node); return; } //如果父节点是黑色 那么直接返回即可 if (isBlack(parent)) { return; } //叔父节点 Node<E> uncle = parent.sibling(); //祖父节点 Node<E> grand = parent.parent; if (isRed(uncle)) { black(parent);//把parent染成黑色 black(uncle);//叔父同 red(grand);//祖父染成red色 染色完成之后当作新添加的节点向上合并 addafter(grand);//递归进行 直到添加完成 return; } //叔父节点不是红色 if (parent.isLeftChild()) {//L if(node.isLeftChild()){//LL black(parent); red(grand); rotateright(grand); } else {//LR black(node); red(grand); rotateleft(parent); rotateright(grand); } } else {//R if (node.isLeftChild()) {//RL black(node); red(grand); rotateright(parent); rotateleft(grand); } else {//RR black(parent); red(grand); rotateleft(grand); } } } / *重写删除之后的操作 * 因为我们在AVL树中已经写过了删除的操作 * 因此我们这里只要重写红黑树中特殊的删除后的操作即可 */ @Override protected void removeafter(Node<E> node, Node<E> replacement) { //如果删除的节点是红色 if(isRed(node)){ return; } //用以取代的node的节点是红色 if(isRed(replacement)){ black(replacement); return; } Node<E> parent=node.parent; if(parent==null){//删除的是根节点 return; } //删除的是黑色叶子节点 //判断被删除的node是左还是右 因为我们这个是删除之后的操作 //到这的都是叶子节点 删除时操作已经让我们无法知道兄弟节点的方向了 boolean left=parent.left==null||node.isLeftChild(); Node<E> sibling=left?parent.right:parent.left; if(left){//当被删除的节点在左边 兄弟节点在右边 if(isRed(sibling)){ black(sibling); red(parent); rotateleft(parent); sibling=parent.right; } if(isBlack(sibling.left)&&isBlack(sibling.right)){ boolean parentBlack=isBlack(parent); black(parent); red(sibling); if(parentBlack){ removeafter(parent,null); } else { color(sibling,colorOf(parent)); isBlack(parent); isBlack(sibling.left); rotateright(parent); } } } else {//当被删除的节点在右边 兄弟节点在左边 if(isRed(sibling)) {//兄弟节点是红色 black(sibling); red(parent); rotateright(parent); //更换兄弟即可 sibling=parent.left; } //到这里的情况肯定是兄弟节点必然是黑色 if(isBlack(sibling.left)&&isBlack(sibling.right)) { //这种情况就是兄弟节点没有子节点或者有红色子节点 // 即是它只有虚拟黑色节点或红色子节点 我们默认虚拟的不存在的节点是黑色的而已 //因为这是最后一层 这是B树的特性 boolean parentBlack = isBlack(parent); black(parent); red(sibling); if (parentBlack) {//如果parent是黑色的节点 我们需要做的就是把下溢后的空结点删除 removeafter(parent, null); } } else {//兄弟节点至少有一个红色子节点 那么就可以向兄弟节点借用元素了 //如果兄弟节点左边是黑色 那么先进行旋转 if(isBlack(sibling.left)){ rotateleft(sibling); //每一次旋转之后兄弟节点都会变化 sibling=parent.left; } //把中心节点的颜色染成和父节点颜色一致 color(sibling,colorOf(parent)); black(sibling.left); black(parent); rotateright(parent); } } } / * 创建一个染色的方法 封装起来 */ private Node<E> color(Node<E> node,boolean color){ if(node==null){ return null; } //染色 ((RBNode<E>)node).color=color; return node; } / *染色成红色 黑色 */ private Node<E> red(Node<E> node){ return color(node,RED); } private Node<E> black(Node<E> node){ return color(node,BLACK); } / * 传进来一个节点 判断是什么颜色 */ private boolean colorOf(Node<E> node){ //如果是null那么在红黑树中默认是BLACK颜色 //不为空 那么就看看它到底是什么颜色 return node==null?BLACK:((RBNode<E>)node).color; } / *你是否为黑色？ */ private boolean isBlack(Node<E> node){ return colorOf(node)==BLACK; } / *你是否为红色？ */ private boolean isRed(Node<E> node){ return colorOf(node)==RED; } / *开创一个内部类 */ private static class RBNode<E> extends Node<E> { boolean color; public RBNode(E elements, Node<E> parent) { super(elements, parent); } } }

总结：