Java实现红黑树(平衡二叉树)的详细过程

目录

• 前言
• 红黑二叉查找树

• 2-3树
• 2-3树的插入操作

/**
 * <p>
 *     符号表的基本API
 * </p>
 * @author qzlzzz
 * @version 1.0
 * @since 2021/10/8
 */
public interface RedBlackBST<Key extends Comparable<Key>,Value> {
    /**
     * 根据Key在符号表中找到Value
     * @param key the key
     * @return the value of key
     */
    Value get(Key key);
    /**
     * 插入key-value，如果符号表中有Key，且Key不为空则将该Key的Value转为传入的Value
     * @param key the-key
     * @param value the-value
     */
    void put(Key key,Value value);
    /**
     * 根据Key去符号表中删除Key
     * @param key the key
     */
    void delete(Key key);
}

    /**
     * 根据位置返回键，如果没有返回null
     * @param k the index of key
     * @return the key
     */
    Key select(int k);
    /**
     * 返回红黑树中最小的键
     * @return the min key in this tree
     */
    Key min();
    /**
     * 返回红黑树中最大的键
     * @return the max key in this tree
     */
    Key max();
    /**
     * 返回小于该键的数量
     * @param key the key
     * @return amount of key small than the key
     */
    int rank(Key key);

/**
 * <h3>
 *     红黑树的实现,博客:https://www.cnblogs.com/qzlzzz/p/15395010.html
 * </h3>
 * @author qzlzzz
 * @since 2021/10/12
 * @version 1.0
 */
public class RedBlackBST<Key extends Comparable<Key>,Value> {
    private Node root;//根节点
    //<父结点>指向自己<子结点>的链接是黑色的
    private static final boolean RED = true;
    //<父结点>指向自己<子结点>的链接是黑色的
    private static final boolean BLACK = false;
    /**
     * <p>红黑树的结点定义</p>
     * @author qzlzzz
     */
    private class Node{
        private boolean color;//指向该结点的链接的颜色
        private Key key;//键
        private Value value;//值
        private Node left,right;//该结点指向左结点的链接和右结点的链接
        private int n;//该子树的结点树
        public Node(Key key,Value value,boolean color,int n){
            this.key = key;
            this.value = value;
            this.color = color;
            this.n = n;
        }
    }
}

    /**
     * 计算红黑树的结点总数,内部调用了{@link RedBlackBST#size(Node)}
     * @return
     */
    public int size(){
        return size(root);
    }
    //计算某个子树的结点总数
    private int size(Node x){
        if (x == null) return 0;
        else return x.n;
    }
    /**
     * 将红色右链接变为左链接，总体有序性不变，子树结点数量不变
     * @param h
     * @return
     */
    private Node rotateLeft(Node h){
        Node t = h.right;
        h.right = t.left;
        t.left = h;
        t.color = h.color;
        h.color = RED;
        t.n = h.n;//转换后子树的结点是不变的，
        h.n = size(h.left) + size(h.right) + 1;
        return t;
    }

    //判断链接是否为红色，不是返回false
    private boolean isRed(Node x){
        if (x == null) return false;
        return x.color;
    }

    /**
     * <p>若左右两边的链接皆为红色，将两边链接颜色设置为黑色，并使指向自己链接的颜色设为红</p>
     * @param x
     */
    private void changeColor(Node x){
        x.color = true;
        x.left.color = false;
        x.right.color = true;
    }

    /**
     * 通过键来查找值，内部调用{@link RedBlackBST#get(Node, Comparable)}
     * @param key
     * @return
     */
    public Value get(Key key){
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        return get(root,key);
    }
    private Value get(Node x,Key key){
        for (;;){
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x.value;
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
    }

    /**
     * 插入键值对,内部使用{@link RedBlackBST#put(Node, Comparable, Object)}
     * @param key
     * @param value
     */
    public void put(Key key,Value value){
        if (key == null) throw new IllegalArgumentException("argument to put() is null");
        root = put(root,key,value);
        root.color = false;
    }
    private Node put(Node x,Key key,Value value){
        if (x == null) return new Node(key,value,RED,1);
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {x.value = value;}
        else if (cmp < 0) x.left = put(x.left,key,value);
        else x.right = put(x.right,key,value);
        if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
        if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
        if (isRed(x.left) && isRed(x.right)) changeColor(x);
        x.n = size(x.left) + size(x.right) + 1;
        return x;
    }

    /**
     * 根据位置返回键,内部调用{@link RedBlackBST#select(Node, int)}
     * @param k
     * @return
     */
    public Key select(int k){
        return select(root,k);
    }
    private Key select(Node x,int k){
        while(x != null){
            int t = x.left.N;
            if (t > k) x = x.left;
            else if (t < k){
                x = x.right;
                k = k - t - 1;
            }
            else return x.key;
        }
        return null;
    }
    /**
     * 根据键，返回该键的数量，内部调用{@link RedBlackBST#rank(Node, Comparable)}
     * @param key
     * @return
     */
    public int rank(Key key){
        return rank(root,key);
    }
    private int rank(Node x,Key key){
        while (x != null){
            int cmp = key.compareTo(x.key);
            int count = x.left.N;
            if (cmp == 0) return (count < root.N ? count : 1 + root.left.N + count);
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
        return 0;
    }