Saya mencari algoritme untuk menggabungkan dua pohon pencarian biner dengan ukuran dan jangkauan yang berubah-ubah. Cara yang jelas saya akan menerapkan ini adalah untuk menemukan seluruh sub pohon yang jangkauannya dapat masuk ke dalam simpul eksternal yang berubah-ubah di pohon lain. Namun, kasus terburuk berjalan waktu untuk jenis algoritma tampaknya berada di urutan O(n+m)
di mana n
dan m
adalah ukuran masing-masing pohon masing-masing.
Namun, saya telah diberitahu bahwa ini bisa dilakukan di O(h)
, di mana h
ketinggian pohon dengan ketinggian lebih besar. Dan saya benar-benar bingung tentang bagaimana ini mungkin. Saya sudah mencoba bereksperimen dengan memutar satu pohon terlebih dahulu, tetapi memutar pohon menjadi tulang belakang sudah O (h).
O(log n)
dengan fungsi simpul gerak yang sederhana?n
. Hanya pohon biner penuh atau lengkap memiliki tinggi logaritmik untuk jumlah total node mereka.Jawaban:
Dalam ArXiv: 1002.4248 , John Iacono dan Özgür Özkan menggambarkan algoritma yang relatif sederhana untuk menggabungkan dua pohon pencarian biner dalam waktu diamortisasi ; analisis adalah bagian yang sulit. [ Pembaruan: Seperti yang diamati Joe dengan benar dalam jawabannya, algoritma ini disebabkan oleh Brown dan Tarjan.] Mereka juga menggambarkan struktur data kamus yang lebih rumit, berdasarkan daftar lompatan yang bias, yang mendukung penggabungan dalam waktu diamortisasi O ( log n ) .O(log2n) O(logn)
Di sisi lain, ikatan kasus terburuk dari tidak mungkin. Pertimbangkan dua pohon pencarian biner dengan n node, satu menyimpan bilangan bulat genap antara 2 dan 2 n , yang lain menyimpan bilangan bulat ganjil antara 1 dan 2 n - 1 . Menggabungkan dua pohon menciptakan pohon pencarian biner baru yang menyimpan semua bilangan bulat antara 1 dan 2 n . Dalam pohon seperti itu, sebagian kecil dari node memiliki paritas yang berbeda dari orang tua mereka. (Bukti: Induk daun aneh harus genap.) Dengan demikian, menggabungkan pohon genap dan aneh perlu diubahO(logn) n 2 2n 1 2n−1 1 2n petunjuk.Ω(n)
sumber
Anda dapat menemukan referensi ini bermanfaat: Brown dan Tarjan, Algoritma Penggabungan Cepat , di mana penulis menunjukkan cara menggabungkan pohon biner seimbang (AVL) di yang optimal (untuk algoritma berbasis perbandingan). m dan n adalah panjang dari daftar yang disortir yang diwakili oleh pohon pencarian biner, dan diasumsikan bahwa m ≥ n .O(nlogmn) m n m≥n
Anda juga dapat melihat diskusi tentang berbagai teknik untuk menggabungkan set yang dipesan pada bagian 11.5 dari makalah ini pada pohon pencarian jari
sumber
Anda dapat menggabungkan pohon dalam waktu kasus terburukO(1) sambil tetap mendukung: masukkan, hapus dan cari di .O(log n)
Brodal, Gerth Stølting, Christos Makris, dan Kostas Tsichlas. 'Fungsional Terburuk dengan Kasus Terbukti, Waktu Konstan Daftar Diurutkan' . Dalam Prosiding Konferensi ke-14 tentang Simposium Tahunan Eropa - Volume 14, 172–183. ESA'06. London, Inggris, Inggris: Springer-Verlag, 2006. [ PDF ]
sumber