Treap

Treap (ツリープ)は、乱択アルゴリズムを使用した平衡2分探索木の1つ。1989年に Cecilia R. Aragon と Raimund Seidel が発表した^[1][2]。平衡2分探索木のアルゴリズムの中ではアルゴリズムが単純であり、コード量が少なくてすむ。Treap という名称は Tree (木構造)と Heap (ヒープ)という2つの単語を組み合わせて作られた。

1. ^ Aragon, Cecilia R.; Seidel, Raimund (1989), “Randomized Search Trees”, Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1, http://faculty.washington.edu/aragon/pubs/rst89.pdf 
2. ^ Seidel, Raimund; Aragon, Cecilia R. (1996), “Randomized Search Trees”, Algorithmica 16 (4/5): 464–497, doi:10.1007/s004539900061, http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8602