Trie（前缀树、字典树、向量树）

基本概念

一般前缀树的三个基本性质

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

前缀树

1// 简单的前缀树（只能存储字符串）
2class TrieNode {
3  nodes = {};
4  constructor() {
5    this.isEnd = false;
6    this.nodes = {};
7  }
8}
9
10class Trie {
11  nodes = {};
12  constructor() {}
13  insert(str) {
14    let node = this;
15    for (let i = 0; i < str.length; i += 1) {
16      const v = str[i];
17      node.nodes[v] || (node.nodes[v] = new TrieNode());
18      node = node.nodes[v];
19      if (i === str.length - 1) node.isEnd = true;
20    }
21  }
22  search(str) {
23    let node = this;
24    for (let i = 0; i < str.length; i += 1) {
25      const v = str[i];
26      if (!node.nodes[v]) return false;
27      node = node.nodes[v];
28    }
29    return node.isEnd;
30  }
31}

ImmutableJS

持久化数据结构、结构共享

Immutable，顾名思义，即不可变数据结构，所有的数据都是不可变的

Vector Trie

使用Array表示

1var fruits = ['banana', 'grape', 'lemon', 'orange', 'apple'];
2
3var fruits2 = fruits.slice();
4fruits.push('watermelon');

使用向量树：

向量树

插入节点 watermelon ：

向量树

位分区

1const SHIFT = 3;
2const NODE_SIZE = 1 << SHIFT;
3
4class ArrayNode {
5  nodes = [];
6  get(idx) {
7    return this.nodes[idx];
8  }
9}
10
11class List {
12  level = SHIFT;
13  root = new ArrayNode();
14  get(idx) {
15    return find(this.root, this.level, idx);
16  }
17}
18
19/**
20[0, 1, 2, 3, 4, 5, 6, 7]
21root = ArrayNode([0, 1, 2, 3, 4, 5, 6, 7])
22level = 0b1000
23*/
24/**
25[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
26root = ArrayNode([
27  ArrayNode([0, 1, 2, 3, 4, 5, 6, 7]),
28  ArrayNode([8, 9])
29])
30level = 0b1000000
31*/
32// list.get(8) === list.get(0b001001) === 9
33
34function find(root, level, idx) {
35  let node = root;
36  while(level > SHIFT) {
37    level = level >>> SHIFT;
38    node = node.get(idx >>> level);
39    idx = ((1 << level) - 1) & idx;
40  }
41  return node.get(idx);
42}