Mengapa std :: map diimplementasikan sebagai pohon merah-hitam?

193

Mengapa std::mapdiimplementasikan sebagai pohon merah-hitam ?

Ada beberapa pohon pencarian biner seimbang (BST) di luar sana. Apa trade-off desain dalam memilih pohon merah-hitam?

c++ dictionary data-structures stl binary-search-tree Denis Gorodetskiy
sumber
26
Meskipun semua implementasi yang saya lihat menggunakan RB-tree, perhatikan bahwa ini masih tergantung pada implementasi.
Thomas
3
@ Thomas. Ini tergantung pada implementasi, jadi mengapa semua implementasi menggunakan RB-tree?
Denis Gorodetskiy
1
Saya benar-benar ingin tahu apakah ada pelaksana STL yang berpikir untuk menggunakan Daftar Lewati.
Matthieu M.
2
Peta dan set C ++ sebenarnya adalah peta yang dipesan dan set yang dipesan. Mereka tidak diimplementasikan menggunakan fungsi hash. Setiap kueri akan diambil O(logn)dan tidak O(1), tetapi nilainya akan selalu diurutkan. Mulai dari C ++ 11 (saya pikir), ada unordered_mapdan unordered_set, yang diimplementasikan menggunakan fungsi hash dan sementara mereka tidak diurutkan, sebagian besar kueri dan operasi dimungkinkan dalam O(1)(rata-rata)
SomethingSomething
@ Thomas itu benar, tetapi tidak begitu menarik dalam praktik. Standar membuat jaminan kompleksitas dengan algoritma tertentu, atau serangkaian algoritma dalam pikiran.
Justin Meiners

Jawaban:

125

Mungkin dua algoritma pohon penyeimbang diri yang paling umum adalah pohon Merah-Hitam dan pohon AVL . Untuk menyeimbangkan pohon setelah penyisipan / perbarui kedua algoritma gunakan gagasan rotasi di mana simpul pohon diputar untuk melakukan penyeimbangan kembali.

Sementara di kedua algoritma operasi insert / delete adalah O (log n), dalam kasus rotasi penyeimbangan ulang pohon Merah-Hitam adalah operasi O (1) sementara dengan AVL ini adalah operasi O (log n) , membuat Pohon Merah-Hitam lebih efisien dalam aspek tahap penyeimbangan ulang dan salah satu alasan yang mungkin lebih sering digunakan.

Pohon Merah-Hitam digunakan di sebagian besar koleksi perpustakaan, termasuk penawaran dari Java dan Microsoft .NET Framework.

Chris Taylor
sumber
54
Anda membuatnya terdengar seperti pohon merah-hitam dapat melakukan modifikasi pohon dalam O (1) waktu, yang tidak benar. modifikasi pohon adalah O (log n) untuk pohon merah-hitam dan AVL. yang membuatnya memperdebatkan apakah bagian penyeimbang modifikasi pohon adalah O (1) atau O (log n) karena operasi utama sudah O (log n). bahkan setelah semua pekerjaan yang sedikit ekstra yang dilakukan pohon AVL menghasilkan pohon yang lebih seimbang yang mengarah ke pencarian yang sedikit lebih cepat. jadi itu adalah tradeoff yang benar-benar valid dan tidak membuat pohon AVL lebih rendah daripada pohon merah-hitam.
necromancer
35
Anda harus melihat di luar kerumitan ke runtime aktual untuk melihat perbedaan - pohon AVL umumnya memiliki runtime total yang lebih rendah ketika ada lebih banyak pencarian daripada sisipan / penghapusan. Pohon RB memiliki runtime total yang lebih rendah ketika ada lebih banyak sisipan / penghapusan. Proporsi pasti di mana kerusakan terjadi tentu saja tergantung pada banyak detail implementasi, perangkat keras, dan penggunaan yang tepat, tetapi karena penulis perpustakaan harus mendukung berbagai pola penggunaan, mereka harus mengambil tebakan yang berpendidikan. AVL juga sedikit lebih sulit untuk diterapkan, jadi Anda mungkin ingin manfaat yang terbukti untuk menggunakannya.
Steve Jessop
6
RB tree bukan "implementasi default". Setiap pelaksana memilih implementasi. Sejauh yang kita tahu, mereka semua memilih pohon RB, jadi mungkin ini untuk kinerja atau untuk kemudahan implementasi / pemeliharaan. Seperti yang saya katakan, breakpoint untuk kinerja mungkin tidak menyiratkan bahwa mereka pikir ada lebih banyak sisipan / penghapusan daripada pencarian, hanya saja rasio antara keduanya berada di atas tingkat di mana mereka berpikir RB mungkin mengalahkan AVL.
Steve Jessop
9
@Denis: sayangnya satu-satunya cara untuk mendapatkan angka adalah dengan membuat daftar std::mapimplementasi, melacak pengembang, dan bertanya kepada mereka kriteria apa yang mereka gunakan untuk membuat keputusan, jadi ini tetap spekulasi.
Steve Jessop
4
Yang hilang dari semua ini adalah biaya, per-simpul, untuk menyimpan informasi tambahan yang diperlukan untuk membuat keputusan yang seimbang. Pohon Merah-Hitam membutuhkan 1-bit untuk mewakili warnanya. Pohon AVL membutuhkan setidaknya 2 bit (untuk mewakili -1, 0 atau 1).
SJHowe
46

