搜刮树——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个节点的线性链。

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个元素元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点；而且结点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。

天生2-3-4树简图

红黑树

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

• 每个节点要么是玄色，要么是赤色。
  
• 根节点是玄色。
  
• 每个叶子节点（NIL）是玄色。
  
• 每个赤色结点的两个子结点肯定都是玄色。
  
• 任意一结点到每个叶子结点的路径都包含数量类似的黑结点。
  

红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色

操作	描述
左旋	以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点， 右子结点的左子结点变为旋转结点的右子结点，左子结点保持稳定。
右旋	以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点， 左子结点的右子结点变为旋转结点的左子结点，右子结点保持稳定。
变色	结点的颜色由红变黑或由黑变红。

旋转操作

概念讲解

左旋：以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持稳定。

右旋：以某!个节点作为旋转点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持稳定。
旋转节点操作（左旋）

1. [/code] [code]private void leftRotate(RBNode p){
2.         if(p != null){
3.             RBNode r = p.right;
4.             // 1.设置 pr-rl 要变为 p-rl
5.             // 把rl设置到p的右子节点
6.             p.right = r.left;
7.             if(r.left != null){
8.                 // 设置rl的父节点为p
9.                 r.left.parent = p;
10.             }
11.             // 2.判断p的父节点情况
12.             r.parent = p.parent; // 不管 p是否有父节点，都把这个父节点设置为 r的父节点
13.             if(p.parent == null){
14.                 root = r; // p没有父节点 则r为root节点
15.             }else if(p.parent.left == p){
16.                 p.parent.left = r; // 如果p为 p.parent的左子节点 则 r 也为 p.parent的左子节点
17.             }else{
18.                 p.parent.right = r; // 反之设置 r 为 p.parent的右子节点
19.             }
20.             // 最后 设置 p 为 r 的左子节点
21.             r.left = p;
22.             p.parent = r;
23.         }
24.     }

复制代码

1. /**
2.      * 围绕p右旋
3.      * @param p
4.      */
5. public void rightRotate(RBNode p){
6.         if(p != null){
7.             RBNode r = p.left;
8.             p.left = r.right;
9.             if(r.right != null){
10.                 r.right.parent = p;
11.             }
12.             r.parent = p.parent;
13.             if(p.parent == null){
14.                 root = r;
15.             }else if(p.parent.left == p){
16.                 p.parent.left = r;
17.             }else{
18.                 p.parent.right = r;
19.             }
20.             r.right = p;
21.             p.parent = r;
22.         }
23.     }

复制代码

插入节点

2. /**
3.     * 新增节点
4.     * @param key
5.     * @param value
6.     */
7.    public void put(K key , V value){
8.        RBNode t = this.root;
9.        if(t == null){
10.            // 说明之前没有元素，现在插入的元素是第一个
11.            root = new RBNode<>(key , value == null ? key : value,null);
12.            return ;
13.        }
14.        int cmp ;
15.        // 寻找插入位置
16.        // 定义一个双亲指针
17.        RBNode parent;
18.        if(key == null){
19.            throw new NullPointerException();
20.        }
21.        // 沿着跟节点找插入位置
22.        do{
23.            parent = t;
24.            cmp = key.compareTo((K)t.key);
25.            if(cmp < 0){
26.                // 左侧找
27.                t = t.left;
28.            }else if(cmp > 0){
29.                // 右侧找
30.                t = t.right;
31.            }else{
32.                // 插入节点的值==比较的节点。值替换
33.                t.setValue(value==null?key:value);
34.                return;
35.            }
36.        }while (t != null);
37.        // 找到了插入的位置  parent指向 t 的父节点  t为null
38.        // 创建要插入的节点
39.        RBNode<K, Object> e = new RBNode<>(key, value == null ? key : value, parent);
40.        // 然后判断要插入的位置 是 parent的 左侧还是右侧
41.        if(cmp < 0){
42.            parent.left = e;
43.        }else{
44.            parent.right = e;
45.        }
46.        // 调整  变色 旋转
47.        fixAfterPut(e);
48.    }

复制代码

