红黑树的底层结构实现_红黑树的底层实现

红黑树的定义

红黑树是含有红黑链接并满足以下条件的二叉查找树

1、红链接均为左连接；

2、没有任何一个结点同时和两条红链接相连；

3、该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。

 红黑树中存储元素的结点

因为每个结点都只会有一条指向自己的链接（即它的父结点指向它），我们可以在之前的Node结点中新增一个布尔类型的变量color来表示此链接的颜色。我们规定：如果指向此结点的链接是红色的，那么该变量的值为true；如果指向此结点的链接时黑色的，那么该变量的值为false。例如下图所示，c是当前结点，h指的是它的父结点，所以h的左子结点（即c结点）的color的值是true

 结点API设计：

 代码实现：

/**
     * 结点类
     */
    private class Node {
        /**
         * 存储键
         */
        private Key key;
        //存储值
        private Value value;
        //记录左子结点
        private Node left;
        //记录右子结点
        private Node right;
        //标记父结点指向当前结点的链接是否是红色：true表示是红色，false表示不是红色（即黑色）
        private boolean color;
 
        /**
         * 构造方法
         */
        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;
        }
 
    }

平衡化

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

左旋

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

例如：当前结点为h，它的右子结点为x；

左旋过程：

1、让x的左子结点变为h的右子结点：h.right=x.left；

2、让h成为x的左子结点：x.left=h；

3、让h的color属性变为x的color属性值：x.color=h.color；

4、让h的color属性变为RED：h.color=true；

右旋

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

例如：当前结点为h，它的左子结点为x；

右旋过程：

1、让x的右子结点变为h的左子结点：h.left=x.right；

2、让h成为x的右子结点：x.right=h；

3、让h的color属性变为x的color属性值：x.color=h.color；

4、让h的color属性变为RED：h.color=true；

颜色反转

当一个结点的左子结点和右子结点的color都为RED时，此时只需要把左子结点和右子结点的颜色变为BLACK，同时让当前结点的颜色变为RED即可。

根结点的颜色总是黑色

在结点Node对象中color属性表示的是父结点指向当前结点的连接的颜色，由于根结点不存在父结点，所以每次插入操作后，我们都需要把根结点的颜色设置为黑色。

红黑树的API设计

 红黑树代码实现

/**
 * @author: xuzhilei
 * @create: 2021-12-21
 * @description: 红黑树
 **/
public class RedBlackTree<Key extends Comparable<Key>, Value> {
    /**
     * 根结点
     */
    private Node root;
    /**
     * 记录树中的元素个数
     */
    private int number;
    /**
     * 表示红色链接
     */
    private static final boolean RED = true;
    /**
     * 表示黑色链接
     */
    private static final boolean BLACK = false;
 
    /**
     * 结点类
     */
    private class Node {
        /**
         * 存储键
         */
        private Key key;
        //存储值
        private Value value;
        //记录左子结点
        private Node left;
        //记录右子结点
        private Node right;
        //标记父结点指向当前结点的链接是否是红色：true表示是红色，false表示不是红色（即黑色）
        private boolean color;
 
        /**
         * 构造方法
         */
        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 RedBlackTree() {
        this.root = null;
        this.number = 0;
    }
 
    /**
     * 获取红黑树中的元素个数
     *
     * @return int
     */
    public int size() {
        return number;
    }
 
    /**
     * 判断当前结点x的父结点指向它的链接是否为红色
     *
     * @param x 当前结点
     * @return boolean
     */
    private boolean isRed(Node x) {
        if (x == null) {
            return false;
        }
        return x.color == RED;
    }
 
    /**
     * 左旋转
     * 当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。
     * 前提：当前结点为h，它的右子结点为x；
     * 左旋过程：
     * 1.让x的左子结点变为h的右子结点：h.right=x.left;
     * 2.让h成为x的左子结点：x.left=h;
     * 3.让h的color属性变为x的color属性值：x.color=h.color;
     * 4.让h的color属性变为RED：h.color=true;
     *
     * @param h 当前结点
     * @return h的右子结点x
     */
    private Node rotateLeft(Node h) {
        //获取h结点的右子结点x
        Node x = h.right;
        //找到x结点的左子结点，让x结点的左子结点成为h结点的右子结点
        h.right = x.left;
        //让h成为x的左子结点
        x.left = h;
        //让h的color属性变为x的color属性值
        x.color = h.color;
        //让h的color属性变为RED
        h.color = RED;
        //返回x结点
        return x;
    }
 
