알고리즘) 2장 코드

 Sequential Search Symbol Table (연결 리스트 이용) (12, 13, 14페이지)

class Node<K,V> {
    K key;
    V value;
    Node<K,V> next;
    public Node(K key, V value, Node<K,V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

public class SequentialSearchST<K,V> {
    private Node<K,V> first;
    int N;

    public V get(K key) {
        for (Node<K,V> x = first; x != null; x = x.next)
            if (key.equals(x.key))
                return x.value;
        return null;
    }

    public void put(K key, V value) {
        for (Node<K,V> x = first; x != null; x = x.next)
            if (key.equals(x.key)) {
                x.value = value;
                return;
            }
        first = new Node<K,V>(key, value, first);
        N++;
    }

    public void delete(K key) {
        if (key.equals(first.key)) {
            first = first.next;
            N--;
            return;
        }
        for (Node<K,V> x = first; x.next != null; x = x.next) {
            if (key.equals(x.next.key)) {
                x.next = x.next.next;
                N--;
                return;
            }
        }
    }

    public Iterable<K> keys() {
        ArrayList<K> keyList = new ArrayList<K>(N);
        for (Node<K,V> x = first; x != null; x = x.next)
            keyList.add(x.key);
        return keyList;
    }

    public boolean contains(K key) { return get(key) != null; }
    public boolean isEmpty() { return N == 0; }
    public int size() { return N; }
}

 
 
 
 
 

 Binary Search Symbol Table (정렬된 배열 이용) (16, 17, 18, 19, 20페이지)

public class BinarySearchST<K extends Comparable<K>, V> {
    private static final int INIT_CAPACITY = 10;
    private K[] keys;
    private V[] vals;
    private int N;

    public BinarySearchST() {
        keys = (K[]) new Comparable[INIT_CAPACITY];
        vals = (V[]) new Object[INIT_CAPACITY];
    }

    public BinarySearchST(int capacity) {
        keys = (K[]) new Comparable[capacity];
        vals = (V[]) new Object[capacity];
    }

    private void resize(int capacity) {
        K[] tempk = (K[]) new Comparable[capacity];
        V[] tempv = (V[]) new Object[capacity];
        for (int i = 0; i < N; i++) {
            tempk[i] = keys[i];
            tempv[i] = vals[i];
        }
        vals = tempv;
        keys = tempk;
    }

    private int search(K key) {
        int lo = 0;
        int hi = N - 1;
        while (lo <= hi) {
            int mid = (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 V get(K key) {
        if (isEmpty()) return null;
        int i = search(key);
        if (i < N && keys[i].compareTo(key) == 0) return vals[i];
        else return null;
    }

    public void put(K key, V value) {
        int i = search(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            vals[i] = value;
            return;
        }
        if (N == keys.length) resize(2 * keys.length);
        for (int j = N; j > i; j--) {
            keys[j] = keys[j - 1];
            vals[j] = vals[j - 1];
        }
        keys[i] = key;
        vals[i] = value;
        N++;
    }

    public void delete(K key) {
        if (isEmpty()) return;
        int i = search(key);
        if (i == N || keys[i].compareTo(key) != 0) return;
        for (int j = i; j < N - 1; j++) {
            keys[j] = keys[j + 1];
            vals[j] = vals[j + 1];
        }
        N--;
        keys[N] = null;
        vals[N] = null;
        if (N > INIT_CAPACITY && N == keys.length / 4) resize(keys.length / 2);
    }

    public Iterable<K> keys() {
        ArrayList<K> keyList = new ArrayList<K>(N);
        for (int i = 0; i < N; i++) keyList.add(keys[i]);
        return keyList;
    }

    public boolean contains(K key) { return get(key) != null; }
    public boolean isEmpty() { return N == 0; }
    public int size() { return N; }
}

 
 
 
 
 
 

Binary Search Tree (BST) (31, 32, 33, 34, 35, 36, 37, 39, 40, 41, 42, 43, 44페이지)

class Node<K,V> {
    K key;
    V value;
    Node<K,V> left, right, parent;
    int N;
    int aux;
    public Node(K key, V val) {
        this.key = key;
        this.value = val;
        this.N = 1;
    }
    public int getAux(){ return aux; }
    public void setAux(int value) { aux = value; }
}

public class BST<K extends Comparable<K>, V> {
    protected Node<K,V> root;

    public int size() { return (root != null) ? root.N : 0; }

    protected Node<K,V> treeSearch(K key) {
        Node<K,V> x = root;
        while (true) {
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x;
            else if (cmp < 0) {
                if (x.left == null) return x;
                else x = x.left;
            } else {
                if (x.right == null) return x;
                else x = x.right;
            }
        }
    }

    public V get(K key) {
        if (root == null) return null;
        Node<K,V> x = treeSearch(key);
        if (key.equals(x.key)) return x.value;
        else return null;
    }

    public void put(K key, V val) {
        if (root == null) { root = new Node<K,V>(key, val); return; }
        Node<K,V> x = treeSearch(key);
        int cmp = key.compareTo(x.key);
        if (cmp == 0) x.value = val;
        else {
            Node<K,V> newNode = new Node<K,V>(key, val);
            if (cmp < 0) x.left = newNode;
            else x.right = newNode;
            newNode.parent = x;
            rebalanceInsert(newNode);
        }
    }

    protected void rebalanceInsert(Node<K,V> x) {
        resetSize(x.parent, 1);
    }

    protected void rebalanceDelete(Node<K,V> p, Node<K,V> deleted) {
        resetSize(p, -1);
    }

    private void resetSize(Node<K,V> x, int value) {
        for (; x != null; x = x.parent)
            x.N += value;
    }

    public Iterable<K> keys() {
        if (root == null) return null;
        ArrayList<K> keyList = new ArrayList<K>(size());
        inorder(root, keyList);
        return keyList;
    }

    private void inorder(Node<K,V> x, ArrayList<K> keyList) {
        if (x != null) {
            inorder(x.left, keyList);
            keyList.add(x.key);
            inorder(x.right, keyList);
        }
    }

    public void delete(K key) {
        if (root == null) return;
        Node<K,V> x, y, p;
        x = treeSearch(key);
        if (!key.equals(x.key)) return;
        if (x == root || isTwoNode(x)) {
            if (isLeaf(x)) { root = null; return; }
            else if (!isTwoNode(x)) {
                root = (x.right == null) ? x.left : x.right;
                root.parent = null;
                return;
            } else {
                y = min(x.right);
                x.key = y.key;
                x.value = y.value;
                p = y.parent;
                relink(p, y.right, y == p.left);
                rebalanceDelete(p, y);
            }
        } else {
            p = x.parent;
            if (x.right == null) relink(p, x.left, x == p.left);
            else if (x.left == null) relink(p, x.right, x == p.left);
            rebalanceDelete(p, x);
        }
    }

    protected boolean isLeaf(Node<K,V> x) { return x.left == null && x.right == null; }
    protected boolean isTwoNode(Node<K,V> x) { return x.left != null && x.right != null; }
    protected void relink(Node<K,V> parent, Node<K,V> child, boolean makeLeft) {
        if (child != null) child.parent = parent;
        if (makeLeft) parent.left = child;
        else parent.right = child;
    }

    public K min() {
        if (root == null) return null;
        Node<K,V> x = root;
        while (x.left != null) x = x.left;
        return x.key;
    }

    protected Node<K,V> min(Node<K,V> x) {
        while (x.left != null) x = x.left;
        return x;
    }

    public K max() {
        if (root == null) return null;
        Node<K,V> x = root;
        while (x.right != null) x = x.right;
        return x.key;
    }

    public K floor(K key) {
        if (root == null || key == null) return null;
        Node<K,V> x = floor(root, key);
        if (x == null) return null;
        else return x.key;
    }

    private Node<K,V> floor(Node<K,V> x, K 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<K,V> t = floor(x.right, key);
        if (t != null) return t;
        else return x;
    }

    public int rank(K key) {
        if (root == null || key == null) return 0;
        Node<K,V> x = root;
        int num = 0;
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0) x = x.left;
            else if (cmp > 0) {
                num += 1 + size(x.left);
                x = x.right;
            } else {
                num += size(x.left);
                break;
            }
        }
        return num;
    }

    private int size(Node<K,V> x) { return (x != null) ? x.N : 0; }

    public K select(int rank) {
        if (root == null || rank < 0 || rank >= size()) return null;
        Node<K,V> x = root;
        while (true) {
            int t = size(x.left);
            if (rank < t) x = x.left;
            else if (rank > t) {
                rank = rank - t - 1;
                x = x.right;
            } else return x.key;
        }
    }

    public boolean contains(K key) { return get(key) != null; }
    public boolean isEmpty() { return root == null; }
}