Struktur Data Treap

Sebagai alternatif AVL Tree, Red Black Tree, dan Splay Tree

Bila Anda sering berkecimpung dalam soal dynamic range query, tidak jarang Anda akan menemukan soal yang membutuhkan Balanced Binary Search Tree (BBST) untuk menyelesaikannya. Biasanya, persoalan tersebut melibatkan:

• Dynamic Order Statistic, yaitu diberikan informasi nilai-nilai yang bisa berubah-ubah, lalu sering ditanyakan "Bila nilai-nilai diurutkan dari yang terbesar, siapa yang berada di posisi ke-i?", atau
• Penambahan dan penghapusan objek yang rentang nilainya bisa sangat besar (sehingga array tidak cukup), dan tidak dapat dilakukan grid compression (pemetaan koordinat menjadi yang hanya dibutuhkan saja), dan terdapat query lain yang tidak dapat dilayani oleh STL set atau map pada C++ secara efisien.

Untuk mengatasi kedua hal tersebut, biasanya orang akan menggunakan BBST. Untuk competitive programming, BBST yang populer adalah AVL Tree dan Red-Black Tree. Lalu apakah masalah selesai sampai di sini?

Ada masalah utama dari AVL Tree dan Red-Black Tree, yaitu sulit untuk menulis implementasinya. Sekalipun kompetisi itu berbentuk ICPC dan Anda memiliki catatan implementasinya, Anda masih harus berhadapan dengan panjang dan rumitnya implementasi tersebut (AVL Tree yang saya implementasikan ada 200 baris). Banyaknya baris kode yang Anda tulis akan meningkatkan peluang terjadinya kesalahan, dan sekalinya ada bug, sulit untuk mendeteksi di mana bug itu berada!

Nah karena masalah tersebut, terdapat varian BBST yang lebih ramah dalam hal implementasi: treap. Struktur data ini merupakan "gabungan" dari struktur Binary Search Tree dan heap. Bentuknya berupa binary tree yang tidak harus complete. Setiap node pada treap mengandung dua nilai, yaitu priority dan key. Perlu diperhatikan nilai priority di sini sifatnya sebagai pembantu dalam menyeimbangkan struktur tree, sehingga nilainya tidak berkaitan dengan nilai sebenarnya yang ingin Anda simpan. Bahkan dalam implementasinya, nilai priority didapatkan dengan random. Oleh karena itu treap juga dikenal sebagai randomized data structure, dan memiliki kompleksitas operasi penambahan, penghapusan, dan pencarian dalam expected O(log N). Menurut sumber-sumber yang saya baca, konstanta dari struktur data ini kecil, sehingga expected O(log N) yang dimiliki sangat ringan dan cepat!

Treap harus memenuhi dua aturan:

1. Setiap node harus memiliki priority yang lebih besar daripada anak-anaknya (aturan seperti pada heap)
2. Setiap node harus memiliki key yang lebih besar daripada seluruh node di subtree anak kirinya, dan lebih kecil dari seluruh node di subtree anak kanannya (aturan seperti pada BST)

Berikut ini adalah contoh treap yang benar. Nilai yang berada di atas adalah priority, dan yang di bawah adalah key.

Inisialisasi struktur data

Seperti halnya BST, treap dimulai dengan tree yang kosong.

Penambahan pada treap

Setiap kali hendak memasukkan node baru dengan suatu nilai key tertentu, ditentukan nilai priority secara acak. Selanjutnya, penambahan akan dimulai dari root dan skenarionya adalah:

1. Jika subtree saat ini kosong, maka langsung tempatkan node baru itu dan selesai.
2. Jika root subtree saat ini memiliki priority yang lebih besar dari priority node yang baru, lakukan penambahan secara rekursif ke subtree kiri atau kanan bergantung pada nilai key (seperti penambahan pada BST). Setelah itu, selesai.
3. Selain daripada itu, node yang baru harus diselipkan sebagai root subtree saat ini. Oleh karena itu lakukan prosedur yang akan dijelaskan dibagian bawah, lalu selesai.

Untuk kasus ketiga, cara menyelipkan node yang baru sebagai root dari suatu subtree dilakukan seperti "membelah". Anggap x sebagai node yang baru ingin dimasukkan. Perhatikan gambar berikut:

