- 1第一次使用GitHub_第一次gang交
- 2实验5：常用的自动化库_自动化工具需要导入哪些库
- 3Mac OS 系统如何访问Library目录_mac library
- 4Spring Cloud Gateway 整合 sentinel 实现流控熔断_spring.cloud.sentinel.eager
- 5HMC 的升级方法
- 6【Spring Security】认证&密码加密&Token令牌&CSRF的使用详解_springsecurity token认证
- 7网上订餐系统|基于springboot的网上订餐系统设计与实现(源码+数据库+文档)_在线订餐系统的设计与实现数据表信息
- 82017ROS暑期学校笔记_马庆华机械臂
- 9jenkins运行python代码报UnicodeEncodeError: ‘charmap‘ codec can‘t encode characters_charmap' codec can't encode characters in position
- 10人工智能和机器学习的应用日益广泛，在医疗健康领域的具体应用是什么？
树05_红黑树_构造红黑树网站
赞
踩
01-红黑树的五个性质
1.根节点为黑色
2.节点不是红色就是黑色
3.虚拟叶子节点为黑色
4.红色节点的子节点必须为黑色
这个可以推导出：红色节点的父只能是黑色
所以对于红色节点来说，父子都必须为黑色
- 1
- 2
5.任意一个节点到虚拟叶子节点经历的黑色节点个数相同
补充说明：
1.性质3中：虚拟叶子结点是假想出来的，实际并不存在；它的作用是给我们用作条件判断
2.这五条性质并不是保证红黑树中平衡因子像AVL树一样严格<=1，只是保证树大致平衡
3.红黑树并没有对黑色节点的子节点做要求，黑色节点的子节点可以是黑色，也可以是红色；
02-红黑树的错误示范
不是红黑树；
从5条性质分析：
1.根节点为黑色
2.节点有黑有红
3.虚拟黑色叶子节点不用管
4.红色节点子节点为黑色
5.不满足性质5
55到38.right 和 55到25.left 经历的黑色节点个数不同
- 1
03-红黑树与4阶B树等价变换
- 首先要明白 红黑树的物理结构是二叉树，不是多阶B树
- 红黑树在逻辑上可以等价转换为4阶B树，并且红黑树中节点的增删严格遵守B树性质
4阶B树的性质
1.节点元素个数：[1,3]
2.节点的子节点个数：节点元素个数+1
这两个性质，约束了4阶B树：
- 当前节点中元素个数过多，则上溢；
- 当前节点中元素个数少了，父节点中元素下溢；
- 子节点元素个数必须为当前节点元素个数+1，这个很重要
红黑树转换为4阶B树的方式
(1)每个black节点等效为4阶B树一个节点中的父元素
(2)black节点和他的所有红色子节点融合，形成1个B树节点
等效转换图示：
（1）红黑树的black节点个数和4阶B树节点总个数是一样的
（2）等效4阶B树中一个节点中的父元素永远是红黑树的black节点
这两个可以推导出红黑树转为4阶B树时，B树节点的4种情况，如上图右上角所示：
红黑树等价转换的4阶B树中节点的四种情况:
1）度为2的black节点和red子节点融合，构成3个元素的节点
2）度为1的black节点和red子节点融合（分左右子节点）
3）度为0，自己为一个节点
因此一个节点最多有3个元素，最少1个节点，因此和4阶B树对应上了。
说明
-
对于AVL树，是通过平衡因子来维护树的平衡。而对于红黑树来说，就是通过在二叉树的增删过程中维护节点颜色来保证满足红黑树5个性质，来维护树的平衡，因此对于红黑树的节点来说只有颜色，不讲究高度、平衡因子
-
红黑树与4阶B树在逻辑上是完美等价的（符合任何情况）
逻辑上等价成4阶B树的目的：在增删节点时维护红黑树节点颜色的同时，也要保证4阶B树的性质； -
2-3树无法和红黑树做等价变换，因此二者比较没有意义
小练习
如图所示：上面是红黑树，下面是等价的4阶B树
04-几个英文单词
Uncle节点：和parent共一个
parent的兄弟节点叫uncle节点，比如图中的50的uncle节点，只有25是
05-红黑树前期准备
1.RBTree构造器
(1) RBTree也是搜索树，因此和AVLTree一样，继承BinarySearchTree,由于搜索树必须提供比较，所以仍然需要带有comparator的构造器
import java.util.Comparator;
public class _04_RBTree<E> extends _02_BinarySearchTree<E>{
public _04_RBTree(){}
public _04_RBTree(Comparator comparator){
super(comparator);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
2.RBTree自己的Node类型
RBTree的Node需要有color属性，因此继承Node，增加color属性；
color只有红色和黑色因此可以设置为布尔值;
在RBTree内部定义私有静态常量来规定RED和Black对应的布尔值：
public class _04_RBTree<E> extends _05_BinaryBalancedSearchTree<E> { private static final boolean RED=false; private static final boolean BLACK=true; public _04_RBTree() { } public _04_RBTree(Comparator comparator) { super(comparator); } private static class RBNode<E> extends Node<E> { boolean color = RED; public RBNode(E element, Node<E> parent) { this.element = element; this.parent = parent; } @Override public String toString() { String str = ""; if(color==RED){ str = "R_"; } return str + element.toString(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
3.辅助类函数
（1）RBTree中添加
//1.todo 给节点染色 //返回值为node 返回染完色的node private Node<E> color(Node<E> node,boolean color){ if(node == null) return node; ((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); } //todo2. 获取node的颜色 private boolean colorOf(Node<E> node){ if(node == null) return BLACK;//空节点在红黑树中往往是叶子结点，因此返回黑色 return ((RBNode<E>)node).color; } private boolean isBlack(Node<E> node){ return colorOf(node) == BLACK; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
（2）在BinaryTree的Node中添加：
public Node<E> sibling() { // 红黑树中用到, 返回兄弟节点
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
05-红黑树的添加
由于红黑树可以完美等价于4阶B树，因此一定要时时刻刻联想到B树（心里有B树）：
(1) B树中，新添加进来的元素必然是添加到叶子结点中
(2) 4阶B树，无论是根节点还是非根节点，元素个数都满足：[1,3]
建议：
将新添加进来的节点默认设置为RED，这样能够让红黑树尽快的满足红黑树的性质。所以在上面写的构造方法中，设置color默认为RED
原因分析：
假设往一个红黑树中添加进一个红色节点，那么满足的性质有：
- 根节点为黑色 √
- 节点是红色或者黑色 √
- 叶子结点全为黑色（假想）√
- 红色节点的子节点为黑色（未必满足） × 有可能添加进去的节点的父节点是红色节点
- 任一节点到叶子节点的黑色节点个数相同 √
06-添加的所有情况
- 对于B树来说，添加新的元素只能添加到叶子节点，因此红黑树添加的所有情况 == B树叶子节点的所有情况
- 由前面红黑树可以和4阶B树完美等价，可知两个结论：
(1)红黑树转为4阶B树时，一个节点有且只有一个blcak元素；而且black元素是其所在节点的父元素
(2)叶子节点四种情况：红黑、黑红、红黑红、黑
红黑树所有的叶子结点类型如下所示：
1.添加一个新节点的12种情况
1）满足红黑树性质4的四种情况
- 这四种情况，添加新元素之后仍然满足等价4阶B树的性质和红黑树的性质（每个节点只有一个黑色节点，而且节点个数在[1,3]范围）
- 因此添加新节点之后不需要做任何额外处理；
2）不满足红黑树性质4的八种情况
红黑树和AVL树不同在于，AVL是通过维护平衡因子来保证搜索树的平衡，因此每个节点都要维护高度。但是红黑树不是通过平衡因子，是通过保障红黑树的5个性质来保证树的平衡，因此对于红黑树，在增删操作中，只要保证满足5个性质，即可。
为什么5个性质能保证平衡，在学完红黑树增删节点之后就能理解了。
2.添加 没有Uncle不上溢（4种）
LL&RR
有8种添加会导致红黑树不满足性质4，现在我们将这8种情况更细一步拆解。
如上图所示，46-50-52 和 76-72-60两种 红色节点的子节点为红色，因此不满足红黑树性质四；我们可以将这两种情况定性为RR和LL 失衡；
定性的原则是 以B树角度来看，当前叶子节点中两个红色元素和黑色父元素的关系
- 1
修复原则
从红黑树等价转换为4阶B树的四种叶子节点情况的角度来进行修复：
RR:46-50-52
(1)当前节点有三个元素，那么只能是红黑红的情况；
(2)黑色元素必须为当前节点的根元素
由这两个条件，可以推断出应该将此节点修复为：
46(RED) <- 50(BLACK) -> 50(RED)
LL:60-72-76
同理修复为：
60(RED) <- 72(BLACK) -> 76(RED)
最终调整完如下图所示：
即所要做的操作为：
先染色，再旋转
- 新添加进去的节点的父节点染成黑色
- 祖父节点染成红色
- RR的情况对祖父节点进行左旋
- LL的情况对祖父节点进行右旋
这两种情况的判定条件
没有uncle节点(或者说uncle节点为黑色（nil）)
LR&RL
判定条件
没有uncle节点
4.添加-有uncle 上溢(4种)
- 如上图所示添加10，其父节点17的兄弟节点为33；
- 由于4阶B树的节点最多容纳3个元素，因此上溢；
上溢的节点选17和25都可以，这里选25因为方便；25直接和父节点合并，17和父节点隔代了，相对比较麻烦。
一旦上溢，25要和38 55合并为一个；那么25和55都要变成红色，38变为黑色，这样17和33变成两个独立的子树根节点。
我们先不处理25上溢的问题，先处理这个叶子节点
当插入一个新节点10：
(1)先处理构成的子树： 17子树和33子树
17和33都要变为黑色=>意味着新节点的父节点和Uncle节点要转为黑色
(2)再处理25: 25作为上溢节点
对于父节点38 和 55 来说也是插入新的元素，因此先将25节点染红，然后套用12种情况作为新元素添加
(3)连续上溢到根节点
如果持续上溢到根节点，树会长高，根节点只有一个新的元素，此时只需要将新的根节点染成黑色
LL的修复
此情况，上溢出没有旋转操作，只需要染色即可。
RR的修复
LR的修复
RL的修复
5.添加情况总结
添加一共有个12种情况：
(1)父节点是黑色
占了四种情况，这四种情况不需要做任何处理
(2)Uncle节点是黑色
占了四种情况，这四种情况又分为：LL LR RR RL
- LL和RR的处理方式为：
- LR和RL的处理方式为：
（3）Uncle节点为红色
也分为LL LR RR RL 四种
6.添加实现
代码重构
由于Uncle为黑色的情况下也涉及到旋转，那么和AVL树的旋转是一样的，这样有公共代码，就可以抽象到一个公共类中；原本的继承结构如下：
- 现在进行修改：引入一个平衡二叉搜索树BBSTree，继承BST，然后AVLTree和RBTree继承BBStree
- AVL继承BBSTree，将旋转操作拷贝过去，由于RBTree旋转不需要更新节点的高度，因此在公共类中，将更新高度的操作给删除，在AVLTree进行重写
公共类
package _02_二叉树; import java.util.Comparator; public class _05_BinaryBalancedSearchTree<E> extends _02_BinarySearchTree<E>{ public _05_BinaryBalancedSearchTree() { } public _05_BinaryBalancedSearchTree(Comparator<E> comparator) { super(comparator); } //旋转 protected void rotateLeft(Node<E> node) { Node<E> parent = node.right; Node<E> child = parent.left; //1.更改左右子节点 parent.left = node; node.right = child; afterRotate(node,parent,child); //更新高度 更新高度只有AVL树需要做 // updateHeight(node); // updateHeight(p); } protected void rotateRight(Node<E> node){ Node<E> parent = node.left; Node<E> child = parent.right; parent.right = node; node.left = child; afterRotate(node,parent,child); //更新高度 更新高度只有AVL树需要做 //updateHeight(node); //updateHeight(p); } //重新规划parent protected void afterRotate(Node<E> grand,Node<E> parent,Node<E> child){ parent.parent = grand.parent; if(grand.isLeftChild()){ grand.parent.left = parent; }else if(grand.isRightChild()){ grand.parent.right = parent; }else{ root = parent; } } //统一旋转操作 protected void rotate( Node<E> r, // 子树的根节点 Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f) { // 让d成为这颗子树的根结点 d.parent = r.parent; if (r.isLeftChild()) { r.parent.left = d; } else if (r.isRightChild()) { r.parent.right = d; } else { root = d; } // b-c b.right = c; if (c != null) { c.parent = b; } //updateHeight(b); // e-f f.left = e; if (e != null) { e.parent = f; } //updateHeight(f); // b-d-f d.left = b; d.right = f; b.parent = d; f.parent = d; //updateHeight(d); //AVL树中需要更新节点高度 //注意：更新高度的顺序必须是先更新低的节点 } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
AVLTree
AVLTree种重写旋转后的操作，要更新高度
@Override
protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
super.afterRotate(grand, parent, child);
updateHeight(grand);
updateHeight(parent);
}
@Override
protected void rotate(Node<E> r, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f) {
super.rotate(r, b, c, d, e, f);
updateHeight(b);
updateHeight(f);
updateHeight(d);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
afterAdd()
//添加后处理 @Override protected void afterAdd(Node<E> node) { Node<E> parent = node.parent; //todo case1:父节点是black //如果parent==null，意味着新添加的节点为root，此时将此节点染成黑色 //注意：这里也解决了上溢到根节点，根节点溢出新的根节点的问题 //新溢出的根节点要染成黑色 if(parent==null){ black(node); return; } //如果parent是黑色节点，那么直接返回即可，不需要做多的操作 if(isBlack(parent)){ return; } //todo case2:parent为红色，并且Unlce节点为红色 Node<E> uncle = parent.sibling(); // 1.parent 和 Uncle染成black // 2.grand上溢 ： 将grand染成红色，然后当做新节点添加到 Node<E> grand = parent.parent; if(isRed(uncle)){ black(parent); black(uncle); Node<E> newGrand = red(grand);//将grand染成红色 afterAdd(newGrand);//当做一个新的节点添加，注意染成红色后就是添加后的状态了，只需要做afterADd处理 return; } //todo case3: Uncle节点不是红色 // Uncle节点不是红色还有四种情况 LL LR RR RL if(parent.isLeftChild()){//L if(node.isLeftChild()){//LL //parent染成黑色 //grand染成红色 并且单旋操作 black(parent); red(grand); rotateRight(grand); }else{ //LR //自己染成黑色，grand染成红色 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); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
补充
上面的代码中，除了父节点为黑色意外，grand都要染成红色，因此在获取grand节点的时候可以直接染红
删除
被删除的节点8种情况
前提：红黑树可以等价于4阶B树来说，对B树来说，真正被删除的元素只会再叶子节点上；
case1.被删除的是红色节点（4种）
从上图看，删了红色节点不影响红黑树性质；也不影响B树性质
因此可以直接删除，不需要做任何操作
判断条件
isRed(node) == true
处理方式
return；
case2.被删除的是黑色节点（4种）
case2.1黑色节点度为2
BST中，删除度为2的节点，实际上删除的是前继节点，并值进行了替换，效果如下：
判断条件
isRed(node) node是实际被删除的节点
处理方式
return;
case2.2 黑色节点度为1
度为1的黑色节点被删除后：
从B树角度出发：仍然满足B树性质，因此不需要做下溢操作
从红黑树出发：将子元素染成黑色即可
case2.3 黑色节点度为0
度为0的黑色节点被删除后，那么B树就缺了一根胳膊，B树结构肯定要调整；
所以第一时间是看兄弟节点能否借元素。
兄弟节点能借，前提是兄弟节点是黑色，如果是红色，那兄弟节点是B树中父节点的元素
情况2.3.1 兄弟元素为黑色
（1）下溢
- 4阶B树中一个节点必须满足：
1.元素个数为[1,3]；
2.子节点的个数必须=父节点元素个数+1
88节点被删除后，父节点有两个元素，因此对于B树来说必须要有三个指针，因此造成下溢；
B树节点下溢的处理方式：看兄弟能否借元素；当兄弟节点减少一个元素，仍然能满足节点中元素个数为[1,3]那么就可以借
case2.3.1.1：兄弟有元素可以借
从4阶B树来看，兄弟节点元素个数>=2才可以借
下图三种情况，兄弟节点可以借元素
1.条件
(1) 兄弟节点(兄弟元素)必须是黑色
如果兄弟节点是红色，那么这个红色节点在4阶B树的视角来看，
是父节点的元素，无法借元素过来。
- 1
- 2
(2) 兄弟节点有1或者2个红色子节点
2.处理方式
LR 先对兄弟节点左旋转，再对父节点进行右旋转；
旋转后染色：
1.新的父节点继承 parent的颜色
2.旋转后，左右子节点都为Black
类比LL的处理方式，兄弟有元素的三种情况如下图总结： 
上图第三种情况，LL和LR处理都可以。
如果是第一种情况，对brother进行左旋转之后，也变成了LL型，因此三种情况都需要对parent做右旋转
第一种情况的判决条件是 brother.left 是黑色的
if(isBlack(brother.left)){
rotateLeft(brother);
brother = brother.parent;
}
//旋转brother之后，统一变为LL的情况 先染色 再旋转
//（这里brother旋转之后是没有变的,因此要在上面LR的情况修改一下brother）
color(brother,colorOf(parent));
black(brother.left);
black(parent);
rotateRight(parent);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
case2.3.1.2：兄弟节点不能借元素
从4阶B树来看兄弟节点不能借，兄弟节点元素<=1，那么兄弟节点要么为黑色节点要么没有兄弟节点。
兄弟节点不能借，在4阶B树中，是父节点下来和左右子树合并。
1.条件
兄弟节点没有红色子元素
也有两种情况：
（1）有黑色兄弟节点，父节点为红色
那么80下来和76合并。需要更换颜色，因为当前节点的父元素肯定为黑色。
处理如下：
（2）有黑色兄弟节点，父节点为黑色
88删除后，调用了afterRemove(88)，父节点下溢会导致父节点不满足条件，导致祖父节点需要下溢，因此需要再次对parent调用一次afterremove()即可。
处理方式
删除black叶子结点-兄弟节点为红色
情况2.3.2 兄弟元素为红色
判断条件 : isRed(brother)
- 兄弟节点为红色，在4阶B树的角度来看此红色兄弟节点是父节点的元素。
- 从B树角度来看，76是88的兄弟，但是在红黑树的角度看不是的。处理方法是：让红色兄弟的黑色儿子变成我的黑兄弟=> 80.left=80.left.right
- 因此需要对80进行一次右旋转。旋转后如右图所示，55变为根节点，因此需要对55和80进行染色。
- 经过旋转之后，恢复到有兄弟节点的情形了，因此又要判断兄弟节点能不能借。
处理方式
兄弟节点染成黑色
parent染成红色
对parent进行旋转
if(isRed(brother)){
black(brother);
red(parent);
rotateRight(parent);
brother = parent.left;
}
- 1
- 2
- 3
- 4
- 5
- 6
注意：
兄弟节点55的下面绝对是两个节点，否则不满足B树性质
所以旋转后的兄弟节点76是必定存在的
代码调整
在判断被删除的黑色节点是否有红色子节点的时候，我们需要获取子节点的信息，子节点就是被删除节点；因此我们在BST的搜索操作上添加如下删除后修补的方法：
protected void afterRemove(Node<E> node,Node<E> replacement){}
- 1
replacement是被删除元素的子元素；
private void remove(Node<E> node){ if(node == null) return; //先处理度为2的节点，因为也是删除度为1的节点 Node<E> del = null; if(node.left != null && node.right != null){ del = predesessor(node);//前继节点 node.element = del.element; }else{ del = node; } //del要么度为1，要那么度为0 //child为del不为空的子节点。如果child为null，则del为叶子结点。 Node<E> child = del.left == null ? del.right:del.left; if(child != null){ //del是度为1 的节点 需要做这一步 child.parent = del.parent; } if(del.parent == null){ root = child; }else{ if(del == del.parent.left){ del.parent.left = child; }else{ del.parent.right = child; } } //节点真正被删除的时候删除 afterRemove(del,child); size--; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
删除总结
1.明确被删除的元素只能再B树的叶子节点
叶子结点4种情况： 红黑红 黑红 红黑 黑
2.删除红色元素：直接删除，不做任何修复操作
3.删除黑色元素
(1)红黑红：BST中删除的是前继或者后继，删除的还是红色节点；不做任何修复操作
(2)黑红和红黑：BST中的做法是将parent的child指向为红色子元素，因此需要对红色子元素进行染黑处理
(3)黑色光棍：BST的做法是直接删除，因此会产生下溢
3.1.兄弟能借
条件：兄弟节点是黑色，而且还有红色子节点
3.2兄弟不能借
兄弟节点<=1,兄弟要么是黑色光棍，要么是红色节点
3.2.1兄弟也是黑色光棍
3.2.1.1 父节点是红色
直接下来，合并在一起；
3.2.1.2 父节点是黑色
父节点和子节点合并；
兄弟节点染红；
父节点也造成下溢，进行afterRemove()处理
3.2.2 兄弟是红色节点
旋转，让兄弟节点变成黑色
到这里，删除分析结束；
删除代码
@Override protected void afterRemove(Node<E> node, Node<E> replacement) { //todo case1.被删除的节点为红色 //包含两种情况：1.直接删除的红色节点 2.删除的是度为2的黑色节点 红色是替死鬼 if (isRed(node)) { return; } //todo 到这里，剩下的被删除的节点都是黑色 要么度为1 要么度为0 //todo case2.处理度为1的黑色节点 (条件：被删除的节点的替代节点为红色 ) if (isRed(replacement)) { black(replacement); //将染成黑色即可 return; } //todo case3.处理度为0的black节点 // todo 3.1 只有1个节点的红黑树 Node<E> parent = node.parent; if (parent == null) return; // todo 3.2 找到兄弟节点 判断兄弟节点能不能借元素 //Node<E> brother = node.sibling(); // 注意：这里获取brother节点不能这么获取,因为在afterRemove()方法中，node是已经被删除的节点 // 这意味着：如果node是左子节点，那么parent.left==null // public Node<E> sibling() { // 红黑树中用到, 返回兄弟节点 // if (isLeftChild()) { // return parent.right; // } // // if (isRightChild()) { // return parent.left; // } // return null; // } // public boolean isLeftChild(){ // 判断自己是不是左子树 // return parent!=null && this==parent.left; // } // 由于aftrerRemove()方法是在remove()方法之后调用的， // 那么remove()方法中，node节点被删除后： // if(del == del.parent.left){ // del.parent.left = child; // }else{ // del.parent.right = child; // } // del就是被删除节点node,这里 node就是度为0的black节点，child=null // 因此调用remove()后 parent.left == null // 那么在这里调用node.sibling() 会调用 node.isLeftChild() // 如果ndoe是左子节点，那么node.parent.left 已经为null了，右子节点同理 // 因此node调用isLeftChild的时候，praent.left==null了，this不为null，所以判断会有问题。 // 无法获取isLeftChild()，也就无法获取sibling()了 //这里处理的方法是：如果node.parent.left == null 那么node就是左子节点 //为什么能这么判断？ //因为红黑树等效为4阶B树 //4阶B树不可能只有一个子节点 //还用node.isLeftChild()判断是当父节点只有一个黑色元素的时候，父节点下溢，黑色元素下溢和子节点合并，但是并不是真正 //的删除这个黑色元素，也就是说这个黑色元素的parent.left或者parent.right 仍然等于这个黑色元素 boolean left = parent.left == null || node.isLeftChild(); Node<E> brother = left ? parent.right : parent.left; //todo 3.3 判断父节点的颜色 boolean parentColor = colorOf(parent); //3.2 兄弟节点可以借 兄弟节点为黑色，且有子节点。 if (left) { //被删除节点在左边 if (isRed(brother)) { black(brother); red(parent); rotateLeft(parent); //更换兄弟 兄弟是黑色节点 brother = parent.right; } //到这里了，brother肯定为黑色 if (isBlack(brother.left) && isBlack(brother.right)) { //brother是光杆司令,父节点要和子节点合并=> 父节点染黑，兄弟节点染红 这么处理完后相当于删除了父节点 boolean parentBlack = isBlack(parent); black(parent); red(brother); if (parentBlack) { //父节点为黑色，父节点向下融合后就为空了，因此相当于删除掉一个叶子结点，左删除后处理。 afterRemove(parent, null); } } else { //兄弟节点至少有一个红色 if (isBlack(brother.right)) { rotateRight(brother); brother = brother.parent; } //旋转brother之后，统一变为LL的情况 先染色 再旋转 //（这里brother旋转之后是没有变的,因此要在上面LR的情况修改一下brother） color(brother, colorOf(parent)); black(brother.right); black(parent); rotateLeft(parent); } } else { //1.step1 如果被删除节点是右子节点 //2. step2.兄弟节点是红色，先将兄弟节点变成黑色，再接下来统一处理兄弟为黑色的情况 if (isRed(brother)) { black(brother); red(parent); rotateRight(parent); //更换兄弟 兄弟是黑色节点 brother = parent.left; } //3. step3.到这里了，brother肯定为黑色 //4. step4.处理黑兄弟没有红色子节点的情况 （不能借元素） // 这里brother不会为空， if (isBlack(brother.left) && isBlack(brother.right)) { //step 4.1 brother是光杆司令,父节点要和子节点合并 父节点染黑，兄弟节点染红 这么处理完后相当于删除了父节点 boolean parentBlack = isBlack(parent); black(parent); red(brother); // step 4.2 如果父节点是黑色，那么B树角度看，父节点空了，造成连锁下溢 if (parentBlack) { afterRemove(parent, null); } } else { //5. step5.兄弟节点至少有一个红色 找兄弟节点借元素 //6. step6.先处理LR的情况，转变为LL，在后面做统一处理 if (isBlack(brother.left)) { rotateLeft(brother); brother = brother.parent; } //7. step7. 旋转brother之后，统一变为LL的情况 先染色 再旋转 //（这里brother旋转之后是没有变的,因此要在上面LR的情况修改一下brother） color(brother, colorOf(parent)); black(brother.left); black(parent); rotateRight(parent); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
一点都不复杂，真的。
红黑树的平衡
1.红黑树的平衡标准：没有一条路径会使其他路径的2倍,是一种弱平衡策略
AVL树靠的是平衡因子来保证平衡的。红黑树的平衡是靠保证5条性质从而保证红黑树等价于4阶B树；那么四阶B树的平衡，是因为一个节点能够存储多个元素，因此树矮，索引次数少，但是按照红黑树进行展开会发现，树并不矮，并且平衡因子会>1,为什么用红黑树呢、。？
因为红黑树保证的是平衡因子不会过高，不会退化为链表。
最短路径为全是黑色节点。最长路径为黑节点*2； 最长路径就是每个黑色后面跟一个红色
在只看黑色节点的情况下，树的高度是满足AVL的平衡标准的；
性能对比
1.二叉搜索树
添加、删除、搜索都和树的高度有关 O(logN)
2.红黑树
树高级别也是O(logN)
添加、删除、搜索都和树的高度有关 O(logN)
AVL树和红黑树对比：
红黑树和AVL树都是在二叉搜索树添加、删除节点之后的基础上再做的额外操作；
对于红黑树来说，添加和删除的额外修复操作都是O(1)级别的旋转操作
对于AVL树来说，删除的时候可能会造成链式反应，造成O(logN)级别的旋转操作
因此从这方面红黑树的性能优于AVL树
红黑树旋转操作分析：
只有当uncle节点不是红色的情况下，也就是没有uncle节点，这种情况下需要进行旋转操作。会发现最多旋转两次，因此旋转次数为O(1)
而链式反应种，不需要做旋转操作；最多做一次，就是遇到了uncle不是红色的时候
