Cấu trúc dữ liệu và Giải thuật Bài 52: Cây Tiền Tố (Trie / Prefix Tree) - Tối ưu hóa tìm kiếm chuỗi và Autocomplete.

Trong suốt Chương 8, chúng ta đã tôn vinh Bảng băm (Hash Table) như một vị vua không thể lay chuyển về tốc độ tra cứu chính xác tuyệt đối ở mức O(1). Tuy nhiên, Hash Table có một điểm mù chí mạng: Nó chỉ trả lời được câu hỏi "Chuỗi này có tồn tại hay không?".

Nếu bạn gõ từ khóa has lên một thanh tìm kiếm và hệ thống phải ngay lập tức gợi ý tất cả các từ bắt đầu bằng tiền tố đó như hasaki, hasan, hastings, Bảng băm hoàn toàn bất lực. Nó không có khả năng nhận biết "tiền tố" (prefix) và buộc phải quét qua toàn bộ hàng triệu bản ghi trong cơ sở dữ liệu.

Để giải quyết triệt để bài toán tìm kiếm theo tiền tố và hiện thực hóa tính năng Gợi ý tự động (Autocomplete), chúng ta bước vào một cấu trúc dữ liệu cây chuyên biệt mang tên Trie (Prefix Tree).

1. Giải phẫu Cây Tiền Tố (Trie)

Tên gọi Trie bắt nguồn từ chữ Retrieval (Truy xuất), nhưng trong thực tế, các kỹ sư luôn phát âm nó là "Try".

Trie là một Cây N-phân (N-ary Tree) được thiết kế riêng để lưu trữ tập hợp các chuỗi ký tự. Điểm đột phá của Trie nằm ở chỗ nó không lưu trữ toàn bộ từ ở mỗi Node, mà lưu trữ từng ký tự đơn lẻ. Các từ có chung một tiền tố sẽ được gom lại và đi chung một con đường từ gốc cây đi xuống.

Cấu trúc một Node trong Trie:

Children Map (Hoặc Mảng 26 ký tự): Chứa các con trỏ trỏ tới các Node tiếp theo tương ứng với các ký tự trong bảng chữ cái (ví dụ: 'a', 'b', 'c'...).
IsEndOfWord (Boolean): Cờ đánh dấu. Nếu một chuỗi kết thúc tại Node này, cờ sẽ được bật thành true để xác nhận đây là một từ hoàn chỉnh, không chỉ là một đoạn tiền tố dọc đường.

Ví dụ trực quan:

Nếu bạn đưa vào Trie ba từ: cat, car, và dog:

Từ gốc (Root) rẽ nhánh sang c, từ c rẽ sang a.
Từ a, cây rẽ làm hai hướng: Một nhánh sang t (kết thúc từ cat), và một nhánh sang r (kết thúc từ car).
Nhánh d hoàn toàn độc lập rẽ sang o, rồi đến g (kết thúc từ dog).

2. Triển khai Trie bằng Golang

Dưới đây là thiết kế chuẩn mực của một Trie với ba thao tác cốt lõi: Insert (Thêm từ), Search (Tìm chính xác), và StartsWith (Tìm theo tiền tố).

package main

import "fmt"

// Định nghĩa một Node trong Trie
type TrieNode struct {
    children    map[rune]*TrieNode
    isEndOfWord bool
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{
        root: &TrieNode{
            children: make(map[rune]*TrieNode),
        },
    }
}

// 1. Thêm từ vào Trie - Độ phức tạp thời gian: O(m) với m là độ dài từ
func (this *Trie) Insert(word string) {
    current := this.root
    for _, ch := range word {
        // Nếu ký tự chưa tồn tại, tạo Node mới
        if _, exists := current.children[ch]; !exists {
            current.children[ch] = &TrieNode{
                children: make(map[rune]*TrieNode),
            }
        }
        current = current.children[ch]
    }
    // Bật cờ đánh dấu kết thúc một từ hoàn chỉnh
    current.isEndOfWord = true
}

