Префиксное дерево (trie)

Префиксное дерево (trie) - структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. См. статьи в Wikipedia: trie, префиксное дерево.

Префиксное дерево используется для множества приложений: вместо других структур данных (например, хеш-таблиц), представление словарей, сортировка, полнотекстовый поиск, битовые и сжатые деревья. Алгоритм Ахо-Корасик (используется для поиска подстроки в строке) строит префиксное дерево в процессе своей работы.

Реализация префиксного дерева на Java:

import java.util.*;
 
public class Trie {
    static class TrieNode {
        Map<Character, TrieNode> children = new TreeMap<Character, TrieNode>();
        boolean leaf;
    }
 
    TrieNode root = new TrieNode();
 
    public void put(String s) {
        TrieNode v = root;
        for (char ch : s.toLowerCase().toCharArray()) {
            if (!v.children.containsKey(ch)) {
                v.children.put(ch, new TrieNode());
            }
            v = v.children.get(ch);
        }
        v.leaf = true;
    }
 
    public boolean find(String s) {
        TrieNode v = root;
        for (char ch : s.toLowerCase().toCharArray()) {
            if (!v.children.containsKey(ch)) {
                return false;
            } else {
                v = v.children.get(ch);
            }
        }
        return true;
    }
 
    static Map<Integer,String> levelSpacesMap = new HashMap<Integer,String>();
 
    static String getSpace(int level) {
        String result = levelSpacesMap.get(level);        
        if (result == null) {
            StringBuilder sb = new StringBuilder();
            for (int i=0; i<level; i++) {
                sb.append(" ");
            }
            result = sb.toString();
            levelSpacesMap.put(level,result);
        }
        return result;
    }
 
    public static void printSorted(TrieNode node) {
        printSorted2(node,0);        
    }
 
    private static void printSorted2(TrieNode node, int level) {
        for (Character ch : node.children.keySet()) {
            System.out.println(getSpace(level)+ch);
            printSorted2(node.children.get(ch), level+1);
        }
        if (node.leaf) {
            System.out.println();
        }
    }    
 
    // Usage example
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.put("hello");        
        trie.put("house");
        trie.put("hell");
        trie.put("world");
        System.out.println(trie.find("hello"));
        printSorted(trie.root);
    }
}