Thuật toán tìm kiếm Tam Phân (Trisearch), xác định vị trí của phần tửcần tìm trongmột bảng lệt kê các phần tửđươợc sắp xếp theo thứ tự tăng (hay giảm) dần của trường khoá. Bằng cách chialiên tiếp bảng liệt kê thành ba bảng liệt kê con có kích thơước tương đươơng nhau (Step=(R-L+1) div 3). Thuật toán này là sự thể hiện sinh động của tinh thần “chia để trị”. Giả sử bảng liệt kêđơược xác định bởi hai con trỏ L,R, trỏ đến phần tử trái và phải. Thuật toán sẽ chia bảng [L,R] thành ba bảng con: [L,U-1], [U+1,V-1], [V+1,R]. Dựa vào giá trị khoá của Argument và giá trị khoá tại các điểmU=Step , V=L+2*Step. Tìm kiếm sẽ dừng nếu khoá của mẫu bằng với giá trị khoá của một trong hai điểm trên, ngược lại tìm kiếm sẽ tiếp tục trên một trong ba bảng con đơược chia. Quá trình cứ tiếp tục nhươ thế cho đến khi tìmđươợc phần tử mong muốn hoặc bảng phần tử đang sét là rỗng. Hình 1 mô tả hình thức tam phân của Trisearch theo sơ đồ “chia để trị”.

(Hình 1- Bảng khoá chia 3 theo sơ đồ chia để trị )

Thuật toán sau đây được trình bày đưới dạng giả mã, sẽ tìm kiếm phần tử Item trong mảng Key đã được sắp xếp theo thứ tự tăng dần:

intTrisearch(int key[], int item,int l, int r)

{

int u, v, result, step;

result=0;

while ((l<=r) && (result==0))

{

step =(r-l+1) / 3;

u=l+step; v=l+2*step;

if (item == key[u] ) result=u;

else

if (item == key[v] ) result=v;

else

if (item > key[v]) l=v+1;

else

if (item > key[u])

{

l=u+1;

r=v-1;

}

else

r=u-1;

}

return (result);

}

Chúng ta có thể cài đặt thuật toán trên theo phương pháp đệ quy. Với vùng bộ nhớ Stack hạn chế, nên lưu ý khi kích thước bảng phần tử lớn ta nên truyền tham số Key theo kiểu tham chiếu (địa chỉ). Điều này giúp ta tránh được lỗi “Stack overflow error” do tràn vùng bộ nhớ ngăn xếp.

intTrisearch_dq( int key[], int item,intl, int r)

{

int u, v, step;

if(l<=r)

{

step=(r-l+1) / 3;

u=l+step; v=l+2*step;

if (item == key[u])return u;

else

if (item == key[v])return v;

else

if (item >key[v] )

return Trisearch_dq(key, item,v+1,r);

else+

if (item >key[u] )

return Trisearch_dq(key, item,u+1,v-1);

else

return Trisearch_dq(key, item,l,u-1);

}

else /*khong thanh cong*/

return 0;

}

Khi nói đến các thuật toán tìm kiếm, chúng ta sẽ cảm thấy quen thuộc hơn với thuật toán tìm kiếm nhị phân (Binsearch). Có lẽ bởi tính tự nhiên của phương pháp và dễ cài đặt của thuật toán. Binsearch có độ phức tạp thuật toán về thời gian là O(log₂n). Vậy hiệu quả của Trisearch so với Binsearch? Dễ nhận thấy rằng so với Binsearch thì thuật toán Trisearch trong cài đặt đệ quy sẽ hội tụ nhanh hơn, hạn chế khả năng đệ quy sâu. Sau đây chúng ta sẽ phân tích độ phức tạp thuật toán về thời gian của Trisearch.

Không giảm tính tổng quát, ta giả thiết phạm vi tìm kiếm là từ 1 đến N, bảng key có N phần tử. Sau lần lặp thứ nhất phạm vi tìm kiếm là phần tử, sau lần lặp thứ 2 phạm vi tìm kiếm là . Trong trường hợp tồi nhất vòng lặp While sẽ kết thúc khi , hay . Trong mỗi lần lặp tốn thời gian O(1) nên thời gian thực hiện của hàm Trisearch là . Dễ nhận thấy rằng Binsearch và Trisearch có cùng độ phức tạp, hay (vì ). Nhìn vào bảng khảo sát liệt kê giá trị tại một số điểm (hình 2), đồ thị của (hình 3) ta cũng thấy được mối tương quan giữa hai hàm.

Nhưng có lẽ không nên đánh giá thuật toán tìm kiếm này tốt hơn thuật toán tìm kiếm khác. Điều quan trọng là sử dụng chúng sao cho phù hợp với từng ứng dụng và yêu cầu cụ thể. Không có cách nào hiểu thấu đáo một thuật toán nhanh hơn là bắt tay cài đặt chúng. Mình rất mong được học hỏi và đóng góp ý kiến của tất cả các bạn(Tanbv_it@yahoo.com).

School@net (Theo THNT)