Thực đơn
Treap TreapTreap đượ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:
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.
Thực đơn
Treap TreapLiên quan
Treap Treasure Treasure (bài hát của Bruno Mars) Treponema pallidum TRAPPIST-1 Treasure Planet Trespass (phim 2011) TRAPPIST-1c Trapani Calcio Trapusa và BahalikaTài liệu tham khảo
WikiPedia: Treap http://www.fernando-rodriguez.com/a-high-performan... http://code.google.com/p/as3-commons/source/browse... http://code.google.com/p/treapdb/ http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applet... http://citeseer.ist.psu.edu/viewdoc/summary?doi=10... http://www.cs.uiuc.edu/class/sp09/cs473/notes/08-t... http://faculty.washington.edu/aragon/pubs/rst89.pd... http://faculty.washington.edu/aragon/treaps.html http://stromberg.dnsalias.org/~dstromberg/treap/ //doi.org/10.1007%2Fs004539900061