Thông thường, người ta thường sử dụng trie khi cần lưu trữ một tập dữ liệu gồm các xâu (tổng quát hơn, có thể là các số lớn vài chục chữ số...)

Cấu trúc:

Trie gồm một gốc không chứa thông tin, trên mỗi cạnh lưu một ký tự, mỗi nút và đường đi từ gốc đến nút đó thể hiện 1 xâu, gồm các ký tự là các ký tự thuộc cạnh trên đường đi đó.

Ví dụ:

Trong hình vẽ trên, nút 1 là nút gốc, nút 7 thể hiện có 1 xâu là ‘bg’, nút 8 thể hiện có 1 xâu là ‘db’, nút 9 thể hiện có 1 xâu là ‘dc’, nút 10 thể hiện có 1 xâu là ‘acd’, nút 5 thể hiện là có 1 xâu là ‘ab’.

Tuy nhiên, như các bạn có thể thấy, đối với một số nút, chẳng hạn nút 4, ta không biết nó là thể hiện kết thúc 1 xâu hay chỉ là 1 phần của đường đi từ nút 1 đến nút 9. Vì vậy, khi cài đặt, thông thường, tại nút U ta cần lưu thêm thông tin nút U có là kết thúc của 1 xâu hay không, hoặc nút U là kết thúc của bao nhiêu xâu (tuỳ bài toán).

Một số ưu điểm của trie:

1/ Cài đặt đơn giản, dễ nhớ

2/ Tiết kiệm bộ nhớ: Khi số lượng khóa lớn và các khóa có độ dài nhỏ, thông thường trie tiết kiệm bộ nhớ hơn do các phần đầu giống nhau của các khoá chỉ được lưu 1 lần. Ưu điểm này có ứng dụng rất lớn, chẳng hạn trong từ điển điện thoại

3/ Thao tác tìm kiếm: O(m) với m là độ dài khóa. Với binary search tree (cân bằng): là O(logN). Khi số lượng khóa cần tìm lớn, logN xấp xỉ m, và như các bạn đã biết, để cài được binary search tree cân bằng không phải là một việc đơn giản. Hơn nữa, trên thực tế, trie chỉ đòi hỏi các phép đi đến 1 phần tử có chỉ số cho trước của mảng, và thông thường thao tác này nhanh hơn trên thực tế.

4/ Dựa vào tính chất của cây trie, có thể thực hiện một số liên quan đến thứ tự từ điển như sắp xếp, tìm một khóa có thứ tự từ điển nhỏ nhất và lớn hơn một khóa cho trước...; và một số thao tác liên quan đến tiền tố, hậu tố.

Cài đặt cụ thể:

//Định nghĩa kiểu trie

type

trie=^node;

node=record

count:longint; //Số lượng xâu kết thúc tại một nút

c:array[‘a’..’z’] of trie; //Link đến các nút con của một nút

end;

var

root:trie; //Gốc trie

//Thêm một nút rỗng vào trie

procedure add(var a:trie);

var

c:char;

begin

new(a);

a^.count:=0;

for c:=’a’ to ‘z’ do

a^.c[c]:=nil;

end;

//Thêm xâu s vào trie

procedure insert(s:string);

var

i:longint;

begin

for i:=1 to length(s) do

begin

//Duyệt mỗi kí tự i của s. Với mỗi kí tự, ta đi theo nhánh tương ứng với ký tự i, nếu nhánh này chưa có, ta thêm vào cây

if p^.c[s[i]]=nil then add(p^.c[s[i]]);

p:=p^.c[s[i]];

end;

inc(p^.count);

end;

//Tìmxem xâu s có trong trie không

function find(s:string):boolean;

var

i:longint;

p:trie;

begin

p:=root;

for i:=1 to length(s) do

begin

if p^.c[s[i]]=nil then exit(false);

p:=p^.c[s[i]];

end;

exit(true);

end;

(Có thể cài đặt thêm thao tác xóa một từ khỏi trie, nhưng đối với các bài toán thường gặp đối với học sinh cấp 3 thì thông thường thao tác này không cần thiết. Việc cài đặt cụ thể xin nhường lại cho bạn đọc)

Một vài ứng dụng trong các bài toán

Sau đây là một vài ví dụ cơ bản thể hiện tác dụng của trie

1/ Chuỗi từ:

(Nguồn: Цикл Интернет-олимпиад для школьников, сезон 2007-2008)

Chuỗi từ có độ dài n là một dãy các từ w₁, w₂, ..., w_n sao cho với mọi 1 ≤ i < n, từ w_ilà tiền tố của từ w_i+1.Từ u có độ dài k là tiền tố của từ v có độ dài l nếu l > k và các ký tự đầu tiên của v trùng với từ u. Cho tập hợp các từ S={s₁, s₂, ..., s_m}. Tìm chuỗi từ dài nhất có thể xây dựng được bằng cách dùng các từ trong tập hợp S (có thể không sử dụng hết các từ).

Thuật toán:

Một trong những cách giải khá đơn giản đối với bài này là sử dụng trie:

Lưu tất cả các từ lại vào trie. Đối với mỗi nút trên cây, ta tính f là độ dài chuỗi từ dài nhất bắt đầu ở nút đó.

Cài đặt một số phần quan trọng:

type

trie=^node;

node=record

f,u:longint; //Số lượng xâu kết thúc tại một nút

c:array[‘a’..’z’] of trie; //Link đến các nút con của một nút

end;

...

procedure dfs(a:trie);

var

c:char;

begin

a^.f:=0

for c:=’a’ to ‘z’ do

begin

dfs(a^.c[c]);

a^.f:=max(a^.f,a^.c[c].f);

end;;

inc(a^.f,a^.u);

end;

function solve:longint;

begin

add(root);

for i:=1 to m do insert(s[i]);

dfs(root);

exit(root^.f);

end;

2/ Tách từ:

(Nguồn: Croatian OI 2006)

Một xâu S độ dài ≤ 300 000 cần được tách thành các đoạn con sao cho mỗi đoạn con thuộc một tập gồm ≤ 400 từ cho trước, mỗi từ có độ dài ≤ 100, không có 2 từ nào giống nhau.

Viết chương trình xác định số cách tách một từ cho trước.

Thuật toán:

Quy hoạch động.

Đặt f[i] = số cách tách đoạn từ 1..i của S.

Như vậy, f[i] = tổng f[j] với mỗi j thoả mãn đoạn từ j+1..i là một từ thuộc tập từ đã cho. Ta lần lượt tính f[i] với i chạy từ 1 đến n. Với mỗi i, để kiểm tra mọi đoạn j..i có là một từ cho trước không, chú ý là khi giảm j, các từ này có độ dài tăng lên, và từ trước là hậu tố của từ sau, các từ có độ dài hơn kém nhau một đơn vị. Do đó, trên cây trie, ta có thể đi từ gốc xuống các nút thể hiện các xâu này, nếu không đi được nữa, tức là không có từ nào thoả mãn. Chú ý là khi thêm các xâu của tập đã cho, ta cần thêm các xâu này theo chiều ngược (hoặc một cách xử lý khác là ta tính hàm f từ n đến 1).

Cài đặt một số phần quan trọng:

f[0]=1;

for i:=1 to n do

begin

j:=i; p:=root;

while (j>0) and (p^.c[s[j]]<>nil) do

begin

p:=p^.c[s[j]];

dec(j);

if (x^.c=1) then inc(f[i],f[j]);

end;

end;

School@net