About: Treap

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