二叉搜索树与堆：高效数据结构解析

### 二叉搜索树与堆：高效数据结构解析 #### 1. 二叉搜索树（BST）概述 在处理数据存储和查询时，传统的未排序列表和排序列表各有优劣。未排序列表插入快，但搜索慢，平均时间复杂度为 Θ(n)；排序的链表对搜索速度提升不大；而排序的数组虽可使用二分查找将搜索时间降至 Θ(log n)，但插入时平均需 Θ(n) 时间，因为要移动大量元素。 二叉搜索树（BST）为解决这一问题提供了更好的方案。BST 是一种二叉树，遵循二叉搜索树属性：对于键值为 K 的节点，其左子树中的所有节点键值小于 K，右子树中的所有节点键值大于或等于 K。这一属性使得按中序遍历 BST 节点时，结果是从小到大排序的。 以下是 BST 的类声明代码： ```java /** Binary Search Tree implementation for Dictionary ADT */ class BST<Key extends Comparable<? super Key>, E> implements Dictionary<Key, E> { private BSTNode<Key,E> root; // Root of the BST private int nodecount; // Number of nodes in the BST /** Constructor */ BST() { root = null; nodecount = 0; } /** Reinitialize tree */ public void clear() { root = null; nodecount = 0; } /** Insert a record into the tree. @param k Key value of the record. @param e The record to insert. */ public void insert(Key k, E e) { root = inserthelp(root, k, e); nodecount++; } /** Remove a record from the tree. @param k Key value of record to remove. @return The record removed, null if there is none. */ public E remove(Key k) { E temp = findhelp(root, k); // First find it if (temp != null) { root = removehelp(root, k); // Now remove it nodecount--; } return temp; } /** Remove and return the root node from the dictionary. @return The record removed, null if tree is empty. */ public E removeAny() { if (root == null) return null; E temp = root.element(); root = removehelp(root, root.key()); nodecount--; return temp; } /** @return Record with key value k, null if none exist. @param k The key value to find. */ public E find(Key k) { return findhelp(root, k); } /** @return The number of records in the dictionary. */ public int size() { return nodecount; } } ``` #### 2. BST 的操作 - **搜索操作**：在 BST 中查找键值为 K 的记录，从根节点开始。若根节点键值为 K，则搜索结束；否则，根据 K 与根节点键值的大小关系，只搜索左子树或右子树，直到找到目标记录或到达叶子节点。以下是 `findhelp` 方法的实现： ```java private E findhelp(BSTNode<Key,E> rt, Key k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) return findhelp(rt.left(), k); else if (rt.key().compareTo(k) == 0) return rt.element(); else return findhelp(rt.right(), k); } ``` - **插入操作**：插入键值为 k 的记录时，先找到该记录若存在于树中应处的位置，即叶子节点或合适方向无孩子的内部节点 R'，然后将包含新记录的节点作为 R' 的孩子添加。以下是 `inserthelp` 方法的实现： ```java private BSTNode<Key,E> inserthelp(BSTNode<Key,E> rt, Key k, E e) { if (rt == null) return new BSTNode<Key,E>(k, e); if (rt.key().compareTo(k) > 0) rt.setLeft(inserthelp(rt.left(), k, e)); else rt.setRight(inserthelp(rt.right(), k, e)); return rt; } ``` - **删除操作**：删除节点相对复杂。先找到要删除的节点 R，若 R 无孩子，将其父节点指针置为 null；若 R 有一个孩子，将其父节点指针指向 R 的孩子；若 R 有两个孩子，可选择用右子树中最小键值的节点替换 R 的值，然后删除右子树中最小键值的节点。以下是 `deletemin` 和 `removehelp` 方法的实现： ```java private BSTNode<Key,E> deletemin(BSTNode<Key,E> rt) { if (rt.left() == null) return rt.right(); rt.setLeft(deletemin(rt.left())); return rt; } private ```