背景
二叉查找树是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。
Java实现
基本数据表示
首先定义好API，以及二叉查找树的数据结构。主要是嵌套定义一个私有类来表示二叉查找树上的一个结点。每个结点都含有一个键、一个值、一条左链接、一条右链接和一个结点计数器。
public class BST<Key extends Comparable<Key>, Value> {
private Node root; // 二叉查找树的根节点
private class Node {
private Key key; // 键
private Value val; // 值
private Node left, right; // 指向子树的链接
private int N; // 以该结点为根的子树中的结点总数
public Node(Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size() {
if(x == null) {
return 0;
} else {
return x.N;
}
}
// 查找等在下文实现
}
查找
在二叉查找树中查找一个键的递归算法：如果树是空的，则查找未命中；如果被查找的键和根结点的键相等，查找命中，否则我们就（递归地）在适当的子树中继续查找。如果被查找的键较小就选择左子树，较大就选择右子树。
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {
// 在以x为根节点的子树中查找并返回key所对应的值
// 如果找不到则返回null
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) {
// 查找key，找到则更新值，否则就创建一个新结点
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
// 如果key存在于以x为根结点的子树中则更新它的值；
// 否则将以key和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.N = size(x.left) + size(x.right) + 1;
return x;
}
有序性的相关方法
主要是四点，最大键、最小键、向上取整和向下取整。
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left)
}
public Key floor(Key key) {
Node x = floor(root, key);
if (x == null) {
return null;
}
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;
}
}
排名
主要是实现能返回给定键的排名。
public Key select(int k) {
return select(root, k).key;
}
private Node select(Node x, int k) {
// 返回排名为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;
}
}
public int rank(Key key) {
return rank(key, root);
}
private int rank(Key key, Node x) {
// 返回以x为根结点的子树中小于x.key的键的数量
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);
}
}
删除
删除最大最小键值对非常简单，只要不断深入结点就可以了。而对于拥有两个子结点的结点有一点麻烦，有一种方法就是删除结点x后用它的后继结点填补它的位置。因为x有一个右子结点，因此它的后继结点就是其右子树中的最小结点。这样的替换仍然能够保证树的有序性。
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node x) {
if (x.left == null) {
return x.right;
}
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
public void delete(Key key) {
root = delete(root, key);
}
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.N = size(x.left) + size(x.right) + 1;
return x;
}
范围查找
要实现能够返回给定范围内键的keys()方法，我们首先需要一个遍历二叉树的基本方法，叫做中序遍历。下面是实现：
public Iterable<Key> keys() {
return keys(min(), max());
}
public Iterable<Key> keys(Key lo, Key hi) {
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);
}
}