12. 使用 BST 实现词典¶

词典 ADT 的一种简单实现可以基于词典或有序列表、无序列表。用无序列表实现词典时，把新记录放到列表末尾就可以快速完成插入。然而，在无序列表中查找某条特定记录，平均情况下需要 \(\Theta(n)\) 时间。对于大型数据库而言，这很可能太慢了。另一种做法是把记录存储在有序列表中。如果列表用链表实现，那么把记录按有序次序存储并不会给查找操作带来任何加速。另一方面，如果我们用有序的基于数组的列表来实现词典，那么就可以用二分查找在 \(\Theta(\log n)\) 时间内找到记录。然而，此时插入平均需要 \(\Theta(n)\) 时间，因为一旦找到新记录在有序列表中的正确位置，就可能需要移动许多记录来为新记录腾出空间。

有没有什么办法来组织一个记录集合，使得插入记录和查找记录都能快速完成？我们可以用二叉搜索树（ BST ）做到这一点。使用 BST 的优点是，所有主要操作（插入、查找和删除）在平均情况下都是 \(\Theta(\log n)\) 。当然，如果树严重失衡，代价可能坏到 \(\Theta(n)\) 。

下面是用 BST 存储记录的词典接口实现。

// Dictionary implementation using BST
// This uses KVPair to manage the key/value pairs
public class BSTDict<K extends Comparable<K>, E> implements Dictionary<K, E> {
  private BST<KVPair<K, E>> theBST; // The BST that stores the records

  // constructor
  BSTDict() { theBST = new BST<KVPair<K, E>>(); }

  // Reinitialize dictionary
  public void clear() { theBST = new BST<KVPair<K, E>>(); }

  // Insert a record
  // k: the key for the record being inserted.
  // e: the record being inserted.
  public void insert(K k, E e) {
      theBST.insert(new KVPair<K, E>(k, e));
  }

  // Remove and return a record.
  // k: the key of the record to be removed.
  // Return a maching record. If multiple records match "k", remove
  // an arbitrary one. Return null if no record with key "k" exists.
  public E remove(K k) {
    KVPair<K, E> temp = theBST.remove(new KVPair<K, E>(k, null));
    if (temp == null) { return null; }
    else { return temp.value(); }
  }

  // Remove and return an arbitrary record from dictionary.
  // Return the record removed, or null if none exists.
  public E removeAny() {
    if (theBST.size() == 0) { return null; }
    KVPair<K, E> temp = theBST.remove(theBST.root().value());
    return temp.value();
  }

  // Return a record matching "k" (null if none exists).
  // If multiple records match, return an arbitrary one.
  // k: the key of the record to find
  public E find(K k) {
    KVPair<K, E> temp = theBST.find(new KVPair<K, E>(k, null));
    if (temp == null) { return null; }
    else { return temp.value(); }
  }

  // Return the number of records in the dictionary.
  public int size() {
    return theBST.size();
  }
}

OpenDSA 完整目录

Chapter 11 Binary Trees

12. 使用 BST 实现词典¶