前言

是的，最近我又换工作了，在看新团队的代码的时候发现，同事们为了追求服务的响应时间，在项目中大量的使用了很多高级的数据结构。

作为传统 Curd 程序员，对算法和数据结构已经比较生疏了。如今看到这些”高级的代码“有点汗颜。所以趁周末好好的在家补课，重新复习一下。

文章将会是一个系列，慢慢的查缺补漏。

简介

Trie 树又叫字典查找树。顾名思义，字典查找树，主要解决的就是字符串的查找。有以下两个优势。

• 查找命中的时间复杂度是 O(k)，k指的是需要查询的 key 的长度。这里注意和字库的大小无关。
• 对于未命中的字符，只需要查询若干字符就可。

基本数据结构

首先 Trie 树，是一棵树。树是由需要建立的所有词构成。

假设我们有，bee 、sea、 shells，she，sells，几个单词。我们可以使用这几个单词构建一棵树。

通过图片我们就可以直观的看出 Trie 的数据结构。这个棵树是由若干节点，链接而成，节点可以指向下一个节点，也可以指向空。从 root 节点开始，顺着链接随便找某个链接往下，直到最低端，经过的路径正好是上文的单词。

数据的代码表示

为了方便使用代码表示。可以考虑每个节点使用数组表示。每个节点都含有一个数组，数组的大小为R，R 是数组的基数，对应每个可能出现的字符。R 的选取取决于报错的字符的类型，如果只包含英文则256 就可以了。如果是中文就需要 65536。

字符和键值都保存在数据结构中。

所以实现代码如下：

1
2
3
4
5
6
7
8
9
10
11

public class TrieST<Value> {

 public static final int R = 256;
 private Node root;

 private static class Node {
  public Object val; // 键值
  public Node[] next = new Node[R];
 }
}

Get 和 Put 方法

对于数据结构的键值的读写方法，我可以使用递归的方式进行查询

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

private Node get(Node x, String key, int d) {

  // 1
  if (x == null) {
   return null;
  }

  //2
  if (d == key.length()) {
   return x;
  }

  //3
  char c = key.charAt(d);

  //4
  return get(x.next[c], key, d + 1);
 }

 public Value get(String key) {
  Node x = get(root, key, 0);
  if (x == null) {
   return null;
  }
  return (Value) x.val;
 }

对于递归的我们需要考虑两个问题。递归的退出的条件是什么，如何进入下一层递归。

对于 Node get(Node x, String key, int d)，入参 x 是当前的节点，key 是需要查找的字字符串，d 是目前递归到的层数，也可以理解为，我们逐个遍历 key 的时候的下标。...