红黑树就是将二三树表示成二叉树的形式，极大地简化了算法。

红黑树的基本思想就是将二三树中的三节点表示成两个二节点，而这两个二节点之间使用红色的连接，普通连接使用黑色的连接。

红黑树中的每个节点都有以下性质：

• 没有一个节点同时拥有两个红连接

• 每个空节点到根节点路径上黑色连接的数量都是相同的

• 红连接只会出现在左边

下图展示了二三树和红黑树的等价表示

查找操作

与普通的二叉树查找树的算法一致，忽略节点的颜色即可。

旋转操作

有时候会出现下图红连接在右侧的情况。这时候就需要通过左旋操作，使其符合红黑树的性质。

下图展示了旋转之后的样子

代码如下：

private Node rotateLeft(Node node) {
    Node right = node.right;
    node.right = right.left;
    right.left = node;
    int color = right.color;
    right.color = node.color;
    node.color = color;
    return right;
}

有时候也会用到右旋操作。右旋操作的目的是为了方便某些操作，等操作结束之后再通过左旋恢复原样。

翻转操作

有时候会出现下图这种双重红连接的情况，这种情况对应的就是二三树中的四节点。此时之需要改变父节点的颜色即可。这种操作叫做翻转操作。

下图是变化之后的图

代码如下：

private Node flipColor(Node node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
    return node;
}

插入操作

在红黑树中进行插入操作时，与普通的二叉查找树一样。每次新增一个子节点时，需要将新增的节点标记成红色。再通过旋转、翻转操作，维持红黑树的性质。

每次插入之后，需要执行以下步骤：

• 如果右子节点是红色的，左子节点是黑色的，执行左旋操作

• 如果左子节点和它的子节点都是红的，执行右旋操作

• 如果两个子节点都是红色的，执行翻转操作

代码如下：

private Node put(Node node, Key key, Value value) {
    // 创建一个新的红色的节点
    if(node == null) {
        return new Node(key, value, RED);
    }
 
    // 定位到需要插入的节点
    int compare = key.compareTo(node.key);
    if(compare < 0) {
        node.left = put(node.left, key, value);
    } else if(compare > 0) {
        node.right = put(node.right, key, value);
    } else {
        node.value = http://www.mamicode.com/node.value;>

性能

红黑树的插入、查找、删除操作的复杂度均为logN。

完整代码
public class RedBlackTree<Key extends Comparable<Key>, Value> {
    private static final int RED = 1;
    private static final int BLACK = 0;
 
    private class Node {
        Key key;
        Value value;
        Node left;
        Node right;
        int color;
 
        Node(Key key, Value value, int color) {
            this.key = key;
            this.value = http://www.mamicode.com/value;>