Trie (Prefix Tree)

1. Giới thiệu

Trie (hay Prefix Tree) là một cấu trúc dữ liệu dạng cây được sử dụng để lưu trữ và tìm kiếm các chuỗi. Mỗi node trong cây đại diện cho một ký tự, và đường đi từ gốc đến node lá tạo thành một từ hoặc chuỗi.

2. Đặc điểm chính

Tìm kiếm prefix với độ phức tạp O(m), m là độ dài prefix
Tiết kiệm bộ nhớ khi lưu trữ nhiều chuỗi có prefix chung
Hỗ trợ tốt cho các thao tác liên quan đến prefix
Thích hợp cho auto-complete và spell checker

3. Cấu trúc node

class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // Cho 26 chữ cái tiếng Anh
        isEndOfWord = false;
    }
}

4. Các thao tác cơ bản

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Thêm từ vào Trie
    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    // Tìm kiếm từ trong Trie
    public boolean search(String word) {
        TrieNode node = searchNode(word);
        return node != null && node.isEndOfWord;
    }

    // Kiểm tra prefix
    public boolean startsWith(String prefix) {
        return searchNode(prefix) != null;
    }

    private TrieNode searchNode(String str) {
        TrieNode current = root;
        for (char ch : str.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                return null;
            }
            current = current.children[index];
        }
        return current;
    }
}

5. Ứng dụng thực tế

Auto-complete và gợi ý từ
Spell checker
Định tuyến IP (IP routing)
Từ điển và tra cứu từ
Tìm kiếm chuỗi con (String matching)

6. Bài tập thực hành

Implement Trie hỗ trợ xóa từ
Xây dựng ứng dụng auto-complete đơn giản
Tìm tất cả các từ có prefix cho trước
Đếm số từ có prefix chung

7. Tối ưu và mở rộng

Nén Trie để tiết kiệm bộ nhớ
Hỗ trợ nhiều bộ ký tự khác nhau
Thêm trọng số cho từng từ
Radix Tree - biến thể của Trie