算法练习_有序符号表

概念

符号表中，经常会使用查询操作，对于无序的符号表，每次遍历数组会降低性能。因此，如果在插入操作时，保证键的有序性，那么后续的查询操作将会变得简单，并且能大大扩展符号表的 API。

有序符号表的键，均是 Comparble对象，因此可以使用 a.comparableTo(b) 来比较两个对象。

API

代码实现

基于链表

public class OrderdST<K extends Comparable<K>, V> {

    Node root;
    int size;

    public void put(K key, V val) {
        if (key == null || val == null) {
            return;
        }
        if (root == null) {
            root = new Node(key, val);
            return;
        }

        Node temp = root;
        Node pre = null;
        while (temp.next != null) {
            if (key.compareTo(temp.key) <= 0) {
                if (key.equals(temp.key)) {
                    temp.val = val;
                } else {
                    size++;
                    Node newNode = new Node(key, val);

                    if (pre == null) {
                        root = newNode;
                        root.next = temp;
                    } else {
                        pre.next = newNode;
                        newNode.next = temp;
                    }
                }
                return;
            }
            pre = temp;
            temp = temp.next;
        }
        temp.next = new Node(key, val);
        size++;
    }

    public V get(K key) {
        if (key == null) {
            return null;
        }
        Node temp = root;
        while (temp.next != null) {
            if (key.equals(temp.key)) {
                return temp.val;
            }
            temp = temp.next;
        }
        return null;
    }

    public void delete(K key) {
        if (key == null) {
            return;
        }
        Node temp = root;
        Node pre = null;
        while (temp.next != null) {
            if (key.compareTo(temp.key) == 0) {
                if (pre == null) {
                    root = temp.next;
                } else {
                    pre.next = temp.next;
                }
                size--;
            }
            pre = temp;
            temp = temp.next;
        }
    }

    private boolean contains(K key) {
        if (key == null) {
            return false;
        }
        Node temp = root;
        while (temp.next != null) {
            if (key.compareTo(temp.key) == 0) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

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

    private int size() {
        return size;
    }

    private K min() {
        return root.key;
    }

    public K max() {
        Node temp = root;
        while (temp.next != null) {
            temp = temp.next;
        }
        return temp.key;
    }

    public K floor(K key) {
        if (key == null) {
            return null;
        }
        Node temp = root;
        while (temp.next != null) {
            if (temp.key.compareTo(key) <= 0 && temp.next.key.compareTo(key) > 0) {
                return temp.key;
            }
        }
        return temp.key;
    }

    public K ceiling(K key) {
        if (key == null) {
            return null;
        }
        Node temp = root;
        while (temp.next != null) {
            if (temp.key.compareTo(key) <= 0 && temp.next.key.compareTo(key) > 0) {
                return temp.next.key;
            }
        }
        return null;
    }

    public int rank(K key) {
        if (key == null) {
            return 0;
        }
        int count = 0;
        Node temp = root;
        while (temp.next != null && temp.key.compareTo(key) < 0) {
            count++;
            temp = temp.next;
        }
        if (temp.key.compareTo(key) < 0) {
            count++;
        }
        return count;
    }

    public K select(int index) {
        if (index < 0) {
            return null;
        }
        if (index > size - 1) {
            return null;
        }
        Node temp = root;
        while (temp.next != null && index != 0) {
            temp = temp.next;
            index--;
        }
        return temp.key;
    }

    class Node {
        K key;
        V val;
        Node next;

        Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }
}