一、2-3查找树

《算法》中有以下定义：

• 一棵2-3查找树或为一棵空树，或由以下结点构成：
  • 2-结点，含有一个键（及其对应的值）和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
  • 3-结点，含有两个键（及其对应的值）和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右连接指向的2-3树中的键都大于该结点。
  • 指向一棵空树的链接称为空链接。

图1 2-3树

二、红黑二叉查找树

2.1 定义

《算法》中关于红黑树的定义：

• 红链接均为左链接；
• 没有任何一个结点同时和两条红链接相连；
• 该数是完美平衡的，即任意空链接到根节点的路径上的黑链接数量相同。

满足这样定义的红黑树和相应的2-3树是一一对应的。

图2 红黑二叉查找树

若将红链接相连的结点合并，得到的便是一颗2-3树。

红黑树既是二叉查找树，也是2-3树。

2.2 性质

• 节点是红色或黑色。
• 根是黑色。
• 所有叶子都是黑色（叶子是null节点）。
• 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

2.3 特性

• 近似平衡：性能退化很少，仍有高性能；
• 高度近似logN。

2.4 解决问题

• 解决动态插入，删除操作后二叉查找树性能退化的问题。

2.5 使用场景

• 需要频繁动态插入、删除、查找，且对性能要求较高。

三、代码实现

package thirdStage.day06_RBTree_Javid.RedBlackBST;

import java.util.*;

/**
 * @author Javid Xi
 * @Classname RedBlackBST
 * @Description 红黑树
 * @Date 2021/5/5
 */
public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root; // 根节点

    /**
     * Description: 插入操作
     */
    public void put (Key key, Value val) {
        // 查找key 找到则更新其值， 否则为它新建一个结点
        root = put(root, key, val);
        root.color = BLACK;
    }
    private Node put (Node h, Key key, Value val) {
        if (h == null) return new Node(key, val, 1, RED); // 标准插入操作，和父节点用红链接相连
        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, val);
        else if (cmp > 0) h.right = put(h.right, key, val);
        else h.val = val;

        // 右孩子为红 左孩子为黑
        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)) flipColors1(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

    /**
     * Description: 删除最小键
     */
    private Node moveRedLeft (Node h) {
        // 假设结点h为红色，h.left和h.left.left都是黑色
        // 将h.left或者h.left的子结点之一变红
        flipColors2(h);
        if (isRed(h.right.left)) {
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
        }
        return h;
    }

    public void deleteMin () {
        if (!isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }
        root = deleteMin(root);
        if (isEmpty()) root.color = BLACK;

    }
    private Node deleteMin (Node h) {
        if (h.left == null) return null;
        if (!isRed(h.left) && !isRed(h.left.left)) {
            h = moveRedLeft(h);
        }
        h.left = deleteMin(h.left);
        return balance(h);
    }

    /**
     * Description: 修复 平衡
     */
    private Node balance (Node h) {
        if (isRed(h.right)) h = rotateLeft(h);

        // 右孩子为红 左孩子为黑
        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)) flipColors1(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }
    /**
     * Description: 删除最大键
     */
    private Node moveRedRight (Node h) {
        // 假设结点h为红色，h.right和h.right.left都是黑色
        // 将h.right或者h.right的子结点之一变红
        flipColors2(h);
        if (!isRed(h.left.left)) {
            h = rotateRight(h);
        }
        return h;
    }

    public void deleteMax () {
        if (!isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }
        root = deleteMax(root);
        if (isEmpty()) root.color = BLACK;
    }

    public Node deleteMax (Node h) {
        if (isRed(h.left)) {
            h = rotateRight(h);
        }
        if (h.right == null) return null;
        if (!isRed(h.right) && !isRed(h.right.left)) {
            h = moveRedRight(h);
        }
        h.right = deleteMax(h.right);
        return balance(h);
    }

    /**
     * Description: 删除key
     */
    public void delete (Key key) {
        if (isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }
        root = delete(root, key);
        if (!isEmpty()) root.color = BLACK;
    }

    private Node delete (Node h, Key key) {
        if (key.compareTo(h.key) < 0) {
            if (!isRed(h.left) && !isRed(h.left.left)) {
                h = moveRedLeft(h);
            }
            h.left = delete(h.left, key);
        } else {
            if (isRed(h.left)) h = rotateRight(h);
            if (key.compareTo(h.key) == 0 && (h.right == null)) return null;
            if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
            if (key.compareTo(h.key) == 0) {
                h.val = get(h.right, min(h.right).key);
                h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            } else h.right = delete(h.right, key);
        }
        return balance(h);
    }

    /**
     * Description: 判空
     */
    private boolean isEmpty () {
        return root == null;
    }

    /******************* 基本操作 ***********************/
    /**
     * Description: 左旋
     */
    private Node rotateLeft (Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

    /**
     * Description: 右旋
     */
    private Node rotateRight (Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

    /**
     * Description: 颜色转换 子结点由红变黑 父结点由黑变红
     */
    private void flipColors1 (Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    /**
     * Description: 颜色转换 子结点变红 父结点变黑
     */
    private void flipColors2 (Node h) {
        h.color = BLACK;
        h.left.color = RED;
        h.right.color = RED;
    }

    /******************* 结点定义 ***********************/
    /**
     * Description: 红黑树结点
     */
    private class Node {
        Key key; // 键
        Value val; // 值
        Node left, right;
        int N; // 子树中的结点总数
        boolean color;

        public Node(Key key, Value val, int N, boolean color) {
            this.key = key;
            this.val = val;
            this.N = N;
            this.color = color;
        }
    }

    /**
     * Description: 判断是否是红结点
     */
    private boolean isRed (Node x) {
        if (x == null) return false;
        return x.color == RED;
    }

    /**
     * Description: 返回子树结点数量
     */
    private int size (Node x) {
        if (x == null) return 0;
        return x.N;
    }
    public int size() {
        return size(root);
    }

    /**
     * Description: 二叉搜索树中求最小最大结点
     */
    public Key min () {
        return min(root).key;
    }
    private Node min (Node x) {
        if (x.left == null) return x;
        return min(x.left);
    }

    /**
     * Description: 二叉搜索树获取一个结点值
     */
    public Value get (Key key) {
        return get(root, key);
    }
    private Value get (Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) return get(x.left, key);
        if (cmp > 0) return get(x.right, key);
        else return x.val;
    }

    /******************* 遍历 ***********************/
    /**
     * Description: 中序遍历
     */
    public List<Value> inOrder () {
        List<Value> list = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        Node node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }
        return list;
    }

    /**
     * Description: 层序遍历
     */
    public List<Value> levelOrder () {
        List<Value> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node != null) {
                list.add(node.val);
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return list;
    }
}