Itu benar-benar tergantung penggunaannya. Pohon AVL biasanya memiliki rotasi rebalancing yang lebih banyak. Jadi, jika aplikasi Anda tidak memiliki terlalu banyak operasi penyisipan dan penghapusan, tetapi beban berat pada pencarian, maka pohon AVL mungkin adalah pilihan yang baik.

std::map menggunakan pohon Merah-Hitam karena mendapat trade-off yang wajar antara kecepatan penyisipan / penghapusan simpul dan pencarian.

webbertiger
sumber
1
Apa kamu yakin akan hal itu??? Saya pribadi berpikir bahwa pohon Merah-Hitam itu atau lebih kompleks, tidak pernah lebih sederhana. Satu-satunya hal, di pohon Rd-Black, penyeimbangan kembali terjadi lebih jarang daripada AVL.
Eric Ouellet
1
@ Eric Secara teoritis, baik R / B tree dan AVL tree memiliki kompleksitas O (log n)) untuk penyisipan dan penghapusan. Tetapi satu bagian besar dari biaya operasi adalah rotasi, yang berbeda antara kedua pohon ini. Silakan merujuk ke diskusi.fogcreek.com/joelonsoftware/... Kutipan: "menyeimbangkan pohon AVL dapat membutuhkan rotasi O (log n), sementara pohon hitam merah akan membutuhkan paling banyak dua rotasi untuk menjadikannya seimbang (meskipun mungkin harus periksa O (log n) node untuk memutuskan di mana rotasi diperlukan). " Sunting komentar saya sesuai.
webbertiger
26

Pohon AVL memiliki ketinggian maksimum 1,44logn, sedangkan pohon RB memiliki maksimum 2logn. Memasukkan elemen dalam AVL dapat menyiratkan penyeimbangan kembali pada satu titik di pohon. Penyeimbangan ulang menyelesaikan penyisipan. Setelah menyisipkan daun baru, memperbarui leluhur daun itu harus dilakukan hingga ke akar, atau sampai pada titik di mana kedua sub pohon memiliki kedalaman yang sama. Probabilitas harus memperbarui k node adalah 1/3 ^ k. Penyeimbangan ulang adalah O (1). Menghapus elemen dapat menyiratkan lebih dari satu penyeimbangan ulang (hingga setengah kedalaman pohon).

BPR-pohon adalah B-pohon pesanan 4 yang direpresentasikan sebagai pohon pencarian biner. 4-simpul dalam B-tree menghasilkan dua level dalam BST yang setara. Dalam kasus terburuk, semua node pohon adalah 2-node, dengan hanya satu rantai 3-node ke daun. Daun itu akan berada pada jarak 2 logn dari akar.

Turun dari root ke titik penyisipan, kita harus mengubah 4-node menjadi 2-node, untuk memastikan setiap penyisipan tidak akan menjenuhkan daun. Kembali dari penyisipan, semua node ini harus dianalisis untuk memastikan mereka benar mewakili 4-node. Ini juga bisa dilakukan turun di pohon. Biaya global akan sama. Tidak ada makan siang gratis! Menghapus elemen dari pohon adalah urutan yang sama.

