搜刮树——AVL、红黑树、B树、B+树
目次二叉搜刮树
AVL树
2-3-4树
红黑树
旋转操作
概念讲解
旋转节点操作（左旋）
插入节点
删除节点
B树和B+树
B树
2.5.2 B+树
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
难度高，如果想要了解红黑树的增长、删除节点操作，肯定要穷举画图理解！！！
二叉搜刮树
一个二叉查找树是由n个节点随机构成,以是，对于某些情况,二叉查找树会退化成一个有n个节点的线性链。
https://i-blog.csdnimg.cn/direct/9804ba81c4c14e179f94697772341a8d.png
BST存在的标题是，树在插入的时候会导致倾斜，差异的插入顺序会导致数的高度不一样，而树的高度直接影响了树的查找服从。最坏的情况所有的节点都在一条斜线上，如许树的高度为N。基于BST存在的标题，平衡查找二叉树（Balanced BST）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树（高度平衡树，具备二叉搜刮树的全部特性，而且左右子树高度差不超过1）和红黑树。
AVL树
它的核心目标是通过动态调解树的布局，保持高度平衡，从而确保查找、插入和删除操作的时间复杂度始终为O(log n)，克制普通二叉搜刮树在极度情况下退化成链表的低效标题。
但是AVL树要求太过严酷，左旋和右旋的开销会比力大，这时出现了红黑树，只要求玄色节点平衡即可。
2-3-4树
2-3-4树是四阶的 B树(Balance Tree)，他属于一种多路查找树，它的布局有以下限制：所有叶子节点都拥有类似的深度。节点只能是 2-节点、3-节点、4-节点之一。
[*] 2-节点：包含 1 个元素的节点，有 2 个子节点；
[*] 3-节点：包含 2 个元素的节点，有 3 个子节点；
[*] 4-节点：包含 3 个元素的节点，有 4 个子节点；
所有节点必须至少包含1个元素元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点；而且结点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。
https://i-blog.csdnimg.cn/direct/95e342a10b2c4f4884ab0f42448ee0fe.png
天生2-3-4树简图
https://i-blog.csdnimg.cn/direct/999527ea53b94027ac094711f221eb9f.png
https://i-blog.csdnimg.cn/direct/110a9fea54ba44e5b5b499b0ddf098bd.png
https://i-blog.csdnimg.cn/direct/add3bb54cd8f45ddaf57d0279135853d.png
红黑树
红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:
[*] 每个节点要么是玄色，要么是赤色。
[*] 根节点是玄色。
[*] 每个叶子节点（NIL）是玄色。
[*] 每个赤色结点的两个子结点肯定都是玄色。
[*] 任意一结点到每个叶子结点的路径都包含数量类似的黑结点。
红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色
操作描述左旋以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点， 右子结点的左子结点变为旋转结点的右子结点，左子结点保持稳定。右旋以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点， 左子结点的右子结点变为旋转结点的左子结点，右子结点保持稳定。变色结点的颜色由红变黑或由黑变红。 旋转操作
概念讲解
https://i-blog.csdnimg.cn/direct/8d051892799843d4a728c37c58c2e5ca.png
左旋：以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持稳定。
右旋：以某!个节点作为旋转点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持稳定。
旋转节点操作（左旋）
https://i-blog.csdnimg.cn/direct/4bd9c6d5e7e749d195596a1ba7bb9572.png
private void leftRotate(RBNode p){
if(p != null){
RBNode r = p.right;
// 1.设置 pr-rl 要变为 p-rl
// 把rl设置到p的右子节点
p.right = r.left;
if(r.left != null){
// 设置rl的父节点为p
r.left.parent = p;
}
// 2.判断p的父节点情况
r.parent = p.parent; // 不管 p是否有父节点，都把这个父节点设置为 r的父节点
if(p.parent == null){
root = r; // p没有父节点 则r为root节点
}else if(p.parent.left == p){
p.parent.left = r; // 如果p为 p.parent的左子节点 则 r 也为 p.parent的左子节点
}else{
p.parent.right = r; // 反之设置 r 为 p.parent的右子节点
}
// 最后 设置 p 为 r 的左子节点
r.left = p;
p.parent = r;
}
}
/**
* 围绕p右旋
* @param p
*/
public void rightRotate(RBNode p){
if(p != null){
RBNode r = p.left;
p.left = r.right;
if(r.right != null){
r.right.parent = p;
}
r.parent = p.parent;
if(p.parent == null){
root = r;
}else if(p.parent.left == p){
p.parent.left = r;
}else{
p.parent.right = r;
}
r.right = p;
p.parent = r;
}
}
插入节点
/**
* 新增节点
* @param key
* @param value
*/
public void put(K key , V value){
RBNode t = this.root;
if(t == null){
// 说明之前没有元素，现在插入的元素是第一个
root = new RBNode<>(key , value == null ? key : value,null);
return ;
}
int cmp ;
// 寻找插入位置
// 定义一个双亲指针
RBNode parent;
if(key == null){
throw new NullPointerException();
}
// 沿着跟节点找插入位置
do{
parent = t;
cmp = key.compareTo((K)t.key);
if(cmp < 0){
// 左侧找
t = t.left;
}else if(cmp > 0){
// 右侧找
t = t.right;
}else{
// 插入节点的值==比较的节点。值替换
t.setValue(value==null?key:value);
return;
}
}while (t != null);
// 找到了插入的位置parent指向 t 的父节点t为null
// 创建要插入的节点
RBNode<K, Object> e = new RBNode<>(key, value == null ? key : value, parent);
// 然后判断要插入的位置 是 parent的 左侧还是右侧
if(cmp < 0){
parent.left = e;
}else{
parent.right = e;
}
// 调整变色 旋转
fixAfterPut(e);
}
private boolean colorOf(RBNode node){
return node == null ? BLACK:node.color;
}
private RBNode parentOf(RBNode node){
return node != null ? node.parent:null;
}
private RBNode leftOf(RBNode node){
return node != null ? node.left:null;
}
private RBNode rightOf(RBNode node){
return node != null ? node.right:null;
}
private void setColor(RBNode node ,boolean color){
if(node != null){
node.setColor(color);
}
}
/**
* 插入节点后的调整处理
* 1. 2-3-4树 新增元素 2节点添加一个元素将变为3节点 直接合并，节点中有两个元素
* 红黑树：新增一个红色节点，这个红色节点会添加在黑色节点下(2节点) --- 这种情况不需要调整
* 2. 2-3-4树 新增元素 3节点添加一个元素变为4节点合并 节点中有3个元素
* 这里有6中情况，( 根左左 根左右根右右 根右左)这四种要调整(左中右的两种)不需要调整
* 红黑树：新增红色节点 会添加到 上黑下红的节点中 = 排序后中间节点是黑色，两边节点是红色
*
*3. 2-3-4树：新增一个元素 4节点添加一个元素需要裂变：中间元素升级为父节点，新增元素与剩下的其中一个合并
* 红黑树：新增节点是红色+爷爷节点是黑色，父亲节点和叔叔节点为红色 调整为
* 爷爷节点变红色，父亲和叔叔节点变为黑色，如果爷爷节点为root节点则调整为黑色
* @param x
*/
private void fixAfterPut(RBNode<K, Object> x) {
x.color = RED;
// 本质上就是父节点是黑色的就不需要调整，对应的 2 3的情况
while(x != null && x != root && x.parent.color == RED){
// 1. x 的父节点是爷爷的 左孩子
if(parentOf(x) == parentOf(parentOf(x)).left){
// 获取当前节点的叔叔节点
RBNode y = rightOf(parentOf(parentOf(x)));
// 情况3
if(colorOf(y) == RED){
// 说明是 上3的情况变色处理
// 父亲节点和叔叔节点设置为黑色
setColor(parentOf(x),BLACK);
setColor(y,BLACK);
// 爷爷节点设置为 红色
setColor(parentOf(parentOf(x)),RED);
// 递归处理
x = parentOf(parentOf(x));
}else{
// 情况 2
if(x == parentOf(x).right){
// 如果x是父节点的右节点那么我们需要先根据 父节点 左旋
x = parentOf(x);
leftRotate(x);
}
// 叔叔节点为空对应于 上面的情况2
// 将父节点变为黑色
setColor(parentOf(x),BLACK);
// 将爷爷节点变为红色
setColor(parentOf(parentOf(x)),RED);
// 右旋转根据爷爷节点右旋转
rightRotate(parentOf(parentOf(x)));
}
}else{
// x 的父节点是爷爷是右孩子
// 获取父亲的叔叔节点
RBNode y = leftOf(parentOf(parentOf(x)));
if(colorOf(y) == RED){
// 情况3
setColor(parentOf(x),BLACK);
setColor(y,BLACK);
setColor(parentOf(parentOf(x)),RED);
x = parentOf(parentOf(x));
}else{
// 情况2
if( x == parentOf(x).left){
x = parentOf(x);
rightRotate(x);
}
setColor(parentOf(x),BLACK);
setColor(parentOf(parentOf(x)),RED);
leftRotate(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
} 删除节点
红黑树删除操作的本质实在就是删除2-3-4树的叶子节点
private RBNode getNode(K key){
RBNode node = this.root;
while (node != null ){
int cmp = key.compareTo((K) node.key);
if(cmp < 0){
// 在左子树
node = node.left;
}else if(cmp >0){
// 右子树
node = node.right;
}else{
return node;
}
}
return null;
}
/**
* 删除节点
* @param key
* @return
*/
public V remove(K key){
// 先找到这个节点
RBNode node = getNode(key);
if(node == null){
return null;
}
// 把值存起来 删除后 返回
V oldValue = (V) node.value;
deleteNode(node);
return oldValue;
}
/**
* 删除节点
* 3种情况
* 1.删除叶子节点，直接删除
* 2.删除的节点有一个子节点，那么用子节点来替代
* 3.如果删除的节点右两个子节点，此时需要找到前驱节点或者后继节点来替代
* 可以转换为 1、2的情况
* @param node
*/
private void deleteNode(RBNode node){
// 3.node节点有两个子节点
if(node.left !=null && node.right != null){
// 找到要删除节点的后继节点
RBNode successor = successor(node);
// 然后用后继节点的信息覆盖掉 要删除节点的信息
node.key = successor.key;
node.value = successor.value;
// 然后我们要删除的节点就变为了 后继节点
node = successor;
}
// 2.删除有一个子节点的情况
RBNode replacement = node.left != null ? node.left : node.right;
if(replacement != null){
// 替代者的父指针指向原来 node 的父节点
replacement.parent = node.parent;
if(node.parent == null){
// 说明 node 是root节点
root = replacement;
}else if(node == node.parent.left){
// 双向绑定
node.parent.left = replacement;
}else{
node.parent.right = replacement;
}
// 将node的左右孩子指针和父指针都指向null node等待GC
node.left = node.right = node.parent = null;
// 替换完成后需要调整平衡
if(node.color == BLACK){
// fixAfterRemove(replacement)
}
}else if(node.parent == null){
// 说明要删除的是root节点
root = null;
}else{
// 1. node节点是叶子节点 replacement为null
// 先调整
if(node.color == BLACK){
// fixAfterRemove(node)
}
// 再删除
if(node.parent != null){
if(node == node.parent.left){
node.parent.left = null;
}else{
node.parent.right = null;
}
node = null;
}
}
}
B树和B+树
B树
（Balanced Tree）这个就是我们的多路平衡查找树，叫做B-Tree（B代表平衡）。跟AVL树一样，B树在枝节点和叶子节点存储键值、数据地址、节点引用。它有一个特点：分叉数（路数）永远比关键字数多1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。
https://i-blog.csdnimg.cn/direct/19fa2938b46744eda54c58bef683b252.png
B Tree的查找规则是什么样的呢？比如我们要在这张表里面查找15。因为15小于17，走左边。因为15大于12，走右边。在磁盘块7里面就找到了15，只用了3次IO。
这个是不是比AVL 树服从更高呢？那B Tree又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟AVL树有什么区别？比如Max Degree（路数）是3的时候，我们插入数据1、2、3，在插入3的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有4个指针，子节点会变成4路，以是这个时候必须进行分裂（实在就是B+Tree）。把中心的数据2提上去，把1和3变成2的子节点。如果删除节点，会有相反的归并的操作。留意这里是分裂和归并，跟AVL树的左旋和右旋是不一样的。我们继续插入4和5，B Tree又会出现分裂和归并的操作。
从这个里面我们也能看到，在更新索引的时候会有大量的索引的布局的调解，以是表明了为什么我们不要在频繁更新的列上建索引，大概为什么不要更新主键。节点的分裂和归并，实在就是InnoDB页（page）的分裂和归并。
相比AVL树，B树的树高更低，尤其实用于磁盘存储场景。由于B树每个节点可存储多个关键字（如Max Degree=3时，每个节点最多存2个关键字），能明显减少IO次数，提拔大规模数据查询服从。
2.5.2 B+树
增强版多路平衡查找树因为B Tree的这种特性非常适合用于做索引的数据布局，以是很多文件系统和数据库的索引都是基于B Tree的。但是实际上，MySQL里面使用的是B Tree的改良版本，叫做B+Tree（增强版多路平衡查找树）。
B+树的存储布局：
https://i-blog.csdnimg.cn/direct/7cb47a98db4d4e838855a4ee1d730e32.png
MySQL中的B+Tree有几个特点：
[*] 它的关键字的数量是跟路数相等的；
[*] B+Tree的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。搜刮到关键字不会直接返回，会到末了一层的叶子节点。比如我们搜刮id=28，固然在第一层直接命中了，但是全部的数据在叶子节点上面，以是还要继续往下搜刮，不停到叶子节点。
[*] B+Tree的每个叶子节点增长了一个指向相邻叶子节点的指针，它的末了一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的布局。
https://i-blog.csdnimg.cn/direct/26640456be804412a052c3bcd14c1561.png
总结， B+Tree的特点带来的优势：
[*] 它是B Tree的变种，B Tree能办理的标题，它都能办理。B Tree办理的两大标题是什么？（每个节点存储更多关键字；路数更多）
[*] 扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵B+Tree拿到所有的数据）
[*] B+Tree的磁盘读写能力相对于B Tree来说更强（根节点和枝节点不保存数据区，以是一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
[*] 排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
[*] 服从更加稳定（B+Tree永远是在叶子节点拿到数据，以是IO次数是稳定的）
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]