Treap

Trong khoa học máy tính, treap và cây tìm kiếm nhị phân ngẫu nhiên hóa là hai dạng cấu trúc dữ liệu cây tìm kiếm nhị phân liên quan chặt chẽ đến nhau. Chúng lưu trữ một tập hợp các khóa và cho phép chèn, xóa, và tìm kiếm khóa. Sau bất kì một dãy các thao tác chèn và xóa nào, hình dạng cây là một biến ngẫu nhiên có cùng phân phối với hình dạng của cây nhị phân ngẫu nhiên. Đặc biệt, với xác suất cao, chiều cao của cây là lôgarit của số khóa, nên mỗi thao tác tìm kiếm, chèn, hoặc xóa chỉ tốn thời gian lôgarit.

Treap

Một treap với khóa là chữ cái và dùng cấu trúc đống max

Treap được phát minh bởi Cecilia R. Aragon và Raimund Seidel năm 1989;^[1][2] Tên của nó là một từ kết hợp của tree (cây) và heap (đống). Nó là một cây Descartes^[3] trong đó mỗi khóa được gắn một độ ưu tiên ngẫu nhiên. Như với mọi cây nhị phân khác, thứ tự duyệt trung thứ tự của các nút là thứ tự tăng dần của các khóa. Cấu trúc của cây được quyết định bởi tính chất đống max: độ ưu tiên của mọi nút khác lá đều lớn hơn hoặc bằng độ ưu tiên của mọi nút trong cây con của nó. Do đó, cũng như với mọi cây Descartes nói chung, nút gốc là nút có độ ưu tiên lớn nhất.

Một cách thức mô tả tương đương của treap là có thể tạo nó bằng cách chèn các nút theo thứ tự độ ưu tiên giảm dần mà không thực hiện bất kì phép cân bằng nào. Do đó, nếu các độ ưu tiên là ngẫu nhiên (từ một phân phối trên một tập hợp đủ lớn sao cho khả năng hai nút có cùng độ ưu tiên là rất thấp) thì hình dạng treap có cùng phân phối với hình dạng cây tìm kiếm nhị phân ngẫu nhiên (cây tìm kiếm nhị phân tạo bởi việc chèn các nút theo thứ tự ngẫu nhiên mà không thực hiện bất kì phép cân bằng nào). Do cây tìm kiếm nhị phân ngẫu nhiên có chiều cao lôgarit với xác suất cao, điều đó cũng đúng cho treap.

Cụ thể, treap cho phép thực hiện các thao tác sau:

• Tìm kiếm một khóa cho trước bằng cách sử dụng thuật toán thông thường cho cây nhị phân và bỏ qua độ ưu tiên.
• Chèn khóa mới x vào treap bằng cách đầu tiên sinh một trọng số ngẫu nhiên y cho x. Tìm kiếm x trên cây và chèn một nút mới chứa x vào vị trí trống mới tìm được. Sau đó thực hiện các phép quay cây để phục hồi tính chất đống: chừng nào x còn chưa là nút gốc và có độ ưu tiên lớn hơn nút cha là z, thì thực hiện phép quay cây trên cạnh nối x và z.
• Xóa khóa x trong treap như sau: nếu x là nút lá, thì xóa nó. Nếu x có một nút con z, xóa x và đặt z vào làm nút con của nút cha của x (hoặc đặt z làm gốc của cây nếu x là gốc cũ). Cuối cùng, nếu x có hai nút con, đổi chỗ x và nút nhỏ nhất trong cây con phải của x là z, và thực hiện một trong hai trường hợp trên cho x ở vị trí mới. Trong trường hợp cuối, z có thể vi phạm tính chất đống nên cần thực hiện các phép quay cây để phục hồi tính chất đống.
• Chia treap thành hai treap, một chứa các khóa nhỏ hơn x, và một chứa các khóa lớn hơn x bằng cách chèn x với độ ưu tiên cao hơn tất cả các khóa vào treap. Sau khi chèn xong, x trở thành nút gốc, và mọi khóa nhỏ hơn x nằm ở treap con bên trái và mọi khóa lớn hơn x nằm ở treap con bên phải. Chi phí của thao tác này đúng bằng một lần chèn.
• Hợp hai treap lại làm một (giả sử mọi khóa của treap thứ nhất nhỏ hơn mọi khóa của treap thứ hai) như sau. Chèn x sao cho x lớn hơn mọi khóa ở treap thứ nhất, và nhỏ hơn mọi khóa của treap thứ hai với độ ưu tiên của x nhỏ hơn độ ưu tiên của mọi khóa. Sau khi chèn xong, x là một nút lá nên có thể xóa dễ dàng. Kết quả thu được là một treap đúng bằng hai treap cũ hợp lại.

