声明: 文章大部分代码来源自《算法》第四版
源程序链接 https://algs4.cs.princeton.edu/32bst/BST.java.html
二叉查找树的性质
- 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点(no duplicate nodes)。
节点表示
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; } }
- key -- 它是关键字,是用来对二叉查找树的节点进行排序的。
- left -- 它指向当前节点的左孩子。
- right-- 它指向当前节点的右孩子。
- val -- 键对应的值
二叉查找树表示
public class BST, Value> { private Node root; // root of BST .... public Node get(); public void put(); //功能在下边分别给出 }
查找
public Value get(Key key) { return get(root, key); } private Value get(Node x, Key key) { if (key == null) throw new IllegalArgumentException("calls 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; }
插入
public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("calls put() with a null key"); if (val == null) { delete(key);//因为值为NULL,删除这个键 return; } root = put(root, key, val); } 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; }
删除最大值和最小值
//删除最小键 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 = x.right; x.left原本指向的节点被回收。 x.left = deleteMin(x.left); x.size = size(x.left) + size(x.right) + 1; return x; } //删除最大值 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 = x.left; x.right原本指向的节点被回收 x.right = deleteMax(x.right); x.size = size(x.left) + size(x.right) + 1; return x; }
最大值和最小值
//最小值 public Key min() { if (isEmpty()) throw new NoSuchElementException("calls 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); } //最大值 public Key max() { if (isEmpty()) throw new NoSuchElementException("calls 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); }
删除
public void delete(Key key) { if (key == null) throw new IllegalArgumentException("calls 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; }
前驱和后继
//前驱 public Key floor(Key key) { if (key == null) throw new IllegalArgumentException("argument to floor() is null"); if (isEmpty()) throw new NoSuchElementException("calls 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}. public Key ceiling(Key key) { if (key == null) throw new IllegalArgumentException("argument to ceiling() is null"); if (isEmpty()) throw new NoSuchElementException("calls 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); }
排名
1.已知排名求键 Select
public Key select(int k) { if (k < 0 || k >= size()) { throw new IllegalArgumentException("argument to select() is invalid: " + 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); //在右子树,在右子树的排名是 k-t-1 else return x; }
2.已知键求排名 Rank
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); }
遍历
public Iterablekeys() { if (isEmpty()) return new Queue (); 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 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 queue = new Queue (); keys(root, queue, lo, hi); return queue; } private void keys(Node x, Queue 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); }