红黑树 | 国哥的博客

二叉查找树（BST）

定义：一颗二叉树，每个结点都有一个Comparable的键且每个结点的键都大于其左子树的任意结点的键而小于右子树的任意结点的键。

二叉查找树的图像形状
查找
插入



public class BST<Key extends Comparable<Key>, Value> {

    private Node root;

    private class Node {
        private Key key; //键
        private Value val;
        private Node left, right; //指向子树的链接
        private int N; //以该结点为根的子树中的节点总数

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

    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null) {
            return 0;
        } else {
            return x.N;
        }
    }

    //查找
    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);
        else if (cmp > 0) return get(x.right, key);
        else return x.val;
    }

    //插入
    public void put(Key key, Value val) {
        root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val) {
        if (x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = put(x.left, key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else x.val = val;
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    //取最小key
    public Key min() {
        return min(root).key;
    }

    private Node min(Node x) {
        if (x.left == null) return x;
        return min(x.left);
    }

    //向下取之整
    public Key floor(Key key) {
        Node x = floor(root, key);
        if (x == null) return null;
        return x.key;
    }

    private Node floor(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp == 0) return x;
        if (cmp < 0) return floor(x.left, key);
        Node t = floor(x.right, key);
        if (t != null) return t;
        else return x;
    }

    //max()
    //ceiling()
}

二分查找法
性能分析

平衡查找树

2-3树

定义：一颗2-3树或为空树，或为以下结点组成：

2-结点：含有一个键(及值)和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
3-结点：含有两个键(及值)和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。

一颗完美平衡的2-3查找树中的所有空链接到根结点的距离都是相同的。

查找

要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。

插入

向2-结点插入新键
- 只要把这个2-结点替换为一个3-结点，将要插入的键保存在其中即可
向只有3-结点插入新键
- 创建一个4-结点很方便，因为很容易将它转换为一颗由3个2-结点组成的2-3树
向父节点为2-结点的3-结点插入新键
- 同上，但是不会为中键创建一个新结点，而是将其移动至原来的父结点中
向父节点为3-结点的3-结点插入新键
- 一直向上不断分解临时的4-结点并将中键插入更高的父结点，直至遇到一个2-结点并将它替换为一个不需要继续分解的3-结点，或者是到达3-结点的根

性能：一颗大小为N的2-3树，查找和插入操作访问的结点必然不超过logN个。高度在log3 N 与log2 N之间。

红黑二叉查找树

一种等价的定义：

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

红链接：将两个2-结点连接起来构成一个3-结点
黑链接：2-3树中的普通链接

示例图
旋转
- 左旋
- 右旋
插入
- 新键最小
- 新键最大
- 新键介于中间
变色

package redblack;

public class RedBlackBST<Key extends Comparable<Key>, Value> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;

    public void put(Key key, Value val) {
        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)) flipColors(h);
        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

    private void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    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 = size(h.left) + size(h.right) + 1;
        return x;
    }

    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 = size(h.left) + size(h.right) + 1;
        return x;
    }

    private boolean isRed(Node x) {
        if (x == null) return false;
        else return x.color == RED;
    }

    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null) {
            return 0;
        } else {
            return x.N;
        }
    }

    private class Node {

        private Key key;
        private Value val;
        private Node left, right;
        private int N;
        private boolean color;

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

    }
}

结论：
性能: 一颗大小为N的红黑树，根结点到任意结点的平均路径长度为logN。
和典型的二叉查找树相比，构造的长度比它低40%左右。

顺序查询（无序链表）最坏情况：查找（N）插入（N）平均情况:查找(N/2) 插入(N)
二分查找（有序数组）最坏情况：查找（logN）插入（N）平均情况:查找(logN) 插入(N/2)
二叉树查找（BST）最坏情况：查找（N）插入（N）平均情况:查找(1.39logN) 插入(1.39logN)
2-3树查找（红黑树）最坏情况：查找（2logN）插入（2logN）平均情况:查找(1.00logN) 插入(1.00logN)

约束条件

节点只能是红色或黑色
根节点必须是黑色
所有NIL 节点都是黑色的
一条路径上不能出现相邻的两个红色节点
在任何递归子树内，根节点到叶子节点的所有路径上包含相同数目的黑色节点

左旋：
左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

treeMap 源码实现


private void rotateLeft(TreeMap.Entry<K, V> p) {
       if (p != null) {
           TreeMap.Entry<K, V> r = p.right;
           p.right = r.left;
           if (r.left != null) {
               r.left.parent = p;
           }

           r.parent = p.parent;
           if (p.parent == null) {
               this.root = r;
           } else if (p.parent.left == p) {
               p.parent.left = r;
           } else {
               p.parent.right = r;
           }

           r.left = p;
           p.parent = r;
       }

   }

右旋：
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。


private void rotateRight(TreeMap.Entry<K, V> p) {
       if (p != null) {
           TreeMap.Entry<K, V> l = p.left;
           p.left = l.right;
           if (l.right != null) {
               l.right.parent = p;
           }

           l.parent = p.parent;
           if (p.parent == null) {
               this.root = l;
           } else if (p.parent.right == p) {
               p.parent.right = l;
           } else {
               p.parent.left = l;
           }

           l.right = p;
           p.parent = l;
       }

   }