2. private boolean colorOf(RBNode node){
3.        return node == null ? BLACK:node.color;
4.    }
6.    private RBNode parentOf(RBNode node){
7.        return node != null ? node.parent:null;
8.    }
10.    private RBNode leftOf(RBNode node){
11.        return node != null ? node.left:null;
12.    }
14.    private RBNode rightOf(RBNode node){
15.        return node != null ? node.right:null;
16.    }
18.    private void setColor(RBNode node ,boolean color){
19.        if(node != null){
20.            node.setColor(color);
21.        }
22.    }
24.    /**
25.     * 插入节点后的调整处理
26.     * 1. 2-3-4树 新增元素 2节点添加一个元素将变为3节点 直接合并，节点中有两个元素
27.     *      红黑树：新增一个红色节点，这个红色节点会添加在黑色节点下(2节点) --- 这种情况不需要调整
28.     * 2. 2-3-4树 新增元素 3节点添加一个元素变为4节点合并 节点中有3个元素
29.     *      这里有6中情况，( 根左左 根左右  根右右 根右左)这四种要调整  (左中右的两种)不需要调整
30.     *      红黑树：新增红色节点 会添加到 上黑下红的节点中 = 排序后中间节点是黑色，两边节点是红色
31.     *
32.     *  3. 2-3-4树：新增一个元素 4节点添加一个元素需要裂变：中间元素升级为父节点，新增元素与剩下的其中一个合并
33.     *      红黑树：新增节点是红色+爷爷节点是黑色，父亲节点和叔叔节点为红色 调整为
34.     *              爷爷节点变红色，父亲和叔叔节点变为黑色，如果爷爷节点为root节点则调整为黑色
35.     * @param x
36.     */
37.    private void fixAfterPut(RBNode<K, Object> x) {
38.        x.color = RED;
39.        // 本质上就是父节点是黑色的就不需要调整，对应的 2 3的情况
40.        while(x != null && x != root && x.parent.color == RED){
41.            // 1. x 的父节点是爷爷的 左孩子
42.            if(parentOf(x) == parentOf(parentOf(x)).left){
43.                // 获取当前节点的叔叔节点
44.                RBNode y = rightOf(parentOf(parentOf(x)));
45.                // 情况3
46.                if(colorOf(y) == RED){
47.                    // 说明是 上3的情况  变色处理
48.                    // 父亲节点和叔叔节点设置为黑色
49.                    setColor(parentOf(x),BLACK);
50.                    setColor(y,BLACK);
51.                    // 爷爷节点设置为 红色
52.                    setColor(parentOf(parentOf(x)),RED);
53.                    // 递归处理
54.                    x = parentOf(parentOf(x));
55.                }else{
56.                    // 情况 2
57.                    if(x == parentOf(x).right){
58.                        // 如果x是父节点的右节点那么我们需要先根据 父节点 左旋
59.                        x = parentOf(x);
60.                        leftRotate(x);
61.                    }
62.                    // 叔叔节点为空  对应于 上面的情况2
63.                    // 将父节点变为黑色
64.                    setColor(parentOf(x),BLACK);
65.                    // 将爷爷节点变为红色
66.                    setColor(parentOf(parentOf(x)),RED);
67.                    // 右旋转  根据爷爷节点右旋转
68.                    rightRotate(parentOf(parentOf(x)));
70.                }
71.            }else{
72.                // x 的父节点是爷爷是右孩子
73.                // 获取父亲的叔叔节点
74.                RBNode y = leftOf(parentOf(parentOf(x)));
75.                if(colorOf(y) == RED){
76.                    // 情况3
77.                    setColor(parentOf(x),BLACK);
78.                    setColor(y,BLACK);
79.                    setColor(parentOf(parentOf(x)),RED);
80.                    x = parentOf(parentOf(x));
81.                }else{
82.                    // 情况2
83.                    if( x == parentOf(x).left){
84.                        x = parentOf(x);
85.                        rightRotate(x);
86.                    }
87.                    setColor(parentOf(x),BLACK);
88.                    setColor(parentOf(parentOf(x)),RED);
89.                    leftRotate(parentOf(parentOf(x)));
90.                }
91.            }
92.        }
93.        root.color = BLACK;
94.    }

复制代码

删除节点

红黑树删除操作的本质实在就是删除2-3-4树的叶子节点