Aragon và Seidel cũng khuyên nên gán cho các nút hay được truy cập trọng số lớn hơn. Thay đổi này làm cây không còn ngẫu nhiên mà khiến cho các nút hay được truy cập dễ nằm ở gần gốc của cây hơn, khiến cho việc tìm chúng nhanh hơn.

Blelloch và Reid-Miller^[4] mô tả một ứng dụng của treap để lưu trữ các tập hợp các đối tượng và hỗ trợ các thao tác hợp tập hợp, giao tập hợp, và phần bù tương đối bằng cách dùng một treap để biểu diễn mỗi tập hợp. Naor và Nissim^[5] mô tả một ứng dụng khác để lưu trữ chứng nhận khóa công khai trong mật mã khóa công khai.

Tham khảo

1. Aragon, Cecilia R.; Seidel, Raimund (1989), “Randomized Search Trees”, [[Symposium on Foundations of Computer Science|Proc. 30th Symp. Foundations of Computer Science (FOCS 1989)]] (PDF), Washington, D.C.: IEEE Computer Society Press, tr. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1 Tựa đề URL chứa liên kết wiki (trợ giúp)
2. Seidel, Raimund; Aragon, Cecilia R. (1996), “Randomized Search Trees”, Algorithmica, 16 (4/5): 464–497, doi:10.1007/s004539900061
3. Vuillemin, Jean (1980), “A unifying look at data structures”, Commun. ACM, New York, NY, USA: ACM, 23 (4): 229–239, doi:10.1145/358841.358852.
4. Blelloch, Guy E.; Reid-Miller, Margaret (1998), “Fast set operations using treaps”, Proc. 10th ACM Symp. Parallel Algorithms and Architectures (SPAA 1998), New York, NY, USA: ACM, tr. 16–26, doi:10.1145/277651.277660, ISBN 0-89791-989-0.
5. Naor, M.; Nissim, K. (2000), “Certificate revocation and certificate update” (PDF), IEEE Journal on Selected Areas in Communications, 18 (4): 561–570, doi:10.1109/49.839932^{[liên kết hỏng]}.

Liên kết ngoài

• Tuyển tập tài liệu tham khảo và thông tin về treap bởi Cecilia Aragon
• Applet minh họa treap Lưu trữ 2015-03-04 tại Wayback Machine bởi Kubo Kovac
• Applet minh họa treap
• Cây tìm kiếm nhị phân ngẫu nhiên hóa Lưu trữ 2011-06-05 tại Wayback Machine. Bài giảng của Jeff Erickson tại UIUC. Nội dung chủ yếu là về treap và skip list và chỉ đề cập một chút đến cây tìm kiếm nhị phân ngẫu nhiên hóa.
• Một cơ sở dữ liệu lưu khóa-giá trị dựa trên treap bởi Junyi Sun
• VB6 implementation of treaps Lưu trữ 2010-01-27 tại Wayback Machine. Treap dưới dạng một đối tượng COM viết bằng Visual basic 6.
• Treap viết bằng ActionScript3
• Treap viết bằng Python và Cython