Jadi untuk mempertahankan struktur BST, node yang hendak dimasukkan membelah subtree menjadi dua bagian. Beruntungnya, yang perlu dilakukan tinggal menyambung-nyambung bagian yang terbelah dengan "parent terdekatnya". Detil implementasi dapat Anda lihat di bagian berikutnya.

Pencarian pada treap

Persis seperti pada BST, yang diperlukan cukup telusuri mulai dari root dan pergi ke anak kiri atau kanan bergantung pada key.

Penghapusan pada treap

Menghapus node pada treap sangat mirip dengan menghapus pada BST. Pertama, cari dulu node yang hendak dihapus. Kemudian ada tiga kasus:

1. Node itu tidak memiliki anak. Tinggal hapus saja node itu.
2. Node itu memiliki satu anak. Cukup ganti node itu dengan anaknya (posisinya diambil alih), lalu hapus node itu.
3. Node itu memiliki dua anak. Yang perlu dilakukan adalah mencari successor in-order (nilai terkecil dari subtree kanannya), lalu memindahkannya untuk menempati posisi node yang hendak dihapus. Setelah itu, ubah priority dari successor in-order itu supaya sama dengan priority node yang ingin dihapus. Terakhir, baru hapus node yang memang ingin dihapus.

Generalisasi untuk kasus umum

Selain priority dan key, umumnya pada perlu disimpan banyaknya node pada subtree yang memiliki root pada node itu. Setiap kali dilakukan perubahan struktur subtree, lakukan update pada root subtree tersebut seperti halnya pada BBST (lihat bagian implementasi, fungsi update).

Bagaimana jika mungkin ada elemen yang sama pada treap?
Untuk mengakalinya, bisa dibuat treap itu berperan sebagai map, yaitu dengan menambahkan satu nilai tambahan pada setiap node: value. Jadi bila ada 3 elemen yang memiliki key=5, maka node dengan key=5 akan memiliki value=3. Perlu diperhatikan, dengan cara ini setiap penambahan belum tentu akan menambahkan node baru, demikian pula penghapusan yang belum tentu akan menghapus suatu node (lihat bagian implementasi, fungsi insert dan delete).

Analisa kompleksitas

Biasanya orang-orang akan ragu, apakah benar treap cukup cepat untuk menjadi alternatif BBST? Mari kita analisa performanya, yang mana sangat mirip dengan menganalisa performa randomized quicksort.

Misalkan terdapat N node pada treap. Maka masing-masing dari node tersebut memiliki peluang yang sama untuk menjadi root dari treap (dengan asumsi fungsi random untuk menentukan priority setiap node cukup uniform). Misalkan node u terpilih sebagai root, maka semua node yang value-nya lebih kecil akan ditempatkan sebagai subtree di anak kiri u, dan yang lebih besar akan ditempatkan sebagai subtree di anak kanan u. Kemudian masing-masing subtree di kiri dan kanan u akan mengikuti pola yang serupa secara rekursif. Jadi, ketinggian dari treap itu adalah 1 ditambah ketinggian maksimum dari subtree kiri dan subtree kanan.

Artinya, bila E[H] menyatakan ketinggian yang diharapkan dari treap yang berisi H sebagai himpunan key, maka dapat dirumuskan:

\(\displaystyle
E[H]= \left\{ \begin{array}{ll} |H| &,|H| \le 1 \\ \frac{1}{|H|} \sum_{a \in H} ( 1 + max(E[H_{\lt a}], E[H_{\gt a}]) )&,|H|>1\end{array} \right.
\)

Penyelesaian dari rekurens itu adalah log N, yang mana artinya kedalaman yang diharapkan adalah O(log N). Dengan begitu, bisa diharapkan bahwa setiap penambahan, pencarian, atau penghapusan dilakukan dalam O(log N)!

Berikut ini adalah implementasi treap yang separuh buatan saya, dan separuh lagi dari berbagai sumber. Implementasi ini juga melayani adanya duplikasi dan sudah teruji AC untuk mengerjakan soal-soal di ICPC Live Archive (Graph and Queries, dan Jewel, ICPC Regional Tianjin 2010). Anda bisa langsung mencoba juga, misalnya di SPOJ ORDERSET.

Update 19 Desember 2013: kode yang lebih pendek dan sampel eksekusi.
Update 21 Februari 2014: komentar yang lebih jelas pada kode.