mahaaoo
0%

Trie树

Posted on Edited on In

Trie树简介

Trie 树，也叫字典树或者叫前缀树。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的树状结构，用来解决在一组字符串集合中快速查找某个字符串的问题。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

下面展示了一个由“hello”、“her”、“hi”、“how”、“see”以及“so”组成的Trie树。

Trie特点

由上图中的Trie中可知

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

实现Trie树

Trie树节点

由于每个节点只存储一个字符，以及指向它的子节点，那么对于每个节点有如下的数据结构

1
2
3
4
function TrieNode(key) {
    this.key = key;
    this.children = [];
}

其中key保存了这个节点的值，children中保存了该节点的所有子节点（对于小写英文字母而言，这个数组的长度为26）

Trie树的插入

构建一棵Trie树就是将字符串逐个插入的过程。由于Trie的特点，插入操作的过程中。要先判断Trie是否已经存在了与待插入字符串相同的前缀，找到所有的公共前缀后，将不同的字符插入Trie中。对于插入的过程，大致的代码如下：

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
// 采用递归插入字符串
function insertData(data, node){
    if (data === '') {
        return;
    }

    let children = node.children;
    let haveData = null;
    
   // 判断存储子节点的数组中，是否有与插入字符串的第一个值匹配的节点
    for (let i in children) {
        if (children[i].key == data[0]) {
            haveData = children[i];
        }
    }
    
    if(haveData) {
        // 待插入的第一个字符已经存在children数组中，则继续判断下一个字符
        this.insertData(data.substring(1), haveData);
    }else{
      // 未找到相应的子节点，分为两种情况
      // 已经是现有Trie的叶子节点
        if(children.length === 0) {
            let insertNode = new TrieNode(data[0]);
            children.push(insertNode);
            this.insertData(data.substring(1), insertNode); 
        }else{
          // 要在当前的children中找到合适的位置，插入字符
            let validPosition = 0;
            for (let j in children) {
                if (children[j].key < data[0]) {
                    validPosition++;
                }
            }
            let insertNode = new TrieNode(data[0]);
            children.splice(validPosition, 0, insertNode);
            this.insertData(data.substring(1), insertNode); 
        }
    }
}

在插入Trie树的过程中，需要遍历所有的字符串，时间复杂度是O(n)，n表示所有字符串的长度和。

Trie树的查找

查找的过程与插入的过程类似，需要逐层遍历，寻找与待匹配字符串相同的字符。其大概代码如下：

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
function search (data) {
    if (data === '' || this.root.children.length === 0) {
        return false;
    }
  // 遍历children
    for (let i in this.root.children) {
        if (this.searchNext(this.root.children[i], data)) {
            return true;
        }
    }
    return false;
}
// 递归查找
function searchNext(node, data) {
    if(data[0] !== node.key) return false;
    let children = node.children;
  // 该节点已经是叶子节点，并且待查找字符串已查找完毕
    if(children.length === 0 && data.length === 1) {
        return true;
    } else if(children.length > 0 && data.length > 1) {
        for(let i in children) {
            // 继续判断下一个字符
            if(children[i].key === data[1]) {
                return searchNext(children[i], data.substring(1));
            }
        }
    } else {
        return false;
    }
}

在Trie树已经构建完成的情况下，查找一个字符串是否在Trie中效率是非常高的，其事件复杂度为O(K)，k表示待查找字符串的长度。

Trie树的删除

先递归查找到字符串的叶子节点，然后从字符串的叶子节点逐级向根节点递归删除叶子节点，直到删除字符串。其大概的代码如下：

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
function deleteNode(data) {
    if (this.search(data)) { // 判断是否存在该单词（字符串）
        for (let i in this.root.children) {
            if (this.deleteNext(this.root, i, data, data)) {
                return;
            }
        }
    }
    return this;
}

/**
* @param parent 父节点
* @param index 子节点在父节点children数组中的索引位置
* @param stringData 递归遍历中的字符串
* @param delStr 调用delete方法时的原始字符串
*/
function deleteNext(parent, index, stringData, delStr) {
    let node = parent.children[index];
    // 若字符与节点key不相等，则不匹配
    if (stringData[0] != node.key) {
        return false;
    } else { // 若与key相等，继续判断
        let children = node.children;
        if (children.length == 0 && stringData.length == 1) { // 叶子节点，最后一个字符，则完全匹配
            // 删除叶子节点，利用父节点删除子节点原理
            parent.children.splice(index, 1);
            // 字符串从尾部移除一个字符后，继续遍历删除方法
            this.deleteNode(delStr.substring(0, delStr.length - 1));
        } else if (children.length > 0 && stringData.length > 1) { // 既不是叶子节点，也不是最后一个字符，则继续递归查找
            for (let i in children) {
                if (children[i].key == stringData[1]) {
                    return this.deleteNext(node, i, stringData.substring(1), delStr); // 记得return 递归函数，否则获取的返回值为undefined
                }
            }
        }
    }
}

