Treap

Treap (ツリープ)は、乱択アルゴリズムを使用した平衡2分探索木の1つ。

平衡2分探索木のアルゴリズムの中ではアルゴリズムが単純であり、コード量が少なくてすむ。

Treap という名称は Tree (木構造)と Heap (ヒープ)という2つの単語を組み合わせて作られた。

(Wikipediaより引用)

つまり、Treapを理解したいとなったらまず先に理解するべきデータ構造があって…