Lebih cepat bergabung dengan struktur data seperti treap dengan ukuran kira-kira sama

Diberi dua pohon AVL dan dan nilai sedemikian rupa sehingga , mudah untuk membangun pohon AVL baru yang berisi dan nilai-nilai di T_1 dan T_2 dalam waktu O (1+ | h (T_1) - h (T_2) |) , di mana h (T) menunjukkan ketinggian pohon T (selama pohon menyimpan ketinggiannya).T 2 t r ∀ x ∈ T 1 , ∀ y ∈ T 2 , x < t r < y t r T 1 T 2 O ( 1 + | h ( T 1 ) - h ( T 2 ) | ) h ( T ) $T_1$$T_2$$t_r$$\forall x \in T_1, \forall y \in T_2, x < t_r < y$$t_r$$T_1$$T_2$$O(1+|h(T_1) - h(T_2)|)$$h(T)$$T$

Ini juga mungkin untuk pohon merah-hitam, dan saya menganggap banyak jenis pohon seimbang juga.

Apakah ini mungkin untuk struktur data treap atau suka treap? Bagaimana jika kita meninggalkan $t_r$ ?

Makalah treaps di Algorithmica menunjukkan bagaimana melakukan ini dalam waktu yang diharapkan . Jika ada cara untuk melakukan O (1) diharapkan bergabung di treaps (atau struktur data treap-like) dengan ukuran yang kira-kira sama (atau prioritas root), saya pikir mungkin untuk menggunakan trik Kaplan & Tarjan dari bootstrap duri untuk membuat treaps (atau struktur data seperti treap) dengan dua-logaritmik bergabung.$O(\min(h(T_1),h(T_2)))$

Tidak, itu tidak mungkin dilakukan dengan Treaps biasa jika prioritasnya acak.

Klaim tepat yang akan saya buat adalah bahwa untuk melakukan penggabungan pada dua treaps yang berukuran sama dengan prioritas acak memerlukan pembaruan pointer dengan harapan.$\Theta(\log n)$

Berikut ini sketsa bukti kasar:

Pertimbangkan jumlah petunjuk yang harus Anda ubah dengan harapan untuk melakukan operasi. Lebih mudah membuktikan ikatan jika kita tidak memasukkan t r tetapi hanya menggabungkan T 1 dan T 2 . Pertimbangkan tulang belakang kanan S 1 dari T 1 dan tulang belakang kiri S 2 dari T 2 . Warnai elemen S 1 merah dan S 2 biru. Pesan S 1 ∪ S $\Theta(\log n)$$t_r$$T_1$$T_2$$S_1$$T_1$$S_2$$T_2$$S_1$$S_2$$S_1 \cup S_2$berdasarkan prioritas. Kita harus mengubah pointer setiap kali warna berubah dalam urutan ini. Karena kedua duri memiliki ukuran dengan probabilitas tinggi, dan prioritasnya acak, tidak terlalu sulit untuk melihat bahwa # perubahan warna dalam urutan juga Θ ( log n ) . Jadi kita perlu memperbarui Θ ( log n ) pointer untuk gabungan (tanpa menambahkan t r ).$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$$t_r$

Sekarang, menambahkan saat melakukan penggabungan tidak benar-benar membantu banyak. Jumlah perubahan pointer dalam hal ini dapat dibatasi lebih rendah sebagai berikut: Urutan S 1 ∪ S 2 ∪ { t r } dengan prioritas. Hapus segala sesuatu kurang dari t r dalam urutan. Kemudian # perubahan warna dalam urutan yang dihasilkan adalah batas bawah kita. Karena t r memiliki prioritas acak, ketinggian yang diharapkan dari subtree yang berakar padanya dalam treap akhir adalah O ( 1 ) , sehingga hanya memiliki O ( 1 ) node S $t_r$$S_1 \cup S_2 \cup \{t_r\}$$t_r$$t_r$$O(1)$$O(1)$ dengan prioritas lebih rendah dari yang diharapkan, jadi kami hanya kehilangan O ( 1 ) perubahan pointer di batas bawah kami saat menambahkan t r .$S_1 \cup S_2$$O(1)$$t_r$

Sekarang, yang mengatakan, mungkin ada cara untuk mendapatkan struktur data "seperti treap" yang memungkinkan penggabungan waktu yang konstan.

Pembaruan: lihat di bawah untuk pembaruan tentang kesalahan operasi gabungan ini

Berikut ini adalah sketsa kasar dari solusi yang mungkin:

Saya pikir saya mungkin punya solusi untuk masalah ini menggunakan tipe B + -tree-seimbang acak. Seperti pohon treaps, pohon-pohon ini memiliki representasi yang unik. Tidak seperti treaps, mereka menyimpan beberapa kunci beberapa kali. Dimungkinkan untuk memperbaikinya dengan menggunakan trik dari Bent Trees et al "Biased Search Trees" untuk menyimpan setiap kunci hanya di level tertinggi (yaitu, paling dekat dengan root) di mana ia muncul)

