二叉搜索树

private class BST<Key> {
    private Key key;
    private BST left;
    private BST right;

    public BST(Key key, BST left, BST Right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }

    public BST(Key key) {
        this.key = key;
    }
}

这个 BST 成员变量颇有递归的味道......

抽象数据类型（ADT）是通过操作来定义的，而不是通过实现。（可以用接口来定义 ADT）

一些有用的抽象数据类型：

• 分离集、映射、集合、列表。
• Java 提供了映射、集合、列表接口，以及多个实现。

我们看到了两种实现集合（或映射）的方法：

• ArraySet：在最坏情况下的操作。
• BST：如果树是平衡的，操作为 Θ(logN)Θ(logN) 。

BST 实现：

• 搜索和插入很简单（但插入有点棘手）。
• 删除更具挑战性。典型方法是“希巴德删除法”。