Bagaimana Anda mengimplementasikan treap dengan split dan merge?

1. Masalah dan konteks

Pertahankan set terurut dinamis yang mendukung pencarian, penyisipan, penghapusan, dan pemisahan sesekali berdasarkan kunci yang diikuti oleh penggabungan. Implementasikan treap: setiap node memenuhi invarian binary-search-tree pada key dan invarian max-heap pada priority acak. Asumsikan kunci unik terlebih dahulu, lalu jelaskan penanganan duplikat.

2. Apa yang sedang diuji oleh pewawancara

• Menjelaskan apa yang disediakan oleh masing-masing invarian BST dan invarian heap.
• Menyusun insert dan erase dari split dan merge alih-alih hanya menghafal rotasi.
• Menyatakan bahwa O(log n) adalah nilai yang diharapkan (expected), dan bahwa kualitas keacakan serta tabrakan prioritas memengaruhi bentuk tree.
• Mempertahankan ukuran subtree atau agregat, dengan urutan pembaruan yang benar dan penanganan child kosong.

3. Pertanyaan untuk diklarifikasi terlebih dahulu

• Apakah kunci bersifat unik? Jika duplikat diizinkan, letakkan kunci yang sama secara konsisten di satu sisi atau gunakan (key, id) sebagai kunci komposit.
• Apakah prioritas disediakan oleh pemanggil atau dibuat secara internal? Pembuatan internal memerlukan sumber acak, kebijakan tabrakan, dan seed pengujian yang dapat direproduksi.
• Apakah split menempatkan kunci batas di sebelah kiri, atau memerlukan pemisahan yang strictly less-than? Hal ini mengubah kode penyisipan dan kueri rentang.
• Apakah kita memerlukan statistik urutan ke-k, jumlah rentang, atau urutan implisit (implicit sequence)? Setiap mutasi kemudian harus memperbarui metadata subtree.

4. Kerangka jawaban tiga puluh detik

“Saya mempertahankan urutan BST berdasarkan kunci dan urutan max-heap berdasarkan prioritas acak. Operasi intinya adalah split(T, key), yang mengembalikan kunci yang paling banyak sebesar batas dan kunci di atasnya, serta merge(L, R), yang mengasumsikan setiap kunci di L tidak lebih besar dari setiap kunci di R dan memilih root dengan prioritas lebih tinggi. Insert memisahkan di sekitar kunci baru dan menggabungkannya kembali; erase menggabungkan child dari target. Setiap return rekursif memperbarui ukuran. Tinggi dan operasi diharapkan bernilai O(log n), bukan worst-case, sehingga kode produksi memerlukan pengujian yang dapat direproduksi, pemantauan kedalaman, atau tree dengan batas deterministik.”

5. Penalaran langkah demi langkah

Pertama, tetapkan invarian. Untuk setiap node, kunci kiri tidak lebih besar dari kuncinya, kunci kanan lebih besar, dan prioritasnya setidaknya sebesar kedua prioritas child-nya. Artikel ini menggunakan aturan “kunci yang sama diletakkan di kiri”; (key, uniqueId) komposit adalah kebijakan jelas lainnya.

Kedua, implementasikan split. Jika kunci root paling banyak sebesar batas, root dan subtree kiri termasuk dalam hasil kiri, jadi lakukan rekursi ke child kanan. Jika tidak, lakukan rekursi ke child kiri untuk hasil kanan. Sambungkan kembali child yang dikembalikan dan perbarui ukuran. Hanya satu jalur root-ke-leaf yang dikunjungi.

Ketiga, implementasikan merge. Tangani tree kosong terlebih dahulu. Jika root kiri memiliki prioritas lebih tinggi, pertahankan sebagai root dan gabungkan child kanannya dengan tree kanan; jika tidak, pertahankan root kanan dan gabungkan tree kiri dengan child kirinya. Prasyarat bahwa setiap kunci kiri tidak lebih besar dari setiap kunci kanan menjaga urutan BST.

