北海道恋人

2020-05-25 21:19 已编辑门头沟学院 Java

关注

数据结构复习之红黑树B树B+树（HashMap底层红黑树，磁盘I/OB树、数据库索引B+树）

五、红黑树

2-3查找树能保证在插入元素之后，树依然保持平衡状态，它的最坏情况下所有子结点都是2-结点，树的高度为lgN，相比普通的二叉查找树保证了最坏情况下的时间复杂度。红黑树是2-3树思想的简单实现

红黑树主要是对2-3树进行编码，红黑树背后的基本思想是（标准的二叉查找树）和一些额外的信息替换3-结点来表示2-3树。所以将树中的链接分为两种类型：

红链接：将两个2-结点链接起来构成一个3-结点（红链接只能是左斜链接）

黑链接：是2-3树中的普通链接

红黑树定义：

红链接均为左链接
没有任何一个结点同时和两条红链接相连
红黑树是黑色平衡的，即任意空链接到根结点的路径上黑链接数量相同
将红黑树水平绘制就变成你熟悉的2-3树了
*

1、红黑树的平衡化

对红黑树进行一些增删改操作后，很有可能会出现红色的右链接或者两条连着的红链接。这些不满足红黑树的定义，所以我们需要通过旋转进行修复，让红黑树保持平衡。

左旋：

左旋时机：当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋

左旋过程：

E.right = S.left
S.left = E
E.color = S.color
S.color = false （变为黑***r>

右旋：

当某个结点的左子结点为红色，且左子结点的左子结点也是红色。需要右旋

(tips:右旋相当于把原来的临时4-结点变为三个2-结点，提升中间结点熟悉吧)

优选过程：

S.left = E.right
E.right = S
S.color = E.color
E.color = false

这仍是有问题的，因为右侧不允许出现红链接。所以后续会处理

2、红黑树插入算法

向单个2-结点中插入新键

一棵只含有一个键的红黑树只含有一个2-结点，插入另一个键后，我们需要马上旋转

如果新插入的结点小于当前结点，则新增一个红色结点即可
如果新城结点大于当前结点，会出现右红链接，则需要将树左旋，保证红黑树的特性

向底部的2-结点插入新键

用二叉查找树的方式向红黑树中插入一个新键，会在树的底部增加一个结点（保证有序性），区别在于：我们用红链接将其与其父结点相连

插入C，小于E，进入左子树
C>A，放入A的右子结点
加上红链接（在右侧，需要左旋）
左旋

颜色反转

当一个结点的左子结点和右子结点的color都为红色时，也就是出现了临时4-结点，此时需要把左子结点和右子结点的color变为black，同时让当前结点的颜色变为红色

（tips：相当于将4-结点的中间元素提升与其父结点组成3-结点）

向一棵双键树（即一个3-结点）中插入新键

可以有三种情况：

新键>原树中的两个键
插入c，c>b && c>a 所以c放入b的右子结点
与父结点建立红链接，形成临时4-结点
颜色反转(如果b为整个树根结点则将b.color = false)
新键>原树中一个键
- 插入b，假如a<b<c，进入a的右子结点
- 与a建立红链接（在右侧，需要左旋）
- 左旋后形成左边连续两个红链接，需要右旋
- 提升b，下沉c
- 颜色反转
新键不大于原树中的两个键
- 插入a,a<b<c，所以a放在b的左子结点，建立红链接
- 左边连续两个红链接，需要右旋
- 提升b，颜色反转

向树底部的3-结点插入新键

分析那么多步骤：跟着也分析一波呗

出现两个连续左红链接，需要右旋，提升R，下沉S
颜色反转,E-R之间出现红链接
右侧出现红链接，需要左旋

大功告成，看到这你会发现也不难其实。

六、手搓红黑树

又到手搓环节，激动嘛，跟着写一遍试试呗，吹爆面试官

package TreeTest;

