Pertanyaan
Diberikan sebuah universe bilangan bulat tetap dengan kunci dari 0 hingga U-1, implementasikan van Emde Boas Tree yang mendukung insertion, deletion, membership, minimum, maximum, predecessor, dan successor. Jelaskan dekomposisi high dan low, struktur summary, penanganan cluster kosong, serta mengapa operasi membutuhkan O(log log U) alih-alih O(log U).
Hal yang sedang diuji oleh pewawancara
- Apakah Anda memahami bahwa vEB Tree mengasumsikan universe bilangan bulat tetap dan operasi bit, sehingga struktur ini tidak langsung menggantikan pohon perbandingan (comparison tree) untuk objek arbitrer.
- Apakah Anda dapat menghitung indeks cluster dan offset dengan benar serta menjaga summary tetap mengetahui cluster mana saja yang tidak kosong.
- Apakah Anda menangani pohon kosong, singleton, kunci batas, penghapusan nilai minimum, dan pembersihan setelah sebuah cluster menjadi kosong.
- Apakah Anda dapat menyatakan kompleksitas teoretis dan biaya ruang O(U), lalu menyebutkan kapan y-fast trie, sorted array, atau balanced tree biasa lebih disukai.
Jawaban model
Misalkan U adalah pangkat dua dengan lebar bit w. Setiap simpul (node) vEB memiliki sub-universe berukuran u dan membagi sebuah kunci menjadi indeks cluster bagian atas (high) dan offset bagian bawah (low). Dalam definisi rekursif yang biasa, kedua bagian menggunakan sekitar setengah dari bit yang ada, sehingga sebuah simpul memiliki sekitar sqrt(u) cluster. Setiap cluster merupakan vEB lain berukuran sqrt(u), dan sebuah summary berukuran sqrt(u) mencatat cluster mana saja yang tidak kosong.
Simpul tersebut juga menyimpan min dan max sehingga operasi-operasi umum tidak perlu melakukan rekursi hingga ke daun (leaf). Menyisipkan elemen pertama akan menetapkan kedua nilai tersebut; penyisipan berikutnya menukar kunci yang lebih kecil ke dalam min dan menyisipkan nilai min yang lama ke dalam clusternya. Penghapusan harus menangani penghapusan min atau max, menemukan cluster tidak kosong berikutnya melalui summary, dan menghapus cluster dari summary saat cluster tersebut menjadi kosong.
Relasi rekurensinya adalah T(u)=T(sqrt(u))+O(1). Operasi akar kuadrat yang berulang membagi dua eksponen pada setiap tingkat, sehingga kedalamannya adalah O(log log U). Dengan tata letak naif (naive layout), pointer cluster dan summary di seluruh simpul rekursif menggunakan ruang O(U). Tata letak renggang (sparse layouts) mengurangi konstanta tetapi tidak dengan sendirinya menghilangkan ketergantungan pada ukuran universe.
Sketsa implementasi
Pseudokode ini menggunakan high, low, dan index untuk dekomposisi dan rekombinasi, tanpa menyertakan pool memori dan validasi argumen.
high(x, bits) = x >> ceil(bits / 2)
low(x, bits) = x & ((1 << floor(bits / 2)) - 1)
index(h, l, bits) = (h << floor(bits / 2)) | l
insert(v, x):
if v.min is empty:
v.min = x; v.max = x; return
if x < v.min:
swap(x, v.min)
if v.bits > 1:
h = high(x, v.bits); l = low(x, v.bits)
if v.cluster[h].min is empty:
insert(v.summary, h)
insert(v.cluster[h], l)
if x > v.max:
v.max = x
successor(v, x):
if v.min is empty or x >= v.max: return empty
if v.bits == 1:
return v.max if v.max > x else empty
if x < v.min: return v.min
h = high(x, v.bits); l = low(x, v.bits)
c = v.cluster[h]
if c is not empty and l < c.max:
return index(h, successor(c, l), v.bits)
next_h = successor(v.summary, h)
if next_h is empty: return empty
return index(next_h, v.cluster[next_h].min, v.bits)Implementasi penghapusan yang sesungguhnya harus mempertahankan aturan cluster kosong yang simetris. Simpul daun dapat menggunakan bitmap kecil atau dua nilai alih-alih mengalokasikan objek secara rekursif. Tetapkan lebar bit terlebih dahulu, kemudian bandingkan urutan operasi acak terhadap ordered set agar hasil predecessor dan successor cocok.
Jebakan umum
- Memperlakukan U sebagai jumlah elemen n dan mengklaim setiap operasi adalah O(log log n). Parameternya adalah ukuran universe U.
- Mengabaikan pembulatan ketika U bukan merupakan pangkat dua, sehingga high, low, dan index tidak lagi menjadi operasi invers.
- Mengimplementasikan membership dan minimum tetapi tidak pernah menghapus cluster kosong dari summary setelah deletion.
- Mengasumsikan vEB selalu lebih cepat daripada red-black tree sambil mengabaikan ruang O(U), lokalitas cache, dan distribusi kunci yang sebenarnya.
- Memberikan struktur rekursif yang sama pada summary tanpa menyatakan batas universe dan representasi kosongnya.
Pertukaran kompleksitas
Untuk bilangan bulat machine-word, universe yang diketahui, dan beban kerja yang berpusat pada predecessor serta successor, O(log log U) secara teoretis sangat menarik. Jika U mendekati rentang word tetapi himpunannya renggang (sparse), tata letak naif akan membuang-buang memori. x-fast atau y-fast trie membuat ruang lebih bergantung pada n, dengan kompensasi berupa hashing, keacakan (randomness), atau kompleksitas implementasi.
Balanced tree biasa menyediakan operasi O(log n), ruang O(n), dan semantik iterator yang lebih sederhana. Sorted array cocok untuk himpunan statis dan kueri batch. Dalam wawancara, pilihlah berdasarkan domain kunci, rasio pembaruan, anggaran memori, dan kemudahan pemeliharaan alih-alih hanya melaporkan batas asimtotik tercepat.
Mulailah dengan U bernilai 2, 4, dan 16, ditambah universe yang bukan pangkat dua, untuk menguji dekomposisi batas. Buat urutan insertion, deletion, dan query acak lalu bandingkan minimum, maksimum, membership, predecessor, dan successor dengan ordered set bawaan bahasa pemrograman. Cakup juga penyisipan duplikat, penghapusan kunci yang tidak ada, penghapusan kunci terakhir, dan penghapusan minimum atau maksimum secara berulang.
Referensi
- Kuliah van Emde Boas Trees dari MIT OpenCourseWare: cluster rekursif, summary, dan penurunan operasi.
- Carnegie Mellon Graduate Algorithms Lecture 7: analisis rekurensi O(log log U) dan detail implementasi.
- Survei pencarian predecessor dari Springer: karya asli van Emde Boas dan konteks masalah predecessor.
Pertanyaan lanjutan
Mengapa struktur summary diperlukan?
Ketika cluster saat ini tidak memiliki elemen yang lebih besar, pohon harus dengan cepat menemukan cluster tidak kosong berikutnya. Summary mengubah persoalan "cluster mana saja yang tidak kosong" menjadi masalah predecessor atau successor lainnya alih-alih memindai cluster secara linear.
Mengapa min dan max dapat berada di luar cluster?
Menyimpan min dan max secara terpisah membuat operasi pada pohon kosong dan singleton berjalan dalam waktu konstan serta mengurangi rekursi. Insertion menukar nilai yang lebih kecil ke dalam min; deletion menemukan nilai ekstrem pengganti melalui summary dan memulihkan invarian.
Bagaimana jika U bukan merupakan pangkat dua?
Bulatkan ke atas ke universe berpangkat dua yang mencakup setiap kunci yang valid dan tolak kunci di luar rentang asli. Alternatifnya, implementasikan batas cluster yang dibulatkan, tetapi buktikan bahwa high, low, dan index tetap merupakan operasi invers dan kompleksitasnya tetap berlaku.
Bagaimana cara mengurangi ruang O(U)?
Gunakan sparse cluster, x-fast trie, atau y-fast trie. Jelaskan collision hash, keacakan, semantik iterator, dan faktor konstanta alih-alih hanya membandingkan notasi big-O.
Kapan Anda harus menghindari vEB?
Gunakan balanced tree atau B-tree ketika domain kunci sangat besar dan renggang, universe tidak dapat ditentukan secara tetap, pembanding umum (general comparator) diperlukan, atau perilaku iterator yang matang lebih penting daripada batas teoretis.