3.2 二叉查找树

小灰灰 2022-06-09 10:29 143阅读 0赞

> 3.2 Binary Search Trees  
> [http://algs4.cs.princeton.edu/32bst/][http_algs4.cs.princeton.edu_32bst]

### 基本实现 ###

*  数据表示
 *  查找  
    ![这里写图片描述][SouthEast]
 *  插入  
    ![这里写图片描述][SouthEast 1]
 *  递归
 *  最大键最小键
 *  向上取整向下取整  
    ![这里写图片描述][SouthEast 2]
 *  选择操作  
    ![这里写图片描述][SouthEast 3]
 *  删除最大值和最小值  
    ![这里写图片描述][SouthEast 4]
 *  删除操作  
    ![这里写图片描述][SouthEast 5]
 *  范围查找

/****************************************************************************** * Compilation: javac BST.java * Execution: java BST * Dependencies: StdIn.java StdOut.java Queue.java * Data files: http://algs4.cs.princeton.edu/32bst/tinyST.txt * * A symbol table implemented with a binary search tree. * * % more tinyST.txt * S E A R C H E X A M P L E * * % java BST < tinyST.txt * A 8 * C 4 * E 12 * H 5 * L 11 * M 9 * P 10 * R 3 * S 0 * X 7 * ******************************************************************************/
    
    import java.util.NoSuchElementException;
    
    public class BST<Key extends Comparable<Key>, Value> { 
        private Node root;             // root of BST
    
        private class Node { 
            private Key key;           // sorted by key
            private Value val;         // associated data
            private Node left, right;  // left and right subtrees
            private int size;          // number of nodes in subtree
    
            public Node(Key key, Value val, int size) {
                this.key = key;
                this.val = val;
                this.size = size;
            }
        }
    
        /** * Initializes an empty symbol table. */
        public BST() {
        }
    
        /** * Returns true if this symbol table is empty. * @return {@code true} if this symbol table is empty; {@code false} otherwise */
        public boolean isEmpty() {
            return size() == 0;
        }
    
        /** * Returns the number of key-value pairs in this symbol table. * @return the number of key-value pairs in this symbol table */
        public int size() {
            return size(root);
        }
    
        // return number of key-value pairs in BST rooted at x
        private int size(Node x) {
            if (x == null) return 0;
            else return x.size;
        }
    
        /** * Does this symbol table contain the given key? * * @param key the key * @return {@code true} if this symbol table contains {@code key} and * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */
        public boolean contains(Key key) {
            if (key == null) throw new IllegalArgumentException("argument to contains() is null");
            return get(key) != null;
        }
    
        /** * Returns the value associated with the given key. * * @param key the key * @return the value associated with the given key if the key is in the symbol table * and {@code null} if the key is not in the symbol table * @throws IllegalArgumentException if {@code key} is {@code null} */
        public Value get(Key key) {
            return get(root, key);
        }
    
        private Value get(Node x, Key key) {
            if (key == null) throw new IllegalArgumentException("called get() with a null 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.val;
        }
    
        /** * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is {@code null}. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */
        public void put(Key key, Value val) {
            if (key == null) throw new IllegalArgumentException("calledput() with a null key");
            if (val == null) {
                delete(key);
                return;
            }
            root = put(root, key, val);
            assert check();
        }
    
        private Node put(Node x, Key key, Value val) {
            if (x == null) return new Node(key, val, 1);
            int cmp = key.compareTo(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;
            x.size = 1 + size(x.left) + size(x.right);
            return x;
        }
    
    
        /** * Removes the smallest key and associated value from the symbol table. * * @throws NoSuchElementException if the symbol table is empty */
        public void deleteMin() {
            if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
            root = deleteMin(root);
            assert check();
        }
    
        private Node deleteMin(Node x) {
            if (x.left == null) return x.right;
            x.left = deleteMin(x.left);
            x.size = size(x.left) + size(x.right) + 1;
            return x;
        }
    
        /** * Removes the largest key and associated value from the symbol table. * * @throws NoSuchElementException if the symbol table is empty */
        public void deleteMax() {
            if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
            root = deleteMax(root);
            assert check();
        }
    
        private Node deleteMax(Node x) {
            if (x.right == null) return x.left;
            x.right = deleteMax(x.right);
            x.size = size(x.left) + size(x.right) + 1;
            return x;
        }
    
        /** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */
        public void delete(Key key) {
            if (key == null) throw new IllegalArgumentException("called delete() with a null key");
            root = delete(root, key);
            assert check();
        }
    
        private Node delete(Node x, Key key) {
            if (x == null) return null;
    
            int cmp = key.compareTo(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.size = size(x.left) + size(x.right) + 1;
            return x;
        } 
    
    
        /** * Returns the smallest key in the symbol table. * * @return the smallest key in the symbol table * @throws NoSuchElementException if the symbol table is empty */
        public Key min() {
            if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
            return min(root).key;
        } 
    
        private Node min(Node x) { 
            if (x.left == null) return x; 
            else                return min(x.left); 
        } 
    
        /** * Returns the largest key in the symbol table. * * @return the largest key in the symbol table * @throws NoSuchElementException if the symbol table is empty */
        public Key max() {
            if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
            return max(root).key;
        } 
    
        private Node max(Node x) {
            if (x.right == null) return x; 
            else                 return max(x.right); 
        } 
    
        /** * Returns the largest key in the symbol table less than or equal to {@code key}. * * @param key the key * @return the largest key in the symbol table less than or equal to {@code key} * @throws NoSuchElementException if there is no such key * @throws IllegalArgumentException if {@code key} is {@code null} */
        public Key floor(Key key) {
            if (key == null) throw new IllegalArgumentException("argument to floor() is null");
            if (isEmpty()) throw new NoSuchElementException("called floor() with empty symbol table");
            Node x = floor(root, key);
            if (x == null) return null;
            else 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; 
        } 
    
        /** * Returns the smallest key in the symbol table greater than or equal to {@code key}. * * @param key the key * @return the smallest key in the symbol table greater than or equal to {@code key} * @throws NoSuchElementException if there is no such key * @throws IllegalArgumentException if {@code key} is {@code null} */
        public Key ceiling(Key key) {
            if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
            if (isEmpty()) throw new NoSuchElementException("called ceiling() with empty symbol table");
            Node x = ceiling(root, key);
            if (x == null) return null;
            else return x.key;
        }
    
        private Node ceiling(Node x, Key key) {
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x;
            if (cmp < 0) { 
                Node t = ceiling(x.left, key); 
                if (t != null) return t;
                else return x; 
            } 
            return ceiling(x.right, key); 
        } 
    
        /** * Return the kth smallest key in the symbol table. * * @param k the order statistic * @return the {@code k}th smallest key in the symbol table * @throws IllegalArgumentException unless {@code k} is between 0 and * <em>n</em>–1 */
        public Key select(int k) {
            if (k < 0 || k >= size()) {
                throw new IllegalArgumentException("called select() with invalid argument: " + k);
            }
            Node x = select(root, k);
            return x.key;
        }
    
        // Return key of rank k. 
        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-t-1); 
            else            return x; 
        } 
    
        /** * Return the number of keys in the symbol table strictly less than {@code key}. * * @param key the key * @return the number of keys in the symbol table strictly less than {@code key} * @throws IllegalArgumentException if {@code key} is {@code null} */
        public int rank(Key key) {
            if (key == null) throw new IllegalArgumentException("argument to rank() is null");
            return rank(key, root);
        } 
    
        // Number of keys in the subtree less than key.
        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 1 + size(x.left) + rank(key, x.right); 
            else              return size(x.left); 
        } 
    
        /** * Returns all keys in the symbol table as an {@code Iterable}. * To iterate over all of the keys in the symbol table named {@code st}, * use the foreach notation: {@code for (Key key : st.keys())}. * * @return all keys in the symbol table */
        public Iterable<Key> keys() {
            return keys(min(), max());
        }
    
        /** * Returns all keys in the symbol table in the given range, * as an {@code Iterable}. * * @param lo minimum endpoint * @param hi maximum endpoint * @return all keys in the symbol table between {@code lo} * (inclusive) and {@code hi} (inclusive) * @throws IllegalArgumentException if either {@code lo} or {@code hi} * is {@code null} */
        public Iterable<Key> keys(Key lo, Key hi) {
            if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
            if (hi == null) throw new IllegalArgumentException("second argument to keys() is null");
    
            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); 
        } 
    
        /** * Returns the number of keys in the symbol table in the given range. * * @param lo minimum endpoint * @param hi maximum endpoint * @return the number of keys in the symbol table between {@code lo} * (inclusive) and {@code hi} (inclusive) * @throws IllegalArgumentException if either {@code lo} or {@code hi} * is {@code null} */
        public int size(Key lo, Key hi) {
            if (lo == null) throw new IllegalArgumentException("first argument to size() is null");
            if (hi == null) throw new IllegalArgumentException("second argument to size() is null");
    
            if (lo.compareTo(hi) > 0) return 0;
            if (contains(hi)) return rank(hi) - rank(lo) + 1;
            else              return rank(hi) - rank(lo);
        }
    
        /** * Returns the height of the BST (for debugging). * * @return the height of the BST (a 1-node tree has height 0) */
        public int height() {
            return height(root);
        }
        private int height(Node x) {
            if (x == null) return -1;
            return 1 + Math.max(height(x.left), height(x.right));
        }
    
        /** * Returns the keys in the BST in level order (for debugging). * * @return the keys in the BST in level order traversal */
        public Iterable<Key> levelOrder() {
            Queue<Key> keys = new Queue<Key>();
            Queue<Node> queue = new Queue<Node>();
            queue.enqueue(root);
            while (!queue.isEmpty()) {
                Node x = queue.dequeue();
                if (x == null) continue;
                keys.enqueue(x.key);
                queue.enqueue(x.left);
                queue.enqueue(x.right);
            }
            return keys;
        }
    
      /************************************************************************* * Check integrity of BST data structure. ***************************************************************************/
        private boolean check() {
            if (!isBST())            StdOut.println("Not in symmetric order");
            if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent");
            if (!isRankConsistent()) StdOut.println("Ranks not consistent");
            return isBST() && isSizeConsistent() && isRankConsistent();
        }
    
        // does this binary tree satisfy symmetric order?
        // Note: this test also ensures that data structure is a binary tree since order is strict
        private boolean isBST() {
            return isBST(root, null, null);
        }
    
        // is the tree rooted at x a BST with all keys strictly between min and max
        // (if min or max is null, treat as empty constraint)
        // Credit: Bob Dondero's elegant solution
        private boolean isBST(Node x, Key min, Key max) {
            if (x == null) return true;
            if (min != null && x.key.compareTo(min) <= 0) return false;
            if (max != null && x.key.compareTo(max) >= 0) return false;
            return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
        } 
    
        // are the size fields correct?
        private boolean isSizeConsistent() { return isSizeConsistent(root); }
        private boolean isSizeConsistent(Node x) {
            if (x == null) return true;
            if (x.size != size(x.left) + size(x.right) + 1) return false;
            return isSizeConsistent(x.left) && isSizeConsistent(x.right);
        } 
    
        // check that ranks are consistent
        private boolean isRankConsistent() {
            for (int i = 0; i < size(); i++)
                if (i != rank(select(i))) return false;
            for (Key key : keys())
                if (key.compareTo(select(rank(key))) != 0) return false;
            return true;
        }
    
    
        /** * Unit tests the {@code BST} data type. * * @param args the command-line arguments */
        public static void main(String[] args) { 
            BST<String, Integer> st = new BST<String, Integer>();
            for (int i = 0; !StdIn.isEmpty(); i++) {
                String key = StdIn.readString();
                st.put(key, i);
            }
    
            for (String s : st.levelOrder())
                StdOut.println(s + " " + st.get(s));
    
            StdOut.println();
    
            for (String s : st.keys())
                StdOut.println(s + " " + st.get(s));
        }
    }

[http_algs4.cs.princeton.edu_32bst]: http://algs4.cs.princeton.edu/32bst/
[SouthEast]: /images/20220609/6b78e2ea314f40a6ad9b737b0e9e8411.png
[SouthEast 1]: /images/20220609/93bf37f27d77439ba2083158d7311b84.png
[SouthEast 2]: /images/20220609/d7cd4fdf7888469cb9e80512f33bca8e.png
[SouthEast 3]: /images/20220609/d3afc25f57ea469a8379d6fded6f02f5.png
[SouthEast 4]: /images/20220609/a143aed7d39843118d202bc2f37552d6.png
[SouthEast 5]: /images/20220609/a7a3737b455147cfb281a4a0707d904c.png