符号表是一种存储键值对的数据结构, 支持插入和查找操作. 要确定一个给定的键是否存在于符号表中, 首先要建立对象等价性的概念. 为了保证一致性, 最好选择不 可变的数据类型作为键. 成本模型: 统计比较的次数, 在内循环不进行比较的情况下, 转为统计数组的访问次数.
二叉查找树 每个结点的键都大于其左子树的任意结点的键而小于右子树的任一结点的键. 一棵二叉查找树代表了一组键(及其相应的值)的集合, 同一个集合可以用多棵不同的二叉树 表示, 如果将所有键都投影到一条直线上, 则可以保证得到一个有序的键列.
查找的惯用做法是: 如果含有该键的结点存在于表中, 则返回相应的值或者返回null. 我们将采用Java 8的Optional类型使得查找的结果总是返回Optional, 将 显示的调用交给使用者.
使用二叉查找树的算法的运行时间取决于树的形状. 在最好的情况下, 一棵含有N个结点的树是完全平衡的, 每条空链接和根结点的距离都为lgN; 而在最坏的情况下 树的高度为N. 当键的分布是随机的情况下, 二叉查找树一般具有较好的平衡性, 此时查找或者插入操作平均所需的次数为2lnN(1.39lgN). 虽然二叉查找树的查找 成本比二分查找高约39%, 但插入操作是对数级别的.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 public class BST<Key extends Comparable<Key>, Value> { private Node root; private class Node { private Node left, right; private Key key; private Value val; private int N; 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(Node node) { if (node == null) return 0; return node.N; } public Optional<Value> get(Key key) { return Optional.of(get(root, key)); } private Value get(Node node, Key key) { if (node == null) return null; int cmp = key.compareTo(node.key); if (cmp > 0) get(node.right, key); else if (cmp < 0) get(node.left, key); return node.val; } public void put(Key key, Value val) { root = put(root, key, val); } private Node put(Node node, Key key, Value val) { if (node == null) return new Node(key, val, 1); int cmp = key.compareTo(node.key); if (cmp > 0) node.right = put(node.right, key, val); else if (cmp < 0) node.left = put(node.left, key, val); else node.val = val; node.N = size(node.left) + size(node.right) + 1; return node; } } 平衡查找树 2-3查找树 一棵2-3查找树或为一棵空树, 或者由以下结点组成:
...