Keempat, susun operasi. Untuk insert, lakukan split(root, key) dan kemudian merge(merge(left, node), right). Untuk erase, ganti target dengan merge(node.left, node.right). Search turun berdasarkan kunci dan tidak memerlukan split. Jika ukuran disimpan, jalankan size = 1 + size(left) + size(right) setelah setiap operasi split, merge, insert, dan erase.

Kelima, diskusikan kompleksitas dan kegagalan. Prioritas acak membuat bentuknya sebanding dengan BST yang dibangun secara acak, memberikan operasi yang diharapkan bernilai O(log n); CP-Algorithms mendokumentasikan split, merge, penyisipan, dan penghapusan logaritmik yang diharapkan. Prioritas yang hampir monoton tetap dapat menciptakan tree O(n), jadi gunakan seed tetap dalam pengujian, pantau tinggi, atau pilih tree AVL atau red-black ketika batas worst-case diwajibkan.

6. Contoh jawaban berkualitas tinggi

“Pertama-tama saya akan menyepakati semantik kunci duplikat, lalu mengimplementasikan dua operasi primitif. split mengembalikan tree kiri dan kanan di sekitar batas, memisahkan satu child secara rekursif, dan menyambungkan kembali root. merge mengasumsikan semua kunci kiri tidak lebih besar dari kunci kanan dan memilih root dengan prioritas lebih tinggi. Insert memisahkan dan menempatkan node baru di antara hasilnya; erase menggabungkan child dari target. Memperbarui ukuran subtree juga memungkinkan pemilihan elemen ke-k. Prioritas acak memberikan tinggi yang diharapkan sebesar O(log n), bukan jaminan worst-case, jadi saya akan menguji dengan seed tetap di seluruh tree kosong, duplikat, dan jejak panjang, memantau kedalaman, dan memilih red-black tree ketika batas deterministik penting.”

7. Kesalahan umum

• Kesalahan → Hanya mempertahankan urutan BST → penyisipan terurut tetap membentuk linked list → pertahankan juga invarian heap prioritas.
• Kesalahan → Melakukan merge tanpa memeriksa rentang kunci → pencarian mengambil jalur yang salah → dokumentasikan bahwa kunci kiri tidak lebih besar dari kunci kanan.
• Kesalahan → Lupa memperbarui ukuran subtree setelah split → statistik ke-k dan rentang menjadi menyimpang → tarik metadata segera setelah menyambungkan kembali child.
• Kesalahan → Memperlakukan O(log n) yang diharapkan sebagai jaminan worst-case → prioritas yang merugikan (adversarial) dapat menciptakan tree yang dalam → pantau kedalaman atau gunakan tree AVL/red-black.
• Kesalahan → Kebijakan duplikat yang tidak konsisten di seluruh search, erase, dan split → kunci yang sama mendarat di subtree yang salah → gunakan kunci komposit atau satu aturan batas.

8. Pertanyaan lanjutan

Bagaimana Anda mendukung elemen terkecil ke-k?

Simpan ukuran subtree di setiap node. Bandingkan k dengan ukuran kiri saat menuruni tree; perbarui ukuran pada setiap operasi split, merge, penyisipan, dan erase, jika tidak kueri akan menjadi salah.

Bagaimana treap dapat merepresentasikan urutan implisit (implicit sequence)?

Jangan simpan kunci eksplisit. Tentukan posisi node dari ukuran subtree kirinya ditambah kontribusi leluhur. Pisahkan berdasarkan posisi dan gabungkan kembali untuk mendukung penyisipan, penghapusan, dan agregat rentang; flag malas (lazy flags) dapat menangani pembalikan atau penambahan rentang.

Kapan Anda akan menghindari treap?

Pilih AVL, red-black tree, atau indeks basis data ketika O(log n) kasus terburuk yang ketat, keacakan yang terkontrol, atau implementasi konkuren yang matang diperlukan. Treap mengorbankan jaminan tersebut demi kode yang pendek dan komposisi split/merge yang fleksibel.