Kapan Memilih RB Tree, B-Tree atau AVL Tree?

Sebagai seorang programmer, kapan saya harus mempertimbangkan untuk menggunakan pohon RB, pohon B atau pohon AVL? Apa poin-poin penting yang perlu dipertimbangkan sebelum memutuskan pilihan?

Bisakah seseorang menjelaskan dengan skenario untuk setiap struktur pohon mengapa itu dipilih daripada yang lain dengan mengacu pada poin-poin utama?

Ambil ini dengan sedikit garam:

B-tree saat Anda mengelola lebih dari ribuan item dan Anda mem-pagingnya dari disk atau media penyimpanan lambat.

RB pohon saat Anda cukup sering melakukan penyisipan, penghapusan, dan pengambilan di pohon.

Pohon AVL saat penyisipan dan penghapusan Anda jarang terjadi dibandingkan pengambilan Anda.

Menurut saya, pohon B + adalah struktur data container yang dipesan untuk keperluan umum yang baik, bahkan dalam memori utama. Bahkan ketika memori virtual tidak menjadi masalah, keramahan cache sering terjadi, dan pohon B + sangat baik untuk akses berurutan - kinerja asimtotik yang sama seperti daftar tertaut, tetapi dengan keramahan cache yang mirip dengan array sederhana. Semua ini dan O (log n) mencari, menyisipkan dan menghapus.

Pohon B + memang memiliki masalah - seperti item bergerak di dalam node saat Anda melakukan penyisipan / penghapusan, membuat pointer ke item tersebut tidak valid. Saya memiliki pustaka penampung yang melakukan "pemeliharaan kursor" - kursor menempel pada simpul daun yang saat ini mereka rujuk dalam daftar tertaut, sehingga mereka dapat diperbaiki atau dibatalkan secara otomatis. Karena jarang ada lebih dari satu atau dua kursor, ini berfungsi dengan baik - tetapi ini merupakan pekerjaan tambahan yang semuanya sama.

Hal lain adalah bahwa pohon B + pada dasarnya hanya itu. Saya kira Anda dapat melepas atau membuat ulang simpul non-daun tergantung pada apakah Anda membutuhkannya atau tidak, tetapi dengan simpul pohon biner Anda mendapatkan lebih banyak fleksibilitas. Pohon biner dapat diubah menjadi daftar tertaut dan kembali tanpa menyalin node - Anda cukup mengubah penunjuk lalu ingat bahwa Anda memperlakukannya sebagai struktur data yang berbeda sekarang. Antara lain, ini berarti Anda mendapatkan O (n) penggabungan pohon yang cukup mudah - ubah kedua pohon menjadi daftar, gabungkan, lalu ubah kembali menjadi pohon.

Namun hal lainnya adalah alokasi memori dan pembebasan. Dalam pohon biner, ini dapat dipisahkan dari algoritme - pengguna dapat membuat node kemudian memanggil algoritme penyisipan, dan menghapus dapat mengekstrak node (melepaskannya dari pohon, tetapi tidak membebaskan memori). Di pohon B atau pohon B +, yang jelas tidak berfungsi - data akan hidup dalam simpul multi-item. Menulis metode penyisipan yang "merencanakan" operasi tanpa memodifikasi node sampai mereka tahu berapa banyak node baru yang dibutuhkan dan bahwa mereka dapat dialokasikan merupakan sebuah tantangan.

Merah hitam vs. AVL? Saya tidak yakin itu membuat perbedaan besar. Perpustakaan saya memiliki kelas "alat" berbasis kebijakan untuk memanipulasi node, dengan metode untuk daftar tertaut ganda, pohon biner sederhana, pohon bentang, pohon merah-hitam, dan hierarki, termasuk berbagai konversi. Beberapa dari metode tersebut hanya diterapkan karena saya bosan pada satu waktu atau lainnya. Saya bahkan tidak yakin saya telah menguji metode treap. Alasan saya memilih pohon merah-hitam daripada AVL adalah karena saya secara pribadi memahami algoritme dengan lebih baik - yang tidak berarti algoritme tersebut lebih sederhana, hanya kebetulan sejarah saja yang lebih saya kenal.

Satu hal lagi - Saya awalnya hanya mengembangkan wadah pohon B + saya sebagai percobaan. Ini adalah salah satu eksperimen yang tidak pernah berakhir, tetapi ini bukan sesuatu yang saya dorong untuk diulangi oleh orang lain. Jika yang Anda butuhkan hanyalah container terurut, jawaban terbaik adalah menggunakan container yang disediakan library Anda - mis. Std :: map dll di C ++. Perpustakaan saya berkembang selama bertahun-tahun, butuh waktu cukup lama untuk membuatnya stabil, dan saya baru saja menemukan itu secara teknis non-portabel (tergantung pada sedikit perilaku offset WRT yang tidak ditentukan).

Dalam memori B-Tree memiliki keunggulan ketika jumlah item lebih dari 32000 ... Lihat speedtest.pdf dari stx-btree .

Saat memilih struktur data, Anda memperdagangkan faktor-faktor seperti

• kecepatan pengambilan v kecepatan update
• seberapa baik struktur mengatasi operasi kasus terburuk, misalnya penyisipan catatan yang datang dalam urutan yang diurutkan
• ruang terbuang

Saya akan mulai dengan membaca artikel Wikipedia yang direferensikan oleh Robert Harvey.

Secara pragmatis, ketika bekerja dalam bahasa seperti Java, programmer rata-rata cenderung menggunakan kelas koleksi yang disediakan. Jika dalam aktivitas penyetelan kinerja ditemukan bahwa kinerja pengumpulan bermasalah maka seseorang dapat mencari implementasi alternatif. Ini jarang menjadi hal pertama yang harus dipertimbangkan oleh pengembangan yang dipimpin bisnis. Sangat jarang seseorang perlu mengimplementasikan struktur data seperti itu dengan tangan, biasanya ada pustaka yang dapat digunakan.