Pohon untuk serangkaian nilai unik yang dibuat dibuat dengan pertama-tama mengaitkan setiap nilai dengan aliran bit, mirip dengan cara setiap nilai dalam treap dikaitkan dengan prioritas. Setiap node di pohon berisi kunci dan bit stream. Selain itu, simpul non-daun mengandung angka alami yang menunjukkan tinggi pohon yang berakar pada simpul itu. Node internal dapat memiliki jumlah anak yang tidak nol. Seperti B + -trees, setiap jalur yang tidak memotong sendiri dari akar ke daun memiliki panjang yang sama.

Setiap simpul internal berisi (seperti dalam B + -trees) kunci k terbesar dari daun turunannya. Masing-masing juga berisi bilangan alami i yang menunjukkan ketinggian pohon yang berakar pada v , dan aliran bit yang terkait dengan k dari bit i + 1 ke depan. Jika setiap kunci dalam pohon yang di-root pada v memiliki bit pertama yang sama dalam bit stream-nya, setiap anak v adalah daun dan i adalah 1 . Kalau tidak, anak-anak v adalah node internal yang semuanya memiliki bit ke- i yang sama dalam bit stream yang terkait dengan kunci mereka.$v$$k$$i$$v$$k$$i+1$$v$$v$$i$$1$$v$$i$

Untuk membuat pohon dari daftar kunci yang diurutkan dengan aliran bit terkait, pertama kumpulkan kunci menjadi kelompok yang berdekatan berdasarkan bit pertama di aliran mereka. Untuk masing-masing grup ini, buat induk dengan kunci dan bit stream dari kunci terbesar dalam grup, tetapi hilangkan bit pertama dari stream. Sekarang lakukan prosedur pengelompokan yang sama pada orang tua baru untuk membuat kakek-nenek. Lanjutkan sampai hanya satu simpul yang tersisa; ini adalah akar pohon.

Daftar kunci berikut dan (awal) bit stream diwakili oleh pohon di bawahnya. Di awalan bit stream, a '.' berarti sedikit pun. Artinya, setiap bit stream untuk kunci A dengan 0 di tempat pertama dengan menghasilkan pohon yang sama dengan yang lain, dengan asumsi tidak ada bit stream kunci lain yang berbeda.

A 0...
B 00..
C 10..
D 0...
E 0011
F 1...
G 110.
H 0001


        ____H____
       /         \
      E           H
      |          / \
    __E__       G   H
   /  |  \      |   |
  B   C   E     G   H
 / \  |  / \   / \  |
A   B C D   E F   G H

Setiap anak dari simpul internal tertentu memiliki bit yang sama di tempat pertama dari bit stream-nya. Ini disebut "warna" dari induk - 0 berwarna merah, 1 berwarna hijau. Anak memiliki "rasa" tergantung pada bit pertama dari aliran bitnya - 0 adalah ceri, 1 adalah mint. Daun memiliki rasa, tetapi tidak berwarna. Menurut definisi, simpul ceri tidak dapat memiliki induk hijau, dan simpul mint tidak dapat memiliki induk merah.

$n$$2^{1-n}$ ${n-1}\choose{i-1}$$(n+1)/2$$n \geq 2$$\leq \frac{3}{4}n$$O(\lg n)$

Untuk bergabung dengan dua pohon dengan ketinggian yang sama, periksa terlebih dahulu untuk melihat apakah akarnya memiliki warna yang sama. Jika demikian, putuskan dari root kiri anak paling kanan dan dari root kanan anak paling kiri, kemudian secara rekursif bergabung dengan dua pohon ini. Hasilnya akan menjadi pohon dengan ketinggian yang sama atau lebih tinggi karena pohon memiliki rasa yang sama (lihat di bawah). Jika hasil rekursif bergabung dengan dua pohon memiliki ketinggian yang sama dengan dua anak yang putus, menjadikannya anak tengah dari akar dengan sisa anak-anak dari akar kiri sebelum dan sisa anak-anak dari akar kanan setelahnya. Jika lebih tinggi dari 1, jadikan anak-anak sebagai anak tengah dari akar dengan sisa anak dari akar kiri sebelum dan sisa anak-anak dari akar kanan setelahnya. Jika akar memiliki warna yang berbeda, periksa untuk melihat apakah mereka memiliki rasa yang sama. Jika mereka melakukannya, beri mereka induk baru dengan kunci dan bit stream dari root kanan, hilangkan bit pertamanya. Jika tidak, berikan masing-masing root induk baru dengan kunci dan bit stream dari root lama (eliding masing-masing bit pertama), kemudian secara rekursif bergabung dengan pohon-pohon itu.

$1/2$$1/2$$O(1)$$1/4$, dan panggilan rekursif berikutnya selalu pada pohon dengan warna yang berbeda, sehingga analisis yang sama berlaku.

$1/2$$O(1)$

$O(1)$

a 01110
b 110..
c 10...
d 00000

Pohon yang dibuat dengan [a,b]tinggi 2, pohon yang dibuat dengan [c,d]tinggi 2, dan pohon yang dibuat dengan joinEqual (tree [a,b]) (tree [c,d])tinggi 3. Namun, pohon yang dibuat [a,b,c,d]memiliki tinggi 5.

Berikut adalah kode yang saya gunakan untuk menemukan kesalahan ini .