算法竞赛常用数据结构-字典树Trie

本文参考资源:

详谈树结构(传统树、字典树、hash 树、Merkle Patricia Tree)_C/C++_smilejiasmile的博客-CSDN博客

概述

Tire树称为字典树,又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。高效查找的数据结构-HashTree(哈希树))典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

Trie树的缺点是它非常消耗空间。

Trie树的三个基本性质:

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

Trie树结构

算法竞赛常用数据结构-字典树Trie

从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

Trie树的应用有:

  1. 维护字符串集合(即字典)。
  2. 向字符串集合中插入字符串(即建树)。
  3. 查询字符串集合中是否有某个字符串(即查询)。
  4. 统计字符串在集合中出现的个数(即统计)。
  5. 将字符串集合按字典序排序(即字典序排序)。
  6. 求集合内两个字符串的LCP(Longest Common Prefix,最长公共前缀)(即求最长公共前缀)。

大多数时候,我们是要维护一个key-value对,key就是这个从根节点到叶子节点形成的字符串,而value信息就存储在叶子节点,例如汉英字典去查一个单词的中文翻译。

java代码实现:(根据不同的应用可以设计不同的实现)

class Node{
    int num;//有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
    Node[] children = new Node[26];//所有的子节点
    Object data;// 如果是叶子节点可以存储数据。
}

算法题示例

你考入大城市沙坪坝的学校, 但是沙坪坝的当地人说着一种很难懂的方言, 你完全听不懂。 幸好你手中有本字典可以帮你。 现在你有若干个听不懂的方言需要查询字典。

输入格式:
第一行,两个整数n和m。
接下来有n行表示字典的内容,每行表示一条字典的记录。每条记录包含两个空格间隔的单词,第一个单词为英文单词,第二个单词为对应的沙坪坝方言。
接下来有m行,每行一个单词,表示你要查询的沙坪坝方言。

输出格式:
输出m行,每行一个英文单词,表示翻译后的结果。
如果某个单词字典查不到,输出"eh"

样例输入:
5  3
dog  ogday
cat  atcay
pig  igpay
froot  ootfray
loops  oopslay
atcay
ittenkay
oopslay
样例输出:
cat
eh
loops
 注:所有单词都用小写字母表示, 且长度不超过10。

解答:

static class Node{
    Node[] children = new Node[26];//所有的子节点
    String data;// 如果是叶子节点可以存储数据。
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int referCount = scanner.nextInt();
    int targetCount = scanner.nextInt();
    Node root = new Node();
    for(int i = 0;i<referCount;i++){
        String origin = scanner.next();
        char[] refer = scanner.next().toCharArray();
        Node node = root;
        for(int n = 0;n<refer.length;n++){
            if(node.children[refer[n]-'a'] != null) {
                node = node.children[refer[n]-'a'];
                continue;
            }
            node = (node.children[refer[n]-'a'] = new Node());
            if(n == refer.length-1) node.data = origin;
        }
    }
    for(int i = 0;i<targetCount;i++){
        char[] toFind = scanner.next().toCharArray();
        Node node = root;
        boolean isFind = true;
        for(int n = 0;n<toFind.length;n++){
            if((node = node.children[toFind[n]-'a'])!=null) continue;
            isFind = false;
            break;
        }
        System.out.println(isFind?node.data:"eh");
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e7%ae%97%e6%b3%95%e7%ab%9e%e8%b5%9b%e5%b8%b8%e7%94%a8%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e5%ad%97%e5%85%b8%e6%a0%91trie/