2.    private RBNode getNode(K key){
3.        RBNode node = this.root;
4.        while (node != null ){
5.            int cmp = key.compareTo((K) node.key);
6.            if(cmp < 0){
7.                // 在左子树
8.                node = node.left;
9.            }else if(cmp >0){
10.                // 右子树
11.                node = node.right;
12.            }else{
13.                return node;
14.            }
15.        }
16.        return null;
17.    }

复制代码

1. [/code] [code]
2. /**
3.     * 删除节点
4.     * @param key
5.     * @return
6.     */
7.    public V remove(K key){
8.        // 先找到这个节点
9.        RBNode node = getNode(key);
10.        if(node == null){
11.            return null;
12.        }
13.        // 把值存起来 删除后 返回
14.        V oldValue = (V) node.value;
15.        deleteNode(node);
16.        return oldValue;
17.    }
19.    /**
20.     * 删除节点
21.     *   3种情况
22.     * 1.删除叶子节点，直接删除
23.     * 2.删除的节点有一个子节点，那么用子节点来替代
24.     * 3.如果删除的节点右两个子节点，此时需要找到前驱节点或者后继节点来替代
25.     *    可以转换为 1、2的情况
26.     * @param node
27.     */
28.    private void deleteNode(RBNode node){
29.        // 3.node节点有两个子节点
30.        if(node.left !=null && node.right != null){
31.            // 找到要删除节点的后继节点
32.            RBNode successor = successor(node);
33.            // 然后用后继节点的信息覆盖掉 要删除节点的信息
34.            node.key = successor.key;
35.            node.value = successor.value;
36.            // 然后我们要删除的节点就变为了 后继节点
37.            node = successor;
38.        }
39.        // 2.删除有一个子节点的情况
40.        RBNode replacement = node.left != null ? node.left : node.right;
41.        if(replacement != null){
42.            // 替代者的父指针指向原来 node 的父节点
43.            replacement.parent = node.parent;
44.            if(node.parent == null){
45.                // 说明 node 是root节点
46.                root = replacement;
47.            }else if(node == node.parent.left){
48.                // 双向绑定
49.                node.parent.left = replacement;
50.            }else{
51.                node.parent.right = replacement;
52.            }
53.            // 将node的左右孩子指针和父指针都指向null node等待GC
54.            node.left = node.right = node.parent = null;
55.            // 替换完成后需要调整平衡
56.            if(node.color == BLACK){
57.                // fixAfterRemove(replacement)
58.            }
59.        }else if(node.parent == null){
60.            // 说明要删除的是root节点
61.            root = null;
62.        }else{
63.            // 1. node节点是叶子节点 replacement为null
64.            // 先调整
65.            if(node.color == BLACK){
66.                // fixAfterRemove(node)
67.            }
68.            // 再删除
69.            if(node.parent != null){
70.                if(node == node.parent.left){
71.                    node.parent.left = null;
72.                }else{
73.                    node.parent.right = null;
74.                }
75.                node = null;
76.            }
77.        }
78.    }

复制代码

B树和B+树

B树

（Balanced Tree）这个就是我们的多路平衡查找树，叫做B-Tree（B代表平衡）。跟AVL树一样，B树在枝节点和叶子节点存储键值、数据地址、节点引用。它有一个特点：分叉数（路数）永远比关键字数多1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。

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+树的存储布局：

MySQL中的B+Tree有几个特点：

• 它的关键字的数量是跟路数相等的；
  
• B+Tree的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。搜刮到关键字不会直接返回，会到末了一层的叶子节点。比如我们搜刮id=28，固然在第一层直接命中了，但是全部的数据在叶子节点上面，以是还要继续往下搜刮，不停到叶子节点。
  
• B+Tree的每个叶子节点增长了一个指向相邻叶子节点的指针，它的末了一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的布局。
  

总结， B+Tree的特点带来的优势：

• 它是B Tree的变种，B Tree能办理的标题，它都能办理。B Tree办理的两大标题是什么？（每个节点存储更多关键字；路数更多）
  
• 扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵B+Tree拿到所有的数据）
  
• B+Tree的磁盘读写能力相对于B Tree来说更强（根节点和枝节点不保存数据区，以是一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
  
• 排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
  
• 服从更加稳定（B+Tree永远是在叶子节点拿到数据，以是IO次数是稳定的）
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。