Semua pohon ini mengharuskan node membawa informasi tentang tinggi, berat, warna, dll. Hanya pohon Splay yang bebas dari info tambahan tersebut. Tetapi sebagian besar orang takut pada pohon Splay, karena struktur bangunannya yang bobrok!

Akhirnya, pohon juga dapat membawa informasi berat di simpul, memungkinkan penyeimbangan berat. Berbagai skema dapat diterapkan. Seseorang harus menyeimbangkan kembali ketika subtree mengandung lebih dari 3 kali jumlah elemen subtree lainnya. Penyeimbangan kembali dilakukan baik melalui rotasi tunggal atau ganda. Ini berarti kasus terburuk dari 2.4logn. Seseorang bisa lolos dengan 2 kali alih-alih 3, rasio yang jauh lebih baik, tetapi itu mungkin berarti meninggalkan sedikit kurang dari 1% dari subtree yang tidak seimbang di sana-sini. Rumit!

Jenis pohon apa yang terbaik? AVL pasti. Mereka adalah yang paling sederhana untuk dikodekan, dan memiliki ketinggian terburuk mereka yang terdekat dengan logn. Untuk pohon dengan 10.000.000 elemen, AVL paling tinggi 29, RB 40, dan bobot seimbang 36 atau 50 tergantung rasio.

Ada banyak variabel lain: keacakan, rasio penambahan, penghapusan, pencarian, dll.

pengguna847376
sumber
2
Jawaban yang bagus. Tetapi jika AVL adalah yang terbaik, mengapa perpustakaan standar mengimplementasikan std :: map sebagai RB tree?
Denis Gorodetskiy
13
Saya tidak setuju bahwa pohon AVL tidak diragukan lagi adalah yang terbaik. Meskipun mereka memiliki ketinggian rendah, mereka membutuhkan (total) lebih banyak pekerjaan untuk melakukan relabancing daripada pohon merah / hitam (O (log n) pekerjaan penyeimbangan versus O (1) pekerjaan penyeimbangan yang diamortisasi). Pohon merentang bisa jauh, jauh lebih baik dan pernyataan Anda bahwa orang takut pada mereka tidak berdasar. Tidak ada satu skema penyeimbangan pohon "terbaik" universal di luar sana.
templatetypedef
Jawabannya nyaris sempurna. Mengapa Anda mengatakan AVL adalah yang terbaik. Itu hanya salah dan itu sebabnya implementasi paling umum menggunakan pohon Merah-Hitam. Anda harus memiliki rasio manipulasi baca-baca yang cukup tinggi untuk memilih AVL. Selain itu, AVL memiliki jejak memori yang sedikit kurang dari RB.
Eric Ouellet
Saya setuju bahwa AVL cenderung lebih baik dalam banyak kasus, karena biasanya pohon dicari lebih sering daripada yang dimasukkan. Mengapa pohon RB secara luas dianggap lebih baik ketika itu adalah pohon dengan sedikit keuntungan dalam penulisan-kebanyakan kasus, dan yang lebih penting, sedikit kerugian dalam sebagian besar kasus baca? Apakah benar-benar percaya bahwa Anda akan memasukkan lebih dari yang Anda temukan?
doug65536
25

Jawaban sebelumnya hanya membahas alternatif pohon dan merah hitam mungkin hanya tersisa karena alasan historis.

Mengapa bukan tabel hash?

Suatu tipe hanya membutuhkan <operator (perbandingan) untuk digunakan sebagai kunci dalam pohon. Namun, tabel hash mengharuskan setiap jenis kunci memiliki hashfungsi yang ditentukan. Menjaga persyaratan tipe menjadi minimum sangat penting untuk pemrograman generik sehingga Anda dapat menggunakannya dengan berbagai jenis dan algoritme.

Merancang tabel hash yang baik membutuhkan pengetahuan yang mendalam tentang konteks yang akan digunakan. Haruskah itu menggunakan pengalamatan terbuka, atau menghubungkan rantai? Tingkat beban apa yang harus diterima sebelum mengubah ukuran? Haruskah menggunakan hash mahal yang menghindari tabrakan, atau yang kasar dan cepat?

Karena STL tidak dapat mengantisipasi yang merupakan pilihan terbaik untuk aplikasi Anda, standarnya harus lebih fleksibel. Pohon "hanya bekerja" dan skala baik.

(C ++ 11 memang menambahkan tabel hash dengan unordered_map. Anda dapat melihat dari dokumentasi itu memerlukan kebijakan pengaturan untuk mengkonfigurasi banyak opsi ini.)