Trie改进

Trie树是非常消耗内存的数据结构，用的是一种空间换时间的思路。Trie树的问题就在于存储子节点的children数组中。如果字符串中只包含从a到z的26个字符，那么children的长度就为26。注意，这里说的是每一个Trie树的节点，都需要申请一个长度为26的数组，即使这个节点只有一个子节点！

那么如果字符串包含了大小写，或者是数字特殊字符。Trie所需的空间就更大了。尤其是在重复的前缀不多的情况下，Trie树不但不能节省内存，而且还有可能浪费更多的内存空间。可以想到的方法就是，将children修改为其他的数据结构，比如有序数组、跳表等。

对只有一个子节点的节点，而且此节点不是一个串的结束节点可以将此节点与子节点合并，这就是缩点优化。

Trie树完整代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
function TrieNode(key) {
    this.key = key;
    this.children = [];
}

function Trie() {
    this.root = new TrieNode('/'); // 添加根节点
    this.insert = insert; // 插入
    this.insertData = insertData;
    this.search = search; // 查找
    this.searchNext = searchNext;
    this.deleteNode = deleteNode; // 删除
    this.deleteNext = deleteNext;

    this.nodeNumber = 0; // trie所有节点个数
    this.print = print; // 打印Trie树
    this.printHelper = printHelper;
}

function insert(data) {
    this.insertData(data, this.root);
}

function insertData(data, node){
    if (data === '') {
        return;
    }

    let children = node.children;
    let haveData = null;
    
    for (let i in children) {
        if (children[i].key == data[0]) {
            haveData = children[i];
        }
    }
    
    if(haveData) {
        this.insertData(data.substring(1), haveData);
    }else{
        if(children.length === 0) {
            let insertNode = new TrieNode(data[0]);
            children.push(insertNode);
            this.insertData(data.substring(1), insertNode); 
        }else{
            let validPosition = 0;
            for (let j in children) {
                if (children[j].key < data[0]) {
                    validPosition++;
                }
            }
            let insertNode = new TrieNode(data[0]);
            children.splice(validPosition, 0, insertNode);
            this.insertData(data.substring(1), insertNode); 
        }
    }
}

function search (data) {
    if (data === '' || this.root.children.length === 0) {
        return false;
    }
    for (let i in this.root.children) {
        if (this.searchNext(this.root.children[i], data)) {
            return true;
        }
    }
    return false;
}

function searchNext(node, data) {
    if(data[0] !== node.key) return false;
    let children = node.children;
    if(children.length === 0 && data.length === 1) {
        return true;
    } else if(children.length > 0 && data.length > 1) {
        for(let i in children) {
            if(children[i].key === data[1]) {
                return searchNext(children[i], data.substring(1));
            }
        }
    } else {
        return false;
    }
}

function deleteNode(data) {
    if (this.search(data)) { 
        for (let i in this.root.children) {
            if (this.deleteNext(this.root, i, data, data)) {
                return;
            }
        }
    }
    return this;
}

function deleteNext(parent, index, stringData, delStr) {
    let node = parent.children[index];
    if (stringData[0] != node.key) {
        return false;
    } else {
        let children = node.children;
        if (children.length == 0 && stringData.length == 1) { 
            parent.children.splice(index, 1);
            this.deleteNode(delStr.substring(0, delStr.length - 1));
        } else if (children.length > 0 && stringData.length > 1) {
            for (let i in children) {
                if (children[i].key == stringData[1]) {
                    return this.deleteNext(node, i, stringData.substring(1), delStr);
                }
            }
        }
    }
}

function print () {
    for (let i in this.root.children) {
        this.nodeNumber++;
        this.printHelper(this.root.children[i], [this.root.children[i].key]);
    }
}

function printHelper (node, data) {
    if (node.children.length === 0) {
        console.log('>', data.join(''));
        return;
    }
    for (let i in node.children) {
        this.nodeNumber++;
        data.push(node.children[i].key);
        this.printHelper(node.children[i], data);
        data.pop();
    }
}

let trie = new Trie();

trie.insert('apple');
trie.insert('appcd');
trie.insert('banana');

trie.print();
console.log(trie.search("app"));
trie.deleteNode('appcd')
trie.print();

console.log(trie.nodeNumber);

// 输出结果
> appcd
> apple
> banana
false
> apple
> banana
11

学习心得

第一次看Trie树的概念，完全没明白到底是什么样的数据结构。直到看了Trie树的图示例，一下就明白了，Trie树的概念非常好理解，就是把相同的前缀放到一起构成了一个数据结构。在对比字符串的时候，就像查字典一层层的比较。

对于每个节点的存储结构确实比较绕，每次遍历children数组就相当于去往下一层比较了，反正每次涉及到递归函数总是不好理解。

参考资料