// 2. Tìm kiếm chính xác một từ - Độ phức tạp thời gian: O(m)
func (this *Trie) Search(word string) bool {
    current := this.root
    for _, ch := range word {
        if _, exists := current.children[ch]; !exists {
            return false // Đứt đoạn, từ không tồn tại
        }
        current = current.children[ch]
    }
    // Phải đảm bảo Node cuối cùng thực sự là kết thúc của một từ
    return current.isEndOfWord
}

// 3. Kiểm tra tiền tố (Prefix) - Độ phức tạp thời gian: O(m)
func (this *Trie) StartsWith(prefix string) bool {
    current := this.root
    for _, ch := range prefix {
        if _, exists := current.children[ch]; !exists {
            return false
        }
        current = current.children[ch]
    }
    // Chỉ cần đi hết chuỗi prefix thành công là đủ, không cần xét cờ isEndOfWord
    return true
}

3. Tại sao Trie là một "Quái vật" về Tốc độ?

Nhìn vào đoạn code trên, bạn sẽ nhận ra một đặc điểm kỹ thuật cực kỳ đắt giá: Thời gian thực thi của Trie hoàn toàn không phụ thuộc vào số lượng từ đang có trong hệ thống ( $N$ ).

Cho dù Trie của bạn đang lưu trữ 10 từ hay 100 triệu từ, thời gian để bạn tìm kiếm một từ có độ dài $m$ ký tự luôn luôn là O(m).
Trong thực tế, độ dài của một từ hoặc một tiền tố tìm kiếm ( $m$ ) thường là một hằng số rất nhỏ (ví dụ: từ khóa tìm kiếm dài từ 3 đến 15 ký tự). Do đó, các thao tác trên Trie gần như đạt tốc độ tức thời O(1) thực tế.

Bên cạnh đó, Trie tối ưu hóa bộ nhớ cực tốt nhờ Sự chia sẻ tiền tố (Prefix Sharing). Các từ có chung phần đầu sẽ dùng chung một hệ thống Node, giúp giảm thiểu đáng kể dung lượng RAM so với việc lưu trữ từng chuỗi rời rạc.

4. Ứng dụng thực tế trong Kiến trúc Hệ thống

Trie không chỉ là bài toán phỏng vấn, nó đứng đằng sau những tính năng cốt lõi của các nền tảng công nghệ lớn:

Hệ thống Gợi ý Từ khóa (Autocomplete / Typeahead): Khi bạn gõ has lên thanh tìm kiếm, hệ thống duyệt dọc theo Trie đến Node s, sau đó kích hoạt thuật toán vét cạn (DFS/BFS) từ Node đó để gom tất cả các nhánh con bên dưới và trả về danh sách gợi ý (hasaki, hastings,...) trong mili-giây.
Trình kiểm tra chính tả (Spell Checker): Các trình soạn thảo văn bản nạp toàn bộ từ điển ngôn ngữ vào một Trie. Khi bạn gõ sai một từ, hệ thống tra cứu trên Trie O(m) để xác định ngay lập tức từ đó có tồn tại hay không.
Định tuyến IP (Longest Prefix Matching): Trong phần cứng Router mạng, các bảng định tuyến (Routing Tables) sử dụng biến thể của Trie (Binary Trie) để khớp các gói tin mạng với dải địa chỉ IP có tiền tố trùng khớp dài nhất với tốc độ phần cứng tối đa.

Sự sắc bén của Trie giúp chúng ta giải quyết hoàn hảo các bài toán về cấu trúc từ và chuỗi tiền tố. Tuy nhiên, nếu bài toán chuyển dịch sang việc tìm kiếm một chuỗi con bất kỳ nằm bên trong một văn bản khổng lồ (Ví dụ: Tìm xem từ "hieu" xuất hiện ở những vị trí nào trong một file log hệ thống dài 10 Gigabyte), Trie sẽ không đủ sức mạnh. Chúng ta cần một lớp thuật toán tìm kiếm chuỗi con chuyên sâu hơn.

cấu trúc dữ liệu

1. Giải phẫu Cây Tiền Tố (Trie)

2. Triển khai Trie bằng Golang

3. Tại sao Trie là một "Quái vật" về Tốc độ?

4. Ứng dụng thực tế trong Kiến trúc Hệ thống

Mục lục