Cây Trie

Trong lĩnh vực khoa học máy tính, cây trie hay còn gọi là cây tiền tố là một cấu trúc dữ liệu dạng cây được sử dụng để lưu trữ một tập hợp các chuỗi ký tự. Khác với cây nhị phân tìm kiếm, mỗi nút trong cây trie không liên kết với một khóa cụ thể. Thay vào đó, mỗi nút liên kết với một chuỗi ký tự, và tất cả các chuỗi ký tự của các nút con dưới một nút đều chia sẻ một tiền tố chung, đó chính là chuỗi ký tự của nút đó. Nút gốc tương ứng với chuỗi ký tự rỗng.

Tên gọi trie có nguồn gốc từ từ tiếng Anh retrieval. Theo từ nguyên học, người sáng tạo cấu trúc này, Edward Fredkin, phát âm nó là cây / triː/. Tuy nhiên, nhiều tác giả khác lại phát âm là /ˈtraɪ/.

Khóa trong cây trie không nhất thiết phải là chuỗi ký tự mà có thể là danh sách các đối tượng theo thứ tự, như chữ số hoặc hình dạng.

Ưu điểm của cây trie so với các cấu trúc dữ liệu tìm kiếm khác

Dưới đây là những lợi ích chính của cây trie so với cây nhị phân tìm kiếm:

• Tìm kiếm nhanh hơn. Việc tìm một khóa dài m chỉ mất $O\left(m\right)$ phép so sánh ký tự. Trong khi đó, cây nhị phân tìm kiếm yêu cầu $O(\log <!--\; \; -->n)$ phép so sánh chuỗi ($n$ là số lượng khóa). Trong trường hợp tồi tệ nhất, cây nhị phân tìm kiếm cần $O(m\log <!--\; \; -->n)$ phép so sánh ký tự.
• Cây trie tiết kiệm bộ nhớ hơn vì các tiền tố chung chỉ cần lưu trữ một lần.
• Cây trie cho phép tìm tiền tố dài nhất trùng khớp.
• Số lượng nút từ gốc đến lá bằng đúng độ dài của khóa.

Dưới đây là những ưu điểm chính của cây trie so với bảng băm:

• Cây trie cho phép liệt kê các khóa theo thứ tự từ điển.
• Cây trie hỗ trợ tìm tiền tố dài nhất trùng khớp.
• Do không phải tính hàm băm, cây trie thường nhanh hơn bảng băm với các khóa nhỏ như số nguyên hoặc con trỏ.

Các ứng dụng

Thay thế các cấu trúc dữ liệu khác

Như đã đề cập, trie mang lại nhiều lợi ích hơn so với cây nhị phân tìm kiếm và cũng có thể thay thế bảng băm trong nhiều tình huống.

Biểu diễn từ điển

Trie thường được sử dụng để xây dựng từ điển. Đặc biệt, nó rất hữu ích cho các ứng dụng yêu cầu tìm kiếm gần đúng, như trong phần mềm kiểm tra chính tả.

• Cây cơ số
• Cây hậu tố
• Mã hóa Huffman
• Thuật toán tìm kiếm

Chú thích