Treap adalah struktur data dasar pada pohon pencarian
random/acak. Kata treap berasala dari tree dan heap
[3]. Lebih jelasnya, misalkan x menyatakan satu set
item di mana setiap item memiliki kunci dan priority.
Treap dari set x menyata kan kasus istimewa dari
pohon pencarian biner yang mana set simpul disusun
berurutan (tergantung kunci) seperti heap fashion (
tergantung pada prioritas).
Waktu pencarian proposional terhadap kedalaman
elemen pada pohon. Penyisipan elemen memerlukan
proses 2-langkah. Langkah pertama menempatkan
posisi daun (sesuai dengan nilai kunci) dan langkah
kedua rotasi item ke atas (sesuai dengan priority
dalam sturktur pohon ). Begitu juga dengan
penghapusan yang memerlukan proses 2-langkah.
Kompleksitas waktu untuk pencarian, penyisipan dan
penghapusan adalah O (log n)[3].