红黑树-实现

package com.example.demo2;

/**
 * 推荐一本非常详细的树<算法> 第四版java 实现。想要的话下方评论哈
 * @param <Key>
 * @param <Value>
 */
public class RBTree<Key extends Comparable<Key>,Value> {
    private Node root;
    // 左旋：把右链接为红色的节点变成左链接红色
    Node rolateLeft(Node h){
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = Color.BLACK.getIsRed();
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return null;
    }
    public int size(Node x){
        if(x == null) return 0;
        return x.left.N + x.right.N;
    }

    // 右旋：把红色左链接变为红色右链接
    Node rolateRight(Node h){
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = Color.RED.getIsRed();
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }
    private boolean isRed(Node x){
        if(x == null) return false;
        return x.color == Color.RED.getIsRed();
    }
    /**
     * 红黑树插入分为 向单个2-结点插入键值对 1、左链接为红色 2、右链接为红色 需要旋转
     * 向树底部插入新键 如果出现红色右链接需要发生左旋
     * 向一颗双键树插入新键 1、新键最大 2、新健最小 3、新键介于两者之间
     * 红链接需要向上传递
     * @param key
     * @param value
     */
    public void put(Key key,Value value){
        root = put(root,key,value);
        root.color = Color.BLACK.getIsRed();
    }


    public Node put(Node h,Key key,Value value){
        if(h == null) return new Node(key,value,1,Color.RED.getIsRed());
        int cmp = key.compareTo((Key) h.key);
        if (cmp<0) h.left = put(h.left,key,value);
        else if(cmp>0) h.right = put(h.right,key,value);
        else h.val = value;
        if(isRed(h.right) && !isRed(h.left)) h = rolateLeft(h);
        if(isRed(h.left) && isRed(h.left.left)) h = rolateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);
        h.N = size(h.left) + size(h.right);
        return h;
    }
    public void flipColors(Node h){
        h.color = Color.RED.getIsRed();
        h.left.color = Color.BLACK.getIsRed();
        h.right.color = Color.BLACK.getIsRed();
    }
}

// 结点 
package com.example.demo2;

// 红黑树节点数据类型
public class Node<Key extends Comparable<Key>,Value> {
    Key key;
    Value val;
    Node left,right;
    int N; // 子树中的节点总数
    boolean color;
    Node(Key key,Value value,int N,boolean color){
        this.key = key;
        this.val = value;
        this.N = N;
        this.color = color;
    }
}

// color 
package com.example.demo2;


public enum Color {
    RED("红色", true), BLACK("黑色", false);
    private String name;
    private boolean isRed;

    Color(String name, boolean isRed) {
        this.name = name;
        this.isRed = isRed;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public boolean getIsRed() {
        return isRed;
    }

    public void setIsRed(boolean isRed) {
        this.isRed = isRed;
    }
}