3. 查找

基于有序链表的二分查找

public class BinarySearchST<Key extends Comparable<Key>, Value> {
    private Key[] keys;
    private Value[] vals;
    private int N;
    public BinarySearchST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Object[capacity];
    }
    public int size() {
        return N;
    }
    public int rank(Key key) {
        int lo =  0, hi = N - 2;
        while(lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0 ) {
                hi = mid - 1;
            } else if (cmp > 0) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return lo;
    }
    public void put(Key key, Value val) {
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            vals[i] = val;
            return;
        }
        for(int j = N; j > i; j--) {
            keys[j] = keys[j - 1];
            vals[j] = vals[j - 1];
        }
        keys[i] = key;
        vals[i] = val;
        N++;
    } 
}

二叉树查找

public class BST<Key extends Comparable<Key> , Value> {
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;
        private int N;
        
        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }
    
    private Node root;
    public int size() {
        return size(root);
    }
    private int size(Node x) {
        if (x == null) {
            return 0;
        }
        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.value;
        }
    }
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }
    private Node put(Node x, Key key, Value value) {
        if (x == null) {
            return new Node(key, value, 1);
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = put(x.left, key, value);
        } else if(cmp > 0) {
            x.right = put(x.right, key, value);
        } else {
            x.value = value;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    public Key min() {
        return min(root).key;
    }
    private Node min(Node x) {
        if (x.left == null) { return x; }
        return min(x.left);
    }
    public Key max() {
        return max(root).key;
    }
    private Node max(Node x) {
        if (x.right == null) {
            return x;
        }
        return max(x.right);
    }
    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;
        }
    }
    public Key select(int k) {
        return select(root, k).key;
    }
    private Node select(Node x, int k) {
        if (x == null) {return null; }
        int t = size(x.left);
        if (t > k) {
            return select(x.left, k);
        } else if(t < k) {
            return select(x.right, k);
        } else {
            return x;
        }
    }
    public int rank(Key key) {
        return rank(key, root);
    }
    private int rank(Key key, Node x) {
        if (x == null) {return 0; }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return rank(key, x.left);
        } else if (cmp > 0) {
            return rank(key, x.right);
        } else {
            return size(x.left);
        }
    }
    public void deleteMin() {
        root = deleteMin(root);
    }
    private Node deleteMin(Node x) {
        if (x.left == null) {
            return x.right;
        }
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    public Iterable<Key> keys() {
        return keys(min(), max());
    }
    private Iterable<Key> keys(Key lo, Key hi) {
        Queue<Key> queue = new Queue<Key>();
        keys(root, queue, lo, hi);
        return queue;
    }
    private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
        if (x == null) { return; }
        int cmplo = lo.compareTo(x.key);
        int cmphi = hi.compareTo(x.key);
        if (cmplo < 0) {
            keys(x.left, queue, lo, hi);
        }
        if (cmplo <= 0 && cmphi >= 0) {
            queue.enqueue(x.key);
        }
        if (cmphi > 0) {
            keys(x.right, queue, lo, hi);
        }
    }
}

红黑二叉查找树

红黑二叉树找背后的基本思想是用标准的二叉查找树和(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。将树中的链接分为两种类型：红链接将两个2-结点连接起来构成一个3-结点，黑链接则是2-3树中的普通链接。
另一种定义：
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private Node root;
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private class Node {
        Key key;
        Value value;
        Node left, right;
        int N;
        boolean color;
        public Node(Key key, Value value, int N, boolean color) {
            this.key = key;
            this.value = value;
            this.color = color;
            this.N = N;
        }
        private boolean isRed(Node h) {
            if (h == null) {
                return false;
            }
            return h.color == RED;
        }
        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;
        }
        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;
        }
        private void filpColors(Node h) {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }
        private int size(Node x) {
            return x.N;
        }
        private Node put(Node h, Key key, Value value) {
            if (h == null) {
                return new Node(key, value, 1, RED);
            }
            int cmp = key.compareTo(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.value = value;
            }
            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)) {
                filpColors(h);
            }
            h.N = size(h.left) + size(h.right) + 1;
            return h;
        }
    }
}

散列表

基于拉链表的散列表

public class SeparateChainingHashST<Key, Value> {
    private int N;
    private int M;
    private SequentialSearchST<Key, Value>[] st;
    public SeparateChainingHashST() {
        this(997);
    }
    public SeparateChainingHashST(int M) {
        this.M = M;
        st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
        for(int i = 0; i < M; i++) {
            st[i] = new SequentialSearchST();
        }
    }
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    public Value get(Key key) {
        return (Value)st[hash(key)].get(key);
    }
    public void put(Key key, Value value) {
        st[hash(key)].put(key, value);
    }
}

基于线性探测的符号表

public class LinearProbingHashST<Key, Value> {
    private int N;
    private int M = 16;
    private Key[] keys;
    private Value[] values;
    
    public LinearProbingHashST() {
        keys = (Key[]) new Object[M];
        values = (Value[]) new Object[M];
    }
    private int hash(Key key) { 
        return (key.hashCode()  & 0x7ffffff) % M;
    }
    public void resize() {
        
    }
    private void resize(int cap) {
        LinearProbingHashST<Key, Value> t;
        t = new LinearProbingHashST<Key, Value>();
        for(int i = 0; i < M; i++) {
            if (keys[i] != null) {
                t.put(keys[i], values[i]);
            }
            keys = t.keys;
            values = t.values;
            M = t.M;
        }
    }
    public void put(Key key, Value value) {
        if (N > M / 2) {
            resize(2 * M);
        }
        int i;
        for(i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                values[i] = value;
                return;
            }
            keys[i] = key;
            values[i] = value;
            N++;
        }
    }
    public Value get(Key key) {
        for(int i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                return values[i];
            }
        }
        return null;
    }
    public void delete(Key key) {
        if (!contains(key)) { return; }
        int i = hash(key);
        while(!key.equals(keys[i])) {
            i = (i + 1) % N;
        }
        keys[i] = null;
        values[i] = null;
        i = (i + 1) % M;
        while(keys[i] != null) {
            Key keyToRedo = keys[i];
            Value valueToRedo = values[i];
            keys[i] = null;
            values[i] = null;
            N--;
            put(keyToRedo, valueToRedo);
            i = (i + 1) % N;
        }
        N--;
        if (N > 0 && N == M / 8) {
            resize(M / 2);
        }
    }
    private boolean contains(Key key) {
        for(int i = 0; i < M; i++) {
            if (keys[i].equals(key)) {
                return true;
            }
        }
        return false;
    }
}