BST

BST 的特性就是左子树都比本节点小，右子树都比本节点大。

private class Node {
    private Key key;
    private Value val;
    private Node left, right;
    public Node(Key key, Value val) {
        this.key = key;
        this.val = val;
    }
}

public class BST<Key extends Comparable<Key>, Value> {
    private Node root;

    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);
        int cmp = key.comapreTo(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;
        return x;
    }

    public Value get(Key key) {
        Node x = root;
        while(x != null) {
            int cmp = key.comapreTo(x.key);
            if (cmp < 0) x = x.left;
            else if (cmp > 0) x = x.right;
            else return x.val;
        }
        return null;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.comapreTo(x.key);
        if (cmp < 0) x.left = delete(x.left, key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else {
            if (x.right == null) return x.left;
            if (x.left == null) return x.right;

            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.count = size(x.left) + size(x.right) + 1;
        return x;
    }

    public Iterable<Key> iterator {
        Queue<Key> q = new Queue<Key>();
        inorder(root, q);
        return q;
    }

    private void inorder(Node x, Queue<Key> q) {
        if (x == null) return;
        inorder(x.left, q);
        q.enqueue(x.key);
        inorder(x.right, q);
    }
}

floor 寻找比 Key 小的数中最大的数

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.comapreTo(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;
}

2-3 Search Trees

Allow 1 or 2 keys per node.

  • 2-node: one key, two children.
  • 3-node: two keys, three children.

Perfect balance. Every path from root to null link has same length. Symmetric order. Inorder traversal yields keys in ascending order.

Insertion

Insertion into a 3-node at bottom.

  • Add new key to 3-node to create temporary 4-node.
  • Move middle key in 4-node into parent.
  • Repeat up the tree, as necessary.
  • If you reach the root and it’s a 4-node, split it into three 2-nodes.

Left-leaning red-black BSTs

  1. Represent 2-3 tree as a BST.
  2. Use “internal” left-leaning links as “glue” for 3-nodes.

Search is the same as for elementray BST(ignore color).

public Val get(Key key) {
    Node x = root;
    while(x != null) {
        int cmp = key.comapreTo(x.key);
        if (cmp < 0) x = x.left;
        else if (cmp > 0) x = x.right;
        else return x.val;
    }
    return null;
}

Red-black BST representation

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

private class Node {
    Key key;
    Value val;
    Node left, right;
    boolean color;
}

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

Left rotation. Orient a right-leaning red link to lean left.

private Node rotateLeft(Node h) {
    assert isRed(h.right);
    Node x = h.right;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    return x;
}

Right rotation. Orient a left-leaning red link to lean right.

private Node rotateRight(Node h) {
    assert isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    return x;
}

Color flip. Recolor to split a 4-node.

private void flipColors(Node h) {
    assert !isRed(h);
    assert isRed(h.right);
    assert isRed(h.left);
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}
  • Right child red, left child black: rotate left.
  • Left child, left-left grandchild red: rotate right.
  • Both children red: flip colors.
private Node put(Node h, Key key, Value val) {
    if (h == null) return new Node(key, val, 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);
}