Mengapa pohon Merah-Hitam begitu populer?

Tampaknya di mana pun saya melihat, struktur data sedang dilaksanakan menggunakan pohon merah-hitam ( std::setdalam C ++, SortedDictionarydi C #, dll.)

Baru saja membahas (a, b), pohon merah-hitam & AVL di kelas algoritme saya, inilah yang saya dapatkan (juga dari bertanya di sekitar profesor, melihat-lihat beberapa buku dan sedikit mencari di Google):

• Pohon AVL memiliki kedalaman rata-rata yang lebih kecil daripada pohon merah-hitam, dan karenanya mencari nilai dalam pohon AVL secara konsisten lebih cepat.
• Pohon merah-hitam membuat lebih sedikit perubahan struktural untuk menyeimbangkan diri dari pohon AVL, yang bisa membuatnya berpotensi lebih cepat untuk disisipkan / dihapus. Saya katakan berpotensi, karena ini akan tergantung pada biaya perubahan struktural ke pohon, karena ini akan sangat tergantung pada runtime dan implemntation (mungkin juga sangat berbeda dalam bahasa fungsional ketika pohon tidak dapat diubah?)

Ada banyak tolok ukur online yang membandingkan AVL dan pohon merah-hitam, tetapi yang mengejutkan saya adalah bahwa pada dasarnya profesor saya berkata, bahwa biasanya Anda akan melakukan salah satu dari dua hal:

• Entah Anda tidak terlalu peduli tentang kinerja, dalam hal perbedaan 10-20% dari AVL vs Merah-hitam dalam banyak kasus tidak akan menjadi masalah sama sekali.
• Atau Anda benar-benar peduli dengan kinerja, di mana Anda akan meninggalkan AVL dan pohon merah-hitam, dan menggunakan B-tree, yang dapat diubah agar bekerja lebih baik (atau (a, b) -tree, saya ' Aku akan meletakkan semua itu dalam satu keranjang.)

Alasan untuk itu adalah karena B-tree menyimpan data lebih padat dalam memori (satu node berisi banyak nilai) akan ada lebih sedikit cache yang hilang. Anda juga dapat mengubah implementasi berdasarkan use case, dan membuat urutan B-tree bergantung pada ukuran cache CPU, dll.

Masalahnya adalah bahwa saya tidak dapat menemukan hampir semua sumber yang akan menganalisis penggunaan kehidupan nyata implementasi pohon pencarian yang berbeda pada perangkat keras modern yang sebenarnya. Saya telah membaca banyak buku tentang algoritma dan belum menemukan apa pun yang akan membandingkan varian pohon yang berbeda secara bersamaan, selain menunjukkan bahwa satu memiliki kedalaman rata-rata yang lebih kecil daripada yang lainnya (yang tidak benar-benar mengatakan banyak tentang bagaimana pohon akan berperilaku dalam program nyata.)

Yang sedang berkata, apakah ada alasan khusus mengapa pohon merah-hitam digunakan di mana-mana, ketika berdasarkan apa yang dikatakan di atas, pohon B harus mengungguli mereka? (sebagai satu-satunya patokan saya dapat menemukan juga menunjukkan http://lh3lh3.users.sourceforge.net/udb.shtml , tetapi mungkin hanya masalah implementasi spesifik). Atau apakah alasan mengapa setiap orang menggunakan pohon merah-hitam karena mereka agak mudah diimplementasikan, atau dengan kata lain, sulit untuk diterapkan dengan buruk?

Juga, bagaimana hal ini berubah ketika seseorang pindah ke bidang bahasa fungsional? Tampaknya Clojure dan Scala menggunakan array Hash yang dipetakan , di mana Clojure menggunakan faktor percabangan 32.

Mengutip dari jawaban untuk pertanyaan " Traversal from root in AVL trees and Red Black Trees "

Untuk beberapa jenis pohon pencarian biner, termasuk pohon merah-hitam tetapi bukan pohon AVL, "perbaikan" untuk pohon tersebut dapat dengan mudah diprediksi dalam perjalanan turun dan dilakukan selama satu laluan top-down, membuat lintasan kedua tidak diperlukan. Algoritma penyisipan seperti itu biasanya diimplementasikan dengan loop daripada rekursi, dan seringkali berjalan sedikit lebih cepat dalam praktik daripada rekan dua-lintasannya.

Jadi penyisipan pohon RedBlack dapat diimplementasikan tanpa rekursi, pada beberapa rekursi CPU sangat mahal jika Anda menyerbu cache panggilan fungsi (mis. SPARC karena penggunaan jendela Daftar )

(Saya telah melihat perangkat lunak berjalan lebih dari 10 kali lebih cepat pada Sparc dengan menghapus satu panggilan fungsi, yang mengakibatkan jalur kode yang sering disebut terlalu dalam untuk jendela register. Karena Anda tidak tahu seberapa dalam jendela register akan hidup. sistem pelanggan Anda, dan Anda tidak tahu seberapa jauh tumpukan panggilan Anda berada di "jalur kode panas", tidak menggunakan rekursi membuat lebih mudah diprediksi.)

Juga tidak berisiko kehabisan tumpukan adalah manfaatnya.

Saya telah meneliti topik ini baru-baru ini juga, jadi inilah temuan saya, tetapi perlu diingat bahwa saya bukan ahli dalam struktur data!

Ada beberapa kasus di mana Anda tidak dapat menggunakan B-tree sama sekali.

Satu kasus yang menonjol adalah std::mapdari C ++ STL. Standar ini mensyaratkan bahwa inserttidak membatalkan iterator yang ada

Tidak ada iterator atau referensi yang tidak valid.

http://en.cppreference.com/w/cpp/container/map/insert

Ini mengesampingkan B-tree sebagai implementasi karena penyisipan akan bergerak di sekitar elemen yang ada.

Kasus penggunaan serupa lainnya adalah struktur data intrusif. Artinya, alih-alih menyimpan data Anda di dalam simpul pohon, Anda menyimpan pointer ke anak-anak / orang tua di dalam struktur Anda:

// non intrusive
struct Node<T> {
    T value;
    Node<T> *left;
    Node<T> *right;
};
using WalrusList = Node<Walrus>;

// intrusive
struct Walrus {
    // Tree part
    Walrus *left;
    Walrus *right;

    // Object part
    int age;
    Food[4] stomach;
};

Anda tidak bisa membuat B-tree mengganggu, karena itu bukan struktur data pointer-only.

Pohon merah-hitam yang mengganggu digunakan, misalnya, di jemalloc untuk mengelola blok memori yang bebas. Ini juga merupakan struktur data yang populer di kernel Linux.

Saya juga percaya bahwa implementasi "single pass tail rekursif" bukan alasan untuk popularitas pohon merah-hitam sebagai struktur data yang bisa berubah .

$\log{n}$

$O(1)$

$O(1)$

Varian yang dijelaskan dalam opendatastructures menggunakan parent pointer, sebuah down pass rekursif untuk pemasangan dan sebuah up up loop berulang untuk perbaikan. Panggilan rekursif berada di posisi ekor dan kompiler mengoptimalkan ini ke loop (saya sudah memeriksa ini di Rust).

$O(1)$

Yah, ini bukan jawaban yang otoritatif, tetapi setiap kali saya harus kode pohon pencarian biner seimbang, itu pohon merah-hitam. Ada beberapa alasan untuk ini:

1) Biaya penyisipan rata-rata adalah konstan untuk pohon merah-hitam (jika Anda tidak harus mencari), sementara itu logaritmik untuk pohon AVL. Lebih jauh lagi, ini melibatkan paling banyak satu restrukturisasi yang rumit. Ini masih O (log N) dalam kasus terburuk, tapi itu hanya pewarnaan ulang sederhana.

2) Mereka hanya membutuhkan 1 bit informasi tambahan per node, dan Anda sering dapat menemukan cara untuk mendapatkannya secara gratis.

3) Saya tidak harus melakukan ini terlalu sering, jadi setiap kali saya melakukannya saya harus mencari tahu bagaimana melakukannya lagi. Aturan sederhana dan korespondensi dengan 2-4 pohon membuatnya tampak mudah setiap saat , meskipun kode itu ternyata rumit setiap saat . Saya masih berharap bahwa suatu hari kode akan menjadi sederhana.

4) Cara pohon merah-hitam membagi simpul pohon 2-4 yang sesuai dan memasukkan kunci tengah ke dalam simpul induk 2-4 hanya dengan mengubah warna menjadi sangat elegan. Saya suka melakukannya.

Pohon merah-hitam atau AVL memiliki keunggulan dibandingkan B-tree dan sejenisnya ketika kunci panjang atau karena alasan lain memindahkan kunci mahal.

Saya menciptakan alternatif saya sendiri std::setdalam proyek besar, karena sejumlah alasan kinerja. Saya memilih AVL daripada merah-hitam karena alasan kinerja (tapi peningkatan kinerja kecil itu bukan pembenaran untuk menggulir sendiri, bukan std :: set). "Kunci" yang rumit dan sulit untuk dipindahkan adalah faktor penting. Apakah (a, b) pohon masih masuk akal jika Anda membutuhkan tingkat tipuan lain di depan kunci? AVL dan pohon merah-hitam dapat direstrukturisasi tanpa memindahkan kunci, sehingga mereka memiliki keuntungan ketika kunci mahal untuk dipindahkan.