Bagaimana dengan pohon lain?

Pohon Merah Hitam menawarkan pencarian cepat dan menyeimbangkan diri, tidak seperti BST. Pengguna lain menunjukkan kelebihannya dibandingkan dengan pohon AVL penyeimbang sendiri.

Alexander Stepanov (Pencipta STL) mengatakan bahwa ia akan menggunakan Pohon B * alih-alih pohon Merah-Hitam jika ia menulis std::maplagi, karena lebih ramah untuk cache memori modern.

Salah satu perubahan terbesar sejak itu adalah pertumbuhan cache. Kehilangan cache sangat mahal, jadi lokasi referensi jauh lebih penting sekarang. Struktur data berbasis node, yang memiliki lokalitas referensi rendah, jauh lebih tidak masuk akal. Jika saya merancang STL hari ini, saya akan memiliki satu set wadah yang berbeda. Misalnya, pohon B * -tingkat dalam memori adalah pilihan yang jauh lebih baik daripada pohon merah-hitam untuk menerapkan wadah asosiatif. - Alexander Stepanov

Haruskah peta selalu menggunakan pohon?

Kemungkinan implementasi peta lainnya adalah vektor yang diurutkan (sortasi sort) dan pencarian biner. Ini akan bekerja dengan baik untuk kontainer yang tidak sering dimodifikasi tetapi sering ditanyai. Saya sering melakukan ini di C sebagai qsortdan bsearchdibangun.

Apakah saya perlu menggunakan peta?

Pertimbangan cache berarti jarang digunakan std::listatau std::dequeberlebihanstd:vector bahkan untuk situasi yang kami diajarkan di sekolah (seperti menghapus elemen dari bagian tengah daftar). Menerapkan alasan yang sama, menggunakan loop untuk pencarian linear daftar seringkali lebih efisien dan lebih bersih daripada membangun peta untuk beberapa pencarian.

Tentu saja memilih wadah yang mudah dibaca biasanya lebih penting daripada kinerja.

Justin Meiners
sumber
3

Pembaruan 2017-06-14: webbertiger mengedit jawabannya setelah saya berkomentar. Saya harus menunjukkan bahwa jawabannya sekarang jauh lebih baik di mata saya. Tapi saya tetap menjawab sebagai informasi tambahan ...

Karena saya pikir jawaban pertama salah (koreksi: tidak keduanya lagi) dan jawaban ketiga salah. Saya merasa saya harus mengklarifikasi hal-hal ...

2 pohon paling populer adalah AVL dan Red Black (RB). Perbedaan utama terletak pada pemanfaatan:

  • AVL: Lebih baik jika rasio konsultasi (baca) lebih besar daripada manipulasi (modifikasi). Memori foot print sedikit kurang dari RB (karena bit yang diperlukan untuk pewarnaan).
  • RB: Lebih baik dalam kasus umum di mana ada keseimbangan antara konsultasi (baca) dan manipulasi (modifikasi) atau lebih banyak modifikasi daripada konsultasi. Jejak memori yang sedikit lebih besar karena penyimpanan bendera merah-hitam.

Perbedaan utama berasal dari pewarnaan. Anda memiliki aksi re-balance yang lebih sedikit dalam RB tree daripada AVL karena pewarnaan memungkinkan Anda untuk kadang-kadang melewati atau memperpendek aksi re-balance yang memiliki biaya relatif tinggi. Karena pewarnaannya, pohon RB juga memiliki level node yang lebih tinggi karena dapat menerima node merah di antara yang hitam (memiliki kemungkinan ~ 2x level lebih) membuat pencarian (baca) sedikit kurang efisien ... tetapi karena itu adalah konstan (2x), tetap di O (log n).

Jika Anda mempertimbangkan hit kinerja untuk modifikasi pohon (signifikansi) VS hit kinerja konsultasi pohon (hampir tidak signifikan), menjadi alami untuk memilih RB daripada AVL untuk kasus umum.

Eric Ouellet
sumber
2

Ini hanya pilihan implementasi Anda - mereka dapat diimplementasikan sebagai pohon seimbang. Berbagai pilihan semuanya sebanding dengan perbedaan kecil. Karena itu, apapun itu sama baiknya dengan apapun.

ahli nujum
sumber