public class RedBlackTree<Key extends Comparable<Key>,Value> {
    //定义树的根结点
    private Node root;
    //记录树中元素个数
    private int N;
    //红色链接
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    //左旋转
    private Node rotateLeft(Node h){
        //找出当前结点的右子结点
        Node x = h.right;
        //将x的左子结点放到h的右子结点处
        h.right = x.left;
        //将x提升，把h作为x的左子结点
        x.left = h;
        h.color = x.color;
        x.color = BLACK;
        return x;
    }
    //判断当前结点的color是否为RED
    private boolean isRed(Node h){
        if(h==null){
            return false;
        }
        return h.color==RED;
    }
    //右旋转
    private Node rotateRight(Node h){
        //找到当前结点的左子结点
        Node x = h.left;
        //将x的右子结点挂到h的左子结点
        h.left = x.right;
        x.right = h;
        return x;
    }
    //颜色反转
    private void flipColors(Node h){
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }
    //在整棵树中插入结点
    public void put(Key key,Value value){
        root = put(root,key,value);
        //根结点颜色置为BLACK
        root.color = BLACK;
    }
    private Node put(Node h,Key key,Value value){
        //如果知道不存在结点的位置，就可以将新增结点放入位置
        if(h == null){
            N++;
            return new Node(key,value,null,null,RED);
        }
        //比较要插入结点与当前结点大小
        //要插入的结点大于当前结点的key
        int cmp = key.compareTo(h.key);
        if (cmp>0){
            h.right = put(h.right,key,value);
        }else if (cmp<0){
            //要插入的结点小于当前结点的key
            h.left = put(h.left,key,value);
        }else{
            //要插入结点的key与当前结点的key相同，替换当前位置的value
            h.value = value;
        }
        //判断是否需要左旋
        //左旋条件：右侧出现红链接
        if(isRed(h.right)){
            //参数为h的原因是：要根据当前结点寻找不合规则的左右结点
            h = rotateLeft(h);
        }
        //判断是否需要右旋
        //右旋条件：左侧连续两个红链接
        if(isRed(h.left) && isRed(h.left.left)){
            h = rotateRight(h);
        }
        //颜色反转
        if(isRed(h.left) && isRed(h.right)){
            flipColors(h);
        }
        return h;
    }
    //根据key，从树中找到对应的value
    public Value get(Key key){
        return get(root,key);
    }
    private Value get(Node h,Key key){
        if(h == null){
            //没有要找的结点
            return null;
        }
        //判断该节点的key值该去左子树还是右子树
        int cmp = key.compareTo(h.key);
        if(cmp > 0){
            return get(h.right,key);
        }else if (cmp < 0){
            return get(h.left,key);
        }else{
            return h.value;
        }
    }
    //获取树中元素个数
    public int size(){
        return N;
    }
    //结点结构
    private class Node {
        private Key key;
        private Value value;
        //该结点指向其父结点的链接颜色
        public boolean color;
        //记录左右子结点
        private Node left;
        private Node right;
        public Node(Key key,Value value,Node left,Node right,boolean color){
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }
    }

    public static void main(String[] args) {
        RedBlackTree<Integer, String> bt = new RedBlackTree<>();
        bt.put(4, "二哈");
        bt.put(1, "张三");
        bt.put(3, "李四");
        bt.put(5, "王五");
        System.out.println(bt.size());
        System.out.println(bt.get(1));
        bt.put(1,"老三");
        System.out.println(bt.get(1));
        System.out.println(bt.size());
    }
}

七、B树与B+树

B树：

B树中允许一个结点中包含多个Key，可以是3个、4个甚至更多。我们可以选取一个参数M，来构造一个B树（其实就是一个n-结点的树）

每个结点最多有M-1个Key，并且以升序排序
每个结点最多有M个子结点
根结点至少要有两个子结点

B树的应用：

B树在磁盘IO中使用

因为磁盘的访问速度较慢，所以访问时一般都会读取一段空间内的所有数据保存到内存中，利用局部性原理提高数据的查询效率。现在计算机一般采用页作为管理存储器的逻辑块，文件系统的设计者利用磁盘预读原理，将一个结点的大小设置为等于一个页，这样每个结点只需要一次I/O就可以完全载入。这样三层的B树就可以容纳102410141024差不多10亿个数据。大大提高了IO效率

B+树：

B+树顾名思义就是B树的变形，与B树的差异在于