Pohon biner penyeimbang mandiri mana yang akan Anda rekomendasikan?

Saya belajar Haskell dan sebagai latihan saya membuat pohon biner. Setelah membuat pohon biner biasa, saya ingin mengadaptasinya menjadi penyeimbang diri. Begitu:

• Mana yang paling efisien?
• Mana yang paling mudah diterapkan?
• Mana yang paling sering digunakan?

Tetapi yang terpenting, yang Anda rekomendasikan?

Saya menganggap ini milik di sini karena itu terbuka untuk diperdebatkan.

Saya akan merekomendasikan Anda mulai dengan pohon Merah-Hitam , atau pohon AVL .

Pohon merah-hitam lebih cepat untuk dimasukkan, tetapi pohon AVL memiliki sedikit keunggulan untuk pencarian. Pohon AVL mungkin sedikit lebih mudah diimplementasikan, tetapi tidak berdasarkan pengalaman saya sendiri.

Pohon AVL memastikan bahwa pohon seimbang setelah setiap memasukkan atau menghapus (tidak ada sub-pohon memiliki faktor keseimbangan lebih besar dari 1 / -1, sedangkan pohon Merah-hitam memastikan bahwa pohon itu seimbang setiap saat.

Saya akan mempertimbangkan alternatif jika Anda baik-baik saja dengan struktur data acak : Abaikan Daftar .

Dari sudut pandang tingkat tinggi, ini adalah struktur pohon, kecuali bahwa itu tidak diimplementasikan sebagai pohon tetapi sebagai daftar dengan banyak lapisan tautan.

Anda akan mendapatkan O (log N) penyisipan / pencarian / penghapusan, dan Anda tidak harus berurusan dengan semua kasus penyeimbangan ulang yang rumit.

Saya tidak pernah mempertimbangkan untuk mengimplementasikannya dalam Bahasa Fungsional, dan halaman wikipedia tidak menunjukkan apa pun, jadi mungkin tidak mudah (wrt to immutability)

Jika Anda ingin struktur yang relatif mudah untuk memulai (baik pohon AVL dan pohon merah-hitam adalah fiddly), satu opsi adalah treap - dinamai sebagai kombinasi "tree" dan "heap".

Setiap node mendapat nilai "prioritas", sering secara acak ditetapkan ketika node dibuat. Node diposisikan di pohon sehingga urutan kunci dihormati, dan sehingga urutan nilai prioritas seperti heap dihormati. Pemesanan mirip tumpukan berarti bahwa kedua anak dari orang tua memiliki prioritas lebih rendah daripada orang tua.

EDIT dihapus "di dalam nilai-nilai kunci" di atas - prioritas dan urutan kunci berlaku bersama, sehingga prioritas penting bahkan untuk kunci unik.

Kombinasi yang menarik. Jika kunci unik dan prioritas unik, ada struktur pohon unik untuk setiap set node. Meski begitu, menyisipkan dan menghapus itu efisien. Sebenarnya, pohon dapat tidak seimbang ke titik di mana ia secara efektif merupakan daftar yang ditautkan, tetapi ini sangat tidak mungkin (seperti dengan pohon biner standar), termasuk untuk kasus normal seperti kunci yang dimasukkan secara berurutan (tidak seperti pohon biner standar).

Mana yang paling efisien?

Tidak jelas dan sulit dijawab. Kompleksitas komputasi semuanya terdefinisi dengan baik. Jika itu yang Anda maksud dengan efisiensi, tidak ada perdebatan nyata. Memang, semua algoritma yang baik datang dengan bukti dan faktor kompleksitas.

Jika Anda bermaksud "waktu berjalan" atau "penggunaan memori" maka Anda harus membandingkan implementasi yang sebenarnya. Kemudian bahasa, run-time, OS dan faktor-faktor lain ikut bermain, membuat pertanyaan sulit dijawab.

Mana yang paling mudah diterapkan?

Tidak jelas dan sulit dijawab. Beberapa algoritma mungkin terlihat rumit bagi Anda, tetapi sepele bagi saya.

Mana yang paling sering digunakan?

Tidak jelas dan sulit dijawab. Pertama ada "oleh siapa?" bagian dari ini? Hanya Haskell? Bagaimana dengan C atau C ++? Kedua, ada masalah perangkat lunak berpemilik di mana kami tidak memiliki akses ke sumber untuk melakukan survei.

Tetapi yang terpenting, yang Anda rekomendasikan?

Saya menganggap ini milik di sini karena itu terbuka untuk diperdebatkan.

Benar. Karena kriteria Anda yang lain tidak terlalu membantu, ini yang akan Anda dapatkan.

Anda bisa mendapatkan sumber untuk sejumlah besar algoritma pohon. Jika Anda ingin mempelajari sesuatu, Anda bisa menerapkan setiap yang Anda bisa temukan. Daripada meminta "rekomendasi", kumpulkan saja setiap algoritma yang dapat Anda temukan.

Berikut daftarnya:

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Ada enam yang populer didefinisikan. Mulailah dengan itu.

Jika Anda tertarik pada pohon Splay, ada versi yang lebih sederhana dari yang saya yakini pertama kali dijelaskan dalam makalah oleh Allen dan Munroe. Itu tidak memiliki jaminan kinerja yang sama, tetapi menghindari komplikasi dalam berurusan dengan penyeimbangan kembali "zig-zig" vs "zig-zag".

Pada dasarnya, ketika mencari (termasuk mencari titik atau simpul untuk dihapus), simpul yang Anda temukan akan diputar langsung ke arah root, dari bawah ke atas (mis. Saat fungsi pencarian rekursif keluar). Pada setiap langkah, Anda memilih satu putaran kiri atau kanan tergantung pada apakah anak yang ingin Anda tarik ke atas root adalah anak kanan atau anak kiri (jika saya ingat arah rotasi saya dengan benar, itu masing-masing).

Seperti pohon Splay, idenya adalah item yang baru diakses selalu dekat dengan akar pohon, jadi cepat diakses lagi. Menjadi lebih sederhana, pohon-pohon Allen-Munroe rotate-to-root (apa yang saya sebut - tidak tahu nama resmi) bisa lebih cepat, tetapi mereka tidak memiliki jaminan kinerja diamortisasi yang sama.

Satu hal - karena struktur data ini menurut definisi bermutasi bahkan untuk operasi pencarian, mungkin perlu diimplementasikan secara monadik. TKI itu mungkin tidak cocok untuk pemrograman fungsional.

Pohon seimbang yang sangat sederhana adalah pohon AA . Itu invarian lebih sederhana dan dengan demikian lebih mudah diterapkan. Karena kesederhanaannya, kinerjanya masih bagus.

Sebagai latihan lanjutan, Anda dapat mencoba menggunakan GADT untuk menerapkan salah satu varian pohon seimbang yang invariannya ditegakkan oleh tipe sistem tipe.