Pohon merah hitam di atas pohon avl

108

AVL dan Pohon hitam merah keduanya menyeimbangkan diri sendiri kecuali warna merah dan hitam di node. Apa alasan utama memilih pohon Merah hitam daripada pohon AVL? Apa Aplikasi Pohon Hitam Merah?

algorithm data-structures red-black-tree suren
sumber
2
kemungkinan duplikat dari Why is std :: map diimplementasikan sebagai pohon merah-hitam?
Lior Kogan
1
Sebagai tambahan, para pengembang Rust memilih untuk menggunakan pohon-B daripada salah satu dari ini untuk peta pesanan standar mereka.
Tom Anderson

Jawaban:

123

Apa alasan utama memilih pohon Merah hitam daripada pohon AVL?

Baik pohon merah-hitam maupun pohon AVL adalah pohon pencarian biner seimbang yang paling umum digunakan dan mendukung penyisipan, penghapusan, dan pencarian dengan jaminan O(logN) time. Namun, ada beberapa poin perbandingan antara keduanya:

  • Pohon AVL lebih seimbang dan karenanya memberikan pencarian yang lebih cepat. Jadi, untuk tugas intensif pencarian, gunakan pohon AVL.
  • Untuk memasukkan tugas intensif, gunakan pohon Merah-Hitam.
  • Pohon AVL menyimpan faktor keseimbangan di setiap node. Ini membutuhkan O(N)ruang ekstra. Namun, jika kita tahu bahwa kunci yang akan disisipkan di pohon akan selalu lebih besar dari nol, kita dapat menggunakan bit tanda kunci untuk menyimpan informasi warna pohon merah-hitam. Jadi, dalam kasus seperti itu, pohon merah-hitam tidak membutuhkan ruang ekstra.

Apa aplikasi pohon merah hitam?

Pohon merah-hitam adalah tujuan yang lebih umum. Mereka melakukannya dengan relatif baik saat menambah, menghapus, dan mencari tetapi pohon AVL memiliki pencarian lebih cepat dengan biaya tambah / hapus yang lebih lambat. Pohon merah-hitam digunakan sebagai berikut:

  • Java: java.util.TreeMap,java.util.TreeSet
  • C ++ STL (di sebagian besar implementasi): map, multimap, multiset
  • Kernel Linux: penjadwal yang benar-benar adil, linux / rbtree.h
Nikunj Banka
sumber
43
In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree.tidak benar.
Jingguo Yao
9
Untuk menjadi bertele-tele, standar C ++ tidak mengamanatkan bahwa std:: mapdan teman-teman menggunakan struktur tertentu. Itu tersisa untuk implementasi, meskipun libstdc ++ dan Dinkumware setidaknya menggunakan pohon merah-hitam, dan sepertinya Anda benar dalam praktiknya.
mbozzi
25
Faktor keseimbangan yang disimpan di setiap node dari pohon AVL adalah dua bit (-1 / 0 / +1). Pohon merah-hitam menyimpan satu bit informasi warna di setiap node. Jadi secara total kedua pohon membutuhkan memori O (N) untuk informasi tambahan.
Seppo Enarvi
5
"Untuk menyisipkan tugas intensif, gunakan pohon Merah-Hitam." Mengapa? Penyisipan pohon AVL hanya membutuhkan satu rotasi paling buruk, sedangkan pohon Merah Hitam dapat mengambil dua rotasi.
Daniel
3
Ini harus diperbarui sesuai dengan analisis kinerja BST tahun 2003 dari Ben Pfaff - Pohon AVL lebih bersifat umum dan bekerja lebih baik. Alasan historis yang tepat untuk Java, C ++ dan kernel Linux yang memilih implementasi yang lebih lambat akan menarik untuk dilacak.
David McManamon
16

Coba baca artikel ini

Ini menawarkan beberapa wawasan bagus tentang perbedaan, persamaan, kinerja, dll.

Berikut kutipan dari artikel tersebut:

RB-Trees sama seperti pohon AVL, self-balancing. Keduanya menyediakan kinerja pencarian dan penyisipan O (log n).

Perbedaannya adalah RB-Trees menjamin O (1) rotasi per operasi penyisipan. Itulah yang sebenarnya membebani kinerja dalam implementasi nyata.

Sederhananya, RB-Trees mendapatkan keuntungan ini dari secara konseptual menjadi 2-3 pohon tanpa membawa beban overhead dari struktur node dinamis. Secara fisik RB-Trees diimplementasikan sebagai pohon biner, bendera merah / hitam mensimulasikan 2-3 perilaku

Sejauh pemahaman saya sendiri, pohon AVL dan pohon RB tidak terlalu jauh dalam hal kinerja. Pohon RB hanyalah varian dari pohon B dan penyeimbangan diimplementasikan secara berbeda dari pohon AVL.

Yordania
sumber
1
AFIAK, pohon AVL juga memiliki O (1) rotasi per penyisipan. Untuk RB-tree dan AVL - satu penyisipan dapat memiliki 1 atau 0 rotasi. Jika rotasi terjadi, algoritme berhenti. Jika tidak terjadi, biasanya algoritme terus memeriksa / mengecat ulang node dari bawah ke akar pohon. Jadi, terkadang rotasi O (1) bisa lebih baik karena menghilangkan pemindaian item yang tersisa O (log (n)). Karena pohon AVL, secara rata-rata, membuat lebih banyak rotasi, pohon AVL biasanya memiliki keseimbangan yang lebih baik ~ 1,44 log (N) daripada RB-pohon 2 log (N).
Sergey Shandar
4

Pemahaman kami tentang perbedaan kinerja telah meningkat selama bertahun-tahun dan sekarang alasan utama untuk menggunakan pohon merah-hitam di atas AVL adalah karena tidak memiliki akses ke implementasi AVL yang baik karena sedikit kurang umum mungkin karena tidak tercakup dalam CLRS.

Kedua pohon sekarang dianggap sebagai pohon dengan peringkat seimbang tetapi pohon merah-hitam secara konsisten lebih lambat sekitar 20% dalam pengujian dunia nyata . Atau bahkan 30-40% lebih lambat saat data berurutan dimasukkan .

Jadi orang yang telah mempelajari pohon merah-hitam tetapi bukan pohon AVL cenderung memilih pohon merah-hitam. Kegunaan utama pohon merah-hitam dirinci di entri Wikipedia untuk mereka .

David McManamon
sumber
1
Lucu! Dalam pembacaan saya, artikel libavl sepertinya mengatakan bahwa AVL dan RB adalah head-to-head, dan tidak ada yang sangat jelas lebih baik dari yang lain secara umum (mana yang lebih baik tergantung pada beban kerja). Saya tidak melihat di mana pun klaim bahwa AVL secara keseluruhan sekitar 20% lebih cepat.
Stefan
3

Jawaban lain di sini merangkum pro & kontra pohon RB dan AVL dengan baik, tetapi menurut saya perbedaan ini sangat menarik:

Pohon AVL tidak mendukung biaya pembaruan diamortisasi yang konstan [tetapi pohon merah-hitam mendukung ]

Sumber: Mehlhorn & Sanders (2008) (bagian 7.4)

Jadi, sementara pohon RB dan AVL menjamin waktu terburuk O (log (N)) untuk pencarian, penyisipan dan penghapusan, memulihkan properti AVL / RB setelah menyisipkan atau menghapus node dapat dilakukan dalam O (1) waktu diamortisasi untuk pohon merah-hitam.

emanek
sumber
Saya yakin, penyisipan pohon AVL memiliki biaya amortisasi yang sama / serupa tetapi menghasilkan pohon yang lebih seimbang (1,44log (N) vs 2log (N)). Pada saat yang sama, penghapusan pohon AVL mungkin memerlukan lebih banyak rotasi. IMHO, ini dialamatkan di WAVL en.wikipedia.org/wiki/WAVL_tree
Sergey Shandar
1

Pemrogram umumnya tidak suka mengalokasikan memori secara dinamis. Masalah dengan pohon avl adalah bahwa untuk elemen "n" Anda membutuhkan setidaknya log2 (log2 (n)) ... (tinggi-> log2 (n)) bit untuk menyimpan tinggi pohon! Jadi, ketika Anda menangani data yang sangat besar, Anda tidak dapat memastikan berapa banyak bit yang dialokasikan untuk menyimpan ketinggian di setiap node.

Misalnya jika Anda menggunakan 4 byte int (32 bit) untuk menyimpan tinggi. Tinggi maksimum dapat menjadi: 2 ^ 32 dan karenanya jumlah maksimum elemen yang dapat Anda simpan di pohon adalah 2 ^ (2 ^ 32) - (sepertinya sangat besar tetapi dalam usia data ini, saya kira tidak ada yang terlalu besar). Dan karenanya, jika Anda melakukan pemotretan berlebihan, batas ini Anda harus mengalokasikan lebih banyak ruang secara dinamis untuk menyimpan ketinggian.

Ini adalah jawaban yang disarankan oleh seorang profesor di universitas saya yang tampaknya masuk akal bagi saya! Semoga saya masuk akal.

Pengeditan: Pohon AVL lebih seimbang dibandingkan dengan Pohon Merah Hitam, tetapi mereka dapat menyebabkan lebih banyak rotasi selama penyisipan dan penghapusan. Jadi jika aplikasi Anda melibatkan banyak penyisipan dan penghapusan yang sering, maka pohon Merah Hitam harus lebih disukai. Dan jika penyisipan dan penghapusan lebih jarang dan pencarian lebih sering beroperasi, maka pohon AVL harus lebih disukai daripada Pohon Merah Hitam. --Sumber GEEKSFORGEEKS.ORG

Prakhar Agrawal
sumber
1
Menurut saya ini menarik tetapi tidak praktis. Memang benar bahwa dalam kasus yang paling ringkas akan menjadi tugas yang sulit untuk memilih jumlah bit yang paling efisien untuk dialokasikan untuk ketinggian, dalam praktiknya setiap ruang tersisa yang kurang dari satu byte pasti tidak akan digunakan, dan apa pun yang tersisa dalam ruang 4 atau bahkan 8 byte hampir pasti tidak akan digunakan. Memori tidak dialokasikan secara tidak selaras karena alasan kinerja yang sangat mengesampingkan manfaat dari merebut kembali sejumlah kecil ruang. Pointer ke anak-anak dan nilainya menempati 24 byte; 8 lagi kemungkinan tidak memiliki biaya praktis.
Mumbleskates
4
you need need atleast log2(log2(n))...(height->log2(n)) bits to store the height of [an AVL] treeSaya tidak memerlukan ketinggian node apa pun di pohon AVL untuk menerapkannya. Anda membutuhkan sedikit informasi tambahan untuk setiap node ( AKU YANG TERBESAR (saudara dengan sub-pohon tertinggi))); akan lebih nyaman serta konvensional untuk memiliki dua bit ekstra (anak lebih tinggi untuk kiri & kanan), seperti yang disajikan oleh AV & L.
greybeard
4
2 ^ (2 ^ 32) unsur sangat banyak ... seperti Anda dapat menyimpan setiap molekul di seluruh alam semesta, dan setiap pasangan yang mungkin dari molekul itu, dan setiap tiga kemungkinan, dan bahkan masih belum mulai datang bahkan dari jarak yang sangat dekat berada dalam bagian kecil dari persentase kecil dari akar pangkat tiga dari angka itu dibagi dengan seratus triliun.
titik koma
4
Ini sangat menyesatkan. Pertama, kita tidak perlu menyimpan ketinggian di simpul pohon AVL. Kedua, bahkan jika kita melakukannya, dan bahkan jika jumlah tipikal memori yang tersedia berlipat ganda setiap tahun, kita masih memiliki 4 miliar tahun hingga tinggi pohon kita melebihi apa yang dapat disimpan dalam 32 bit.
Gassa
3
2 ^ (2 ^ 32) objek adalah sangat, sangat gila, benar-benar lebih dari komputer mana pun yang dapat kita bayangkan saat ini. Kami berada di sekitar 2 ^ 40. Periksa matematika Anda lagi.
Stefan Reich
-1

Penyeimbangan ulang pohon AVL harus memenuhi properti di bawah ini. (Referensi Wiki - Pohon AVL )

Dalam pohon AVL, ketinggian dari dua anak pohon dari setiap node berbeda paling banyak satu; jika sewaktu-waktu berbeda lebih dari satu, dilakukan rebalancing untuk memulihkan properti ini.

Jadi ini menyiratkan bahwa tinggi keseluruhan pohon AVL tidak dapat berubah, yaitu pencarian akan menjadi lebih baik dengan Pohon AVL. Dan karena operasi tambahan (rotasi) harus dilakukan agar ketinggian tidak berubah, operasi modifikasi pohon dapat menjadi sedikit mahal.

samshers
sumber
Disebutkan di banyak tempat lain, tetapi alasan jawaban ini tidak terlalu bagus adalah karena pohon AVL dan pohon RB secara efektif mempertahankan batasan yang sangat mirip - pohon RB tidak akan lebih dari 2,0 kali tinggi yang diperlukan, dan untuk pohon AVL faktornya adalah sekitar 1,44. Akibatnya, pohon AVL sedikit lebih sering berputar, tetapi biaya per rotasi pada dasarnya sama; itu tidak mahal.
Mumbleskates