Berpisah di pohon AVL dengan kompleksitas

Bisakah operasi pemisahan diterapkan untuk pohon AVL dengan kompleksitas $O(\log n)$? Saya tertarik pada tautan ke artikel atau informasi spesifik tentang subjek ini.

Operasi pembagian membagi pohon AVL menjadi dua pohon AVL yang diturunkan, berdasarkan kunci. Salah satu pohon yang diturunkan harus berisi semua simpul di mana semua kunci kurang dari kunci asli, dan yang kedua sisanya.

Saya tahu ini bisa dilakukan di $O(\log^2 n)$waktu. Berikut tautan ke implementasi dengan kompleksitas$O(\log^2 n)$: https://code.google.com/p/self-balancing-avl-tree/

Saya juga tahu cara menggabungkan dua pohon AVL, sehingga kunci dari satu pohon semuanya lebih kecil dari kunci yang lain, di $O(\log n)$waktu. Inilah implementasi dengan kompleksitas$O(\log n)$:

def Merge(l, r) {
    if (!l || !r) 
        return l ? l : r;
    if (l->h <= r->h)
        r->l = Merge(l, r->l), Rebalance(r);
    else
        l->r = Merge(l->r, r), Rebalance(l);
}

Ya, ini mungkin.

Anda dapat membacanya di Ramzi Fadel dan Kim Vagn Jakobsen "Struktur data dan algoritma dalam memori dua tingkat", bagian 3.1.6 , (mirror) atau di perpustakaan standar OCaml, di fungsi "split".

Salah satu wawasan utama adalah bahwa fungsi gabungan yang Anda sebutkan adalah, dengan akuntansi yang lebih hati-hati, $O(h_1 - h_2)$dimana $h_1$ adalah ketinggian pohon yang lebih tinggi dan $h_2$adalah ketinggian pohon yang lebih pendek. Dengan demikian, menggabungkan daftar pohon yang turun atau naik hanya membutuhkan biaya tinggi$O(h_{\max} - h_{\min})$, sejak penjumlahan teleskop .

Mari kita mendefinisikan fungsi split(T,v)yang mengambil pohon, Tdan nilai untuk dipecah pada v,. Misalkan setiap simpul pohon menyimpan anak kirinya dan anak kanan di samping nilai pada simpul itu. Gunakan algoritma berikut:

1. Pertama kita periksa untuk melihat apakah pohon input hanya daun atau tidak.

2. Jika Tbukan daun, bandingkan nilai simpul akarnya v'dengan v.

3. Jika v' < vkemudian secara rekursif panggilan split pada subtree kiri. Simpan nilai-nilai panggilan rekursif sebagai L'(pohon kiri kembali), R'(pohon kanan kembali), dan r(jenis opsi ditunjukkan jika nilai vditemukan atau tidak). Bangun pohon kanan baru newR = Node(R',v',R),, dan kembali (L',r,newR).

4. Lain jika v' > vkemudian secara rekursif panggilan split pada subtree kanan. Simpan nilai-nilai panggilan rekursif sebagai L'(pohon kiri kembali), R'(pohon kanan kembali), dan r(jenis opsi ditunjukkan jika nilai vditemukan atau tidak). Bangun pohon kiri baru newL = Node(L',v',L),, dan kembali (newL,r,R').

5. Jika tidak v' = v, kembalilah L, SOME(v), R.

6. Jika Tadalah daun, kita harus telah mencapai akar pohon tanpa menemukan nilai input v untuk dibelah. Kembali bahwa Anda tidak dapat menemukan daun dengan melewati kembali NONE.

Mengapa ini logaritmik? Yah, paling banyak kamu hanya melintasi satu jalur pohon ke daun. Kita dapat dengan mudah merekonstruksi node dalam waktu yang konstan karena kita hanya menetapkan ulang$O(\log n)$ referensi (dalam bahasa imperatif) atau penugasan kembali $O(\log n)$ nilai-nilai yang membutuhkan waktu konstan untuk menghasilkan (dalam bahasa fungsional).

Berikut kode yang sesuai untuk algoritme. Itu ditulis dalam SML, tetapi saya akan bersedia untuk menjelaskan apa artinya dalam komentar.

fun split(T,v) = case T of Leaf => (Leaf, NONE, Leaf) | Node(L,v,R) => case compare(v, v') of LESS => let val (L',r,R') = split(L,k) in (L',r,Node(R',r,R)) end | GREATER => let val (L',r,R') = split(R,k) in (Node(L',v',L),r,R') end | EQUAL => (L, SOME(v), R)

Lihat dokumen ini untuk lebih jelasnya. Ini memberikan penjelasan yang lebih menyeluruh tentang hal di atas.