Apa perbedaan antara pohon pencarian biner dan tumpukan biner?

Keduanya tampak sangat mirip dan memiliki struktur yang hampir identik. Apa bedanya? Apa kompleksitas waktu untuk operasi yang berbeda masing-masing?

Heap hanya menjamin bahwa elemen pada level yang lebih tinggi lebih besar (untuk max-heap) atau lebih kecil (untuk min-heap) daripada elemen di level yang lebih rendah, sedangkan BST menjamin pesanan (dari "kiri" ke "kanan"). Jika Anda ingin elemen yang diurutkan, gunakan BST. oleh Dante bukan geek

Heap lebih baik di findMin / findMax (O (1)), sedangkan BST bagus di semua ditemukan (O (logN)). Sisipkan adalah O (logN) untuk kedua struktur. Jika Anda hanya peduli dengan findMin / findMax (mis. Terkait prioritas), lanjutkan dengan heap. Jika Anda ingin semuanya diurutkan, gunakan BST.

oleh xysun

Baik pohon pencarian biner dan tumpukan biner adalah struktur data berbasis pohon.

Tumpukan membutuhkan node untuk memiliki prioritas di atas anak-anak mereka. Dalam tumpukan maksimum, anak-anak setiap node harus kurang dari itu sendiri. Ini kebalikan dari min heap:

Pohon pencarian biner (BST) mengikuti pemesanan khusus (pre-order, in-order, post-order) di antara saudara kandung node. Pohon itu harus disortir, tidak seperti tumpukan:

BST memiliki rata-rata untuk penyisipan, penghapusan, dan pencarian. Binary Heaps memiliki rata-rata untuk findMin / findMax dan untuk penyisipan dan penghapusan.$O(\log n)$
$O(1)$$O(\log n)$

Ringkasan

          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

Semua waktu rata-rata di tabel ini sama dengan waktu terburuknya kecuali untuk Sisipan.

• *: di mana-mana dalam jawaban ini, BST == BST Seimbang, karena tidak seimbang menyebalkan tanpa gejala
• **: menggunakan modifikasi sepele yang dijelaskan dalam jawaban ini
• ***: log(n)untuk tumpukan pohon penunjuk, nuntuk tumpukan array dinamis

Keuntungan tumpukan biner dibandingkan BST

• penyisipan waktu rata-rata ke dalam tumpukan biner adalah O(1), untuk BST adalah O(log(n)). Ini adalah fitur pembunuh tumpukan.

  Ada juga tumpukan lain yang mencapai O(1)amortisasi (lebih kuat) seperti Fibonacci Heap , dan bahkan kasus terburuk, seperti antrian Brodal , meskipun mungkin tidak praktis karena kinerja non-asimtotik: https://stackoverflow.com/questions/30782636 / are-fibonacci-heaps-or-brodal-queue-used-in-practice-dimanapun

• tumpukan biner dapat diimplementasikan secara efisien di atas array dinamis atau pohon berbasis pointer, hanya pohon berbasis pointer BST. Jadi untuk heap kita dapat memilih implementasi array yang lebih efisien ruang, jika kita dapat sesekali mengubah ukuran latensi.

• penciptaan biner tumpukan adalah O(n)kasus terburuk , O(n log(n))untuk BST.

Keuntungan BST dibandingkan tumpukan biner

• mencari elemen sewenang-wenang adalah O(log(n)). Ini adalah fitur pembunuh BST.

  Untuk heap, secara O(n)umum, kecuali untuk elemen terbesar yaitu O(1).

"Salah" keuntungan dari tumpukan lebih dari BST

• heap adalah O(1)menemukan max, BST O(log(n)).

  Ini adalah kesalahpahaman umum, karena sepele untuk memodifikasi BST untuk melacak elemen terbesar, dan memutakhirkannya setiap kali elemen itu dapat diubah: pada penyisipan swap yang lebih besar, pada penghapusan cari yang terbesar kedua. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (disebutkan oleh Yeo ).

  Sebenarnya, ini adalah batasan tumpukan dibandingkan dengan BST: satu - satunya pencarian yang efisien adalah untuk elemen terbesar.

Masukkan tumpukan biner rata-rata adalah O(1)

Sumber:

• Paper: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Slide WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Argumen intuitif:

• tingkat pohon bawah memiliki elemen lebih banyak daripada tingkat atas secara eksponensial, sehingga elemen baru hampir pasti akan berada di bagian bawah
• penyisipan heap dimulai dari bawah , BST harus dimulai dari atas

Dalam tumpukan biner, meningkatkan nilai pada indeks yang diberikan juga O(1)karena alasan yang sama. Tetapi jika Anda ingin melakukan itu, ada kemungkinan bahwa Anda ingin menjaga indeks tambahan tetap up-to-date pada operasi heap https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease- kunci-operasi-untuk-min-heap berbasis-prioritas-queu misalnya untuk Dijkstra. Mungkin tanpa biaya waktu tambahan.

GCC C ++ standar memasukkan patokan perpustakaan pada perangkat keras nyata

Saya melakukan benchmark pada sisipan C ++ std::set( Red-black tree BST ) dan std::priority_queue( dynamic array heap ) untuk melihat apakah saya benar tentang waktu insert, dan inilah yang saya dapatkan:

• kode tolok ukur
• skrip plot
• plot data
• diuji pada Ubuntu 19.04, GCC 8.3.0 di laptop Lenovo ThinkPad P51 dengan CPU: CPU Intel Core i7-7820HQ (4 core / 8 thread, basis 2.90 GHz, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB , 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512GB, 3.000 MB / s)

Sangat jelas:

• heap insert time pada dasarnya konstan.

  Kita dapat dengan jelas melihat titik ukuran array dinamis. Karena kami rata-rata setiap 10k menyisipkan untuk dapat melihat apa pun di atas kebisingan sistem , puncak-puncak itu sebenarnya sekitar 10k kali lebih besar daripada yang ditampilkan!

  Grafik yang diperbesar pada dasarnya mengecualikan hanya titik ukuran array, dan menunjukkan bahwa hampir semua sisipan berada di bawah 25 nanodetik.

• BST adalah logaritmik. Semua sisipan jauh lebih lambat daripada rata-rata insert heap.

• BST vs analisis hashmap rinci di: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

GCC C ++ standar memasukkan patokan perpustakaan pada gem5

gem5 adalah simulator sistem lengkap, dan karenanya menyediakan jam yang sangat akurat m5 dumpstats. Jadi saya mencoba menggunakannya untuk memperkirakan waktu untuk setiap sisipan.

Interpretasi:

• heap masih konstan, tetapi sekarang kita melihat lebih detail bahwa ada beberapa baris, dan setiap baris yang lebih tinggi lebih jarang.

  Ini harus sesuai dengan latensi akses memori dilakukan untuk menyisipkan lebih tinggi dan lebih tinggi.

• TODO Saya benar-benar tidak dapat menafsirkan BST sepenuhnya karena tidak terlihat begitu logaritmik dan agak lebih konstan.

  Namun, dengan detail yang lebih besar ini, kita juga dapat melihat beberapa garis yang berbeda, tetapi saya tidak yakin apa yang mereka wakili: Saya berharap garis bawahnya menjadi lebih tipis, karena kita memasukkan bagian bawah atas?

Benchmarked dengan pengaturan Buildroot ini pada CPU HPI aarch64 .

BST tidak dapat diimplementasikan secara efisien pada array

Operasi tumpukan hanya perlu menggelembung ke atas atau ke bawah cabang pohon tunggal, sehingga O(log(n))kasus terburuk bertukar, O(1)rata-rata.

Menjaga BST seimbang membutuhkan rotasi pohon, yang dapat mengubah elemen atas untuk elemen lainnya, dan akan membutuhkan pemindahan seluruh larik ( O(n)).

Tumpukan dapat diimplementasikan secara efisien pada array

Indeks induk dan anak-anak dapat dihitung dari indeks saat ini seperti yang ditunjukkan di sini .

Tidak ada operasi penyeimbangan seperti BST.

Hapus min adalah operasi yang paling mengkhawatirkan karena harus dari atas ke bawah. Tapi itu selalu bisa dilakukan dengan "meresap" satu cabang tumpukan seperti yang dijelaskan di sini . Ini mengarah ke kasus terburuk O (log (n)), karena heap selalu seimbang.

Jika Anda memasukkan satu simpul untuk setiap simpul yang Anda hapus, maka Anda kehilangan keuntungan dari rata-rata sisipan O (1) asimptotik yang diberikan tumpukan karena penghapusan akan mendominasi, dan Anda sebaiknya menggunakan BST. Namun Dijkstra memperbarui node beberapa kali untuk setiap penghapusan, jadi kami baik-baik saja.

Tumpukan array dinamis vs tumpukan pohon penumpukan

Tumpukan dapat diimplementasikan secara efisien di atas tumpukan penunjuk: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efisien-pointer-based-binary-heap-implementations

Implementasi array dinamis lebih hemat ruang. Misalkan setiap elemen tumpukan hanya berisi pointer ke struct:

• implementasi pohon harus menyimpan tiga pointer untuk setiap elemen: orang tua, anak kiri dan anak kanan. Jadi penggunaan memori selalu 4n(3 pointer pohon + 1 structpointer).

  Tree BST juga akan membutuhkan informasi penyeimbangan lebih lanjut, mis. Merah-hitam.

• implementasi array dinamis bisa berukuran 2nsetelah penggandaan. Jadi rata-rata akan seperti itu 1.5n.

Di sisi lain, tumpukan pohon memiliki insert terburuk terburuk, karena menyalin array dinamis dukungan untuk menggandakan ukurannya mengambil O(n)terburuk, sedangkan tumpukan pohon hanya melakukan alokasi kecil baru untuk setiap node.

Namun, penggandaan susunan backing O(1)diamortisasi, sehingga menjadi pertimbangan latensi maksimum. Disebutkan di sini .

Filsafat

• BST menjaga properti global antara orang tua dan semua keturunan (kiri lebih kecil, kanan lebih besar).

  Node atas BST adalah elemen tengah, yang membutuhkan pengetahuan global untuk mempertahankan (mengetahui berapa banyak elemen yang lebih kecil dan lebih besar di sana).

  Properti global ini lebih mahal untuk dirawat (log n insert), tetapi memberikan pencarian yang lebih kuat (log n search).

• Tumpukan mempertahankan properti lokal antara orang tua dan anak-anak langsung (orang tua> anak-anak).

  Catatan utama tumpukan adalah elemen besar, yang hanya membutuhkan pengetahuan lokal untuk mempertahankan (mengetahui orang tua Anda).

Daftar tertaut ganda

Daftar tertaut ganda dapat dilihat sebagai bagian dari tumpukan di mana item pertama memiliki prioritas terbesar, jadi mari kita bandingkan mereka di sini juga:

• insersi:
  • posisi:
    • daftar tertaut dua kali lipat: item yang dimasukkan harus yang pertama atau terakhir, karena kami hanya memiliki pointer ke elemen-elemen itu.
    • tumpukan biner: item yang dimasukkan dapat berakhir pada posisi apa pun. Kurang membatasi daripada daftar tertaut.
  • waktu:
    • daftar tertaut ganda: O(1)kasus terburuk karena kami memiliki petunjuk ke item, dan pembaruannya sangat sederhana
    • biner heap: O(1)rata-rata, jadi lebih buruk dari daftar tertaut. Tradeoff untuk memiliki posisi penyisipan yang lebih umum.
• cari: O(n)untuk keduanya

Kasus penggunaan untuk ini adalah ketika kunci tumpukan adalah cap waktu saat ini: dalam kasus itu, entri baru akan selalu pergi ke awal daftar. Jadi kita bahkan dapat melupakan timestamp yang tepat sama sekali, dan hanya menjaga posisi dalam daftar sebagai prioritas.

Ini dapat digunakan untuk mengimplementasikan cache LRU . Sama seperti untuk menumpuk aplikasi seperti Dijkstra , Anda akan ingin menyimpan hashmap tambahan dari kunci ke simpul yang sesuai dari daftar, untuk menemukan simpul mana yang akan diperbarui dengan cepat.

Perbandingan BST Seimbang yang berbeda

Meskipun memasukkan asimtotik dan menemukan waktu untuk semua struktur data yang umumnya diklasifikasikan sebagai "BST Seimbang" yang saya lihat sejauh ini adalah sama, BBST yang berbeda memiliki trade-off yang berbeda. Saya belum sepenuhnya mempelajari ini, tetapi akan lebih baik untuk meringkas trade-off ini di sini:

• Pohon merah-hitam . Tampaknya menjadi BBST yang paling umum digunakan pada 2019, misalnya BBST yang digunakan oleh implementasi GCC 8.3.0 C ++
• Pohon AVL . Tampaknya sedikit lebih seimbang daripada BST, jadi bisa lebih baik untuk menemukan latensi, dengan biaya penemuan yang sedikit lebih mahal. Wiki merangkum: "Pohon AVL sering dibandingkan dengan pohon merah-hitam karena keduanya mendukung rangkaian operasi yang sama dan meluangkan waktu yang sama untuk operasi dasar. Untuk aplikasi pencarian intensif, pohon AVL lebih cepat daripada pohon merah-hitam karena mereka lebih seimbang. Mirip dengan pohon merah-hitam, pohon AVL seimbang tinggi. Keduanya, secara umum, tidak seimbang berat atau seimbang untuk setiap mu <1/2; yaitu, saudara kandung node dapat memiliki sangat besar jumlah keturunan yang berbeda. "
• WAVL . The kertas asli menyebutkan keuntungan dari versi yang dalam hal batas pada operasi rebalancing dan rotasi.

Lihat juga

Pertanyaan serupa pada CS: Apa perbedaan antara pohon pencarian biner dan tumpukan biner?

Dengan struktur data seseorang harus membedakan tingkat perhatian.

1. The struktur abstrak Data (benda yang tersimpan, operasi mereka) dalam pertanyaan ini berbeda. Satu mengimplementasikan antrian prioritas, yang lain satu set. Antrian prioritas tidak tertarik untuk menemukan elemen yang berubah-ubah, hanya elemen dengan prioritas terbesar.

2. The konkrit pelaksanaan struktur. Di sini pada pandangan pertama keduanya adalah pohon (biner), dengan sifat struktural yang berbeda. Baik urutan relatif kunci dan struktur global yang mungkin berbeda. (Agak tidak tepat, dalam BSTkunci diperintahkan kiri-ke-kanan, dalam tumpukan mereka diperintahkan top-down.) Sebagai IPlant dengan benar menyatakan tumpukan juga harus "lengkap".

3. Ada perbedaan akhir dalam implementasi tingkat rendah . Pohon pencarian biner (tidak seimbang) memiliki implementasi standar menggunakan pointer. Biner heap sebaliknya memiliki implementasi yang efisien menggunakan array (justru karena struktur terbatas).

Di atas jawaban sebelumnya, heap harus memiliki properti struktur heap; pohon harus penuh, dan lapisan paling bawah, yang tidak selalu penuh, harus diisi paling kiri ke kanan tanpa celah.