BinarySearchST

简书 賈小強
转载请注明原创出处，谢谢！

package com.lab1.test3;

import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchST<Key extends Comparable<Key>, Value> {
    private int n;
    private Key[] keys = (Key[]) new Comparable[2];
    private Value[] values = (Value[]) new Object[2];

    private void resize(int capacity) {
        Key[] tempk = (Key[]) new Comparable[capacity];
        Value[] tempv = (Value[]) new Object[capacity];
        for (int i = 0; i < n; i++) {
            tempk[i] = keys[i];
            tempv[i] = values[i];
        }
        keys = tempk;
        values = tempv;
    }

    private int rank(Key key) {
        int lo = 0;
        int hi = n - 1;
        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;
    }

    private Value get(Key key) {
        int i = rank(key);
        if (i < n && key.compareTo(keys[i]) == 0) {
            return values[i];
        }
        return null;
    }

    private Iterable<Key> keys() {
        Queue<Key> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            queue.add(keys[i]);
        }
        return queue;
    }

    private void delete(Key key) {
        int i = rank(key);
        if (contains(key)) {
            for (int j = i; j < n - 1; j++) {
                keys[j] = keys[j + 1];
                values[j] = values[j + 1];
            }
            keys[n - 1] = null;
            values[n - 1] = null;
            n--;
            if (n == keys.length / 4) {
                resize(keys.length / 2);
            }
        }
    }

    private boolean contains(Key key) {
        return get(key) != null;
    }

    private boolean isEmpty() {
        return n == 0;
    }

    private int size() {
        return n;
    }

    private void put(Key key, Value value) {
        int i = rank(key);
        if (i < n && key.compareTo(keys[i]) == 0) {
            values[i] = value;
            return;
        }

        if (n == keys.length) {
            resize(keys.length * 2);
        }
        for (int j = n - 1; j > i - 1; j--) {
            keys[j + 1] = keys[j];
            values[j + 1] = values[j];
        }
        keys[i] = key;
        values[i] = value;
        n++;
    }

    public static void main(String[] args) {
        BinarySearchST<String, Integer> st = new BinarySearchST<>();
        String test = "S E A R C H E X A M P L E";
        String[] keys = test.split(" ");
        for (int i = 0; i < keys.length; i++) {
            st.put(keys[i], i);
        }
        System.out.println("size         = " + st.size());
        System.out.println("isEmpty      = " + st.isEmpty());
        System.out.println("contains     = " + st.contains("S"));
        st.delete("S");
        System.out.println("contains     = " + st.contains("S"));
        for (String key : st.keys()) {
            System.out.println(key + " " + st.get(key));
        }
    }
}

输出

isEmpty      = false
contains     = true
contains     = false
A 8
C 4
E 12
H 5
L 11
M 9
P 10
R 3
X 7

Happy learning !!