    /**
     * 右旋转
     * 当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋
     * 前提：当前结点为h，它的左子结点为x；
     * 右旋过程：
     * 1. 让x的右子结点成为h的左子结点：h.left = x.right;
     * 2. 让h成为x的右子结点：x.right=h;
     * 3. 让x的color变为h的color属性值：x.color = h.color;
     * 4. 让h的color为RED；
     *
     * @param h 当前结点
     * @return h的左子结点x
     */
    private Node rotateRight(Node h) {
        //获取h结点的左子结点x
        Node x = h.left;
        //找到x结点的右子结点，让x结点的右子结点成为h结点的左子结点
        h.left = x.right;
        //让h成为x的右子结点
        x.right = h;
        //让x的color变为h的color属性值
        x.color = h.color;
        //让h的color属性值变为RED
        h.color = RED;
        //返回x结点
        return x;
    }
 
    /**
     * 颜色反转
     * 当某个结点的左子结点是红色，且右子结点也是红色，需要颜色反转
     *
     * @param h 当前结点
     */
    private void flipColors(Node h) {
        //当前结点的color属性值变为RED
        h.color = RED;
        //左子结点和右子结点的color属性都变为BLACK
        h.left.color = BLACK;
        h.right.color = BLACK;
    }
 
    /**
     * 向整个树中插入键值对key-value
     *
     * @param key   待插入键
     * @param value 待插入值
     */
    public void put(Key key, Value value) {
        root = put(this.root, key, value);
        //根结点的color属性总是黑色
        root.color = BLACK;
    }
 
    /**
     * 往指定树h中插入键值对key-value,并返回插入元素后的新树
     *
     * @param h     指定树的根结点
     * @param key   待插入键
     * @param value 待插入值
     */
    private Node put(Node h, Key key, Value value) {
        //如果当前结点为空，则直接创建一个结点并返回此结点
        if (h == null) {
            //元素个数+1
            number++;
            return new Node(key, value, null, null, RED);
        }
 
        //比较结点h的键和参数key的大小
        int comp = key.compareTo(h.key);
        if (comp < 0) {
            //key比当前结点h的键要小，继续向h的左子结点所在的树进行插入操作
            h.left = put(h.left, key, value);
        } else if (comp > 0) {
            //key比当前结点h的键要大，继续向h的右子结点所在的树进行插入操作
            h.right = put(h.right, key, value);
        } else {
            //key与当前结点h的键相等，则用待插入的value替换当前结点的value值
            h.value = value;
        }
 
        //满足左旋转条件：当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。
        if (isRed(h.right) && !isRed(h.left)) {
            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
     *
     * @param key 指定的key
     * @return Value 对应的value
     */
    public Value get(Key key) {
        return get(root, key);
    }
 
    /**
     * 根据key在指定树x中找出对应的value
     *
     * @param x   指定树的根结点
     * @param key 指定的key
     * @return Value 对应的value
     */
    private Value get(Node x, Key key) {
        if (x == null) {
            return null;
        }
        //比较当前结点x的键和参数key的大小
        int comp = key.compareTo(x.key);
        if (comp < 0) {
            //key比当前结点x的键要小，则继续向x的左子结点所在的树进行查找操作
            return get(x.left, key);
        } else if (comp > 0) {
            //key比当前结点x的键要大，则继续向x的右子结点所在的树进行查找操作
            return get(x.right, key);
        } else {
            //key与当前结点x的键相等，则返回结点x的value值
            return x.value;
        }
    }
 
    //测试
    public static void main(String[] args) {
        //创建红黑树
        RedBlackTree<String, String> redBlackTree = new RedBlackTree<>();
 
        //插入元素
        redBlackTree.put("1", "张三");
        redBlackTree.put("2", "李四");
        redBlackTree.put("3", "王五");
 
        //获取树中元素个数
        int size = redBlackTree.size();
        System.out.println(size);
 
        //从树中获取元素
        String s = redBlackTree.get("1");
        System.out.println(s);
 
    }
 
 
}

测试结果：

  以上是个人随手敲的demo，如有不正确的地方，可以在下方留言指正，谢谢。与各位CSDN的伙伴们共勉，每天记录一点点，每天进步一点点