字典树运用

字典树

字典树又叫 前缀树， 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

LC208 创建字典树

这是一个字符串字典树的典型例子，字符串中只包含26个小写字母。

代码为：

class Trie {class Node{boolean end;Node[] son = new Node[26];}private Node root;public Trie() {root = new Node(); //伪根}public void insert(String word) {Node cur = root;for(int i = 0; i < word.length(); i++){char c = word.charAt(i);if(cur.son[c - 'a'] == null){cur.son[c - 'a'] = new Node();}cur = cur.son[c - 'a'];}cur.end = true;}public boolean search(String word) {Node cur = root;for(char ch : word.toCharArray()){ch -= 'a';if(cur.son[ch] == null){return false;}cur = cur.son[ch];}if(cur.end != true){return false;}return true;}public boolean startsWith(String prefix) {Node cur = root;for(char ch : prefix.toCharArray()){ch -= 'a';if(cur.son[ch] == null){return false;}cur = cur.son[ch];}return true;}
}

0-1字典树

应用：求最大异或和

代码如下：

import java.io.*;
import java.util.List;
import java.util.ArrayList;class Main{static class Node{Node[] son = new Node[2];int count = 0;}static void insert(Node root, int num){Node cur = root;cur.count++;for(int i = 31; i >= 0; i--){int bit = (num >> i) & 1;if(cur.son[bit] == null){cur.son[bit] = new Node();}cur = cur.son[bit];cur.count++;}}static void remove(Node root, int num){Node cur = root;cur.count--;for(int i = 31; i >= 0; i--){int bit = (num >> i) & 1;cur = cur.son[bit];cur.count--;  //不物理上删除任何节点，采用count来表示节点删除}}static int query(Node root, int num){Node cur = root;if(root.count == 0){return -1;}int res = 0;for(int i = 31; i >= 0; i--){int bit = (num >> i) & 1;int orBit = 1 - bit;if(cur.son[orBit] != null && cur.son[orBit].count > 0){res += (1 << i);cur = cur.son[orBit];} else {cur = cur.son[bit];}}return res;}public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer st = new StreamTokenizer(br);st.parseNumbers();st.nextToken();int n = (int)st.nval;Node root = new Node();for(int k = 0; k < n; k++){st.nextToken();int ops = (int)st.nval;st.nextToken();int num = (int)st.nval;if(ops == 1){insert(root, num);} else if(ops == 2){remove(root, num);} else {int res = query(root, num);System.out.println(res);}}}   }