Bagaimana cara memilih antara tabel hash dan pohon pencarian seimbang?

Tabel hash memberikan pencarian dan penyisipan O(1) yang diharapkan tetapi tidak ada urutan, sementara pohon pencarian seimbang memberikan operasi O(log n) dan menjaga kunci tetap terurut, mendukung kueri rentang dan penelusuran terurut. Pilih hashing untuk pencarian kunci murni dan pohon ketika pengurutan atau operasi rentang penting.

Apa arti biaya amortisasi untuk struktur data?

Biaya amortisasi adalah biaya rata-rata per operasi selama urutan operasi kasus terburuk. Larik dinamis, misalnya, kadang-kadang membayar O(n) untuk mengubah ukuran tetapi rata-rata O(1) per penambahan karena perubahan ukuran jarang terjadi relatif terhadap penambahan yang murah.

Struktur Data Fundamental

Struktur data fundamental adalah cara terorganisir untuk menyimpan dan mengakses data — larik, daftar tertaut, tabel hash, pohon, tumpukan, dan kerabatnya — yang menentukan efisiensi operasi yang dibangun di atasnya.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Struktur data adalah cara mengatur dan menyimpan data sehingga operasi yang didefinisikan oleh tipe data abstraknya dapat dilakukan secara efisien; struktur data fundamental adalah kumpulan kecil struktur serbaguna yang darinya sebagian besar struktur lain dibangun.

Scope

Area ini mencakup tipe data abstrak (daftar, kamus, antrean prioritas, himpunan) dan struktur konkret yang mengimplementasikannya, bersama dengan biaya operasi intinya (sisipkan, hapus, cari, perbarui) di bawah analisis kasus terburuk dan amortisasi. Ini membahas bagaimana pilihan struktur membentuk kinerja algoritma dan terhubung ke paradigma desain serta algoritma graf dan string yang bergantung pada struktur ini. Ini tidak termasuk struktur penyimpanan basis data dan sistem file yang ditangani di subbidang lain.

Sub-topics

Core questions

Tipe data abstrak apa yang dibutuhkan suatu aplikasi, dan struktur konkret mana yang paling baik mengimplementasikannya?
Berapa biaya kasus terburuk dan amortisasi dari setiap operasi pada struktur tertentu?
Bagaimana struktur menukar memori dengan waktu, atau kecepatan baca dengan kecepatan pembaruan?
Bagaimana mempertahankan invarian (keterurutan, keseimbangan, properti tumpukan) membatasi biaya operasi?
Kapan struktur sederhana lebih disukai daripada struktur yang secara asimtotik lebih cepat tetapi lebih kompleks?

Key concepts

tipe data abstrak
larik dan daftar tertaut
tumpukan dan antrean
tabel hash
pohon pencarian biner
pohon seimbang
tumpukan dan antrean prioritas
analisis amortisasi
pertukaran waktu-ruang

Key theories

Tipe data abstrak versus implementasi: Tipe data abstrak menentukan operasi dan semantiknya secara independen dari representasi; beberapa struktur data konkret dapat mengimplementasikan ADT yang sama dengan profil kinerja yang berbeda, memungkinkan perancang untuk mempertimbangkan kebenaran dan biaya secara terpisah.
Analisis amortisasi: Beberapa struktur (larik dinamis, pohon splay) memiliki operasi mahal sesekali tetapi operasi murah rata-rata dalam suatu urutan; analisis amortisasi (metode agregat, akuntansi, potensial) membatasi biaya rata-rata ini secara ketat.

Clinical relevance

Struktur data fundamental adalah blok bangunan dari hampir semua perangkat lunak: tabel hash mendukung kamus dan indeks basis data, pohon seimbang dan pohon B mengatur sistem file dan basis data, antrean prioritas menggerakkan penjadwal dan simulasi peristiwa, dan pilihan struktur yang tepat sering kali menentukan apakah suatu sistem dapat diskalakan.

History

Struktur data dasar dikatalogkan dalam The Art of Computer Programming karya Knuth mulai tahun 1968. Pohon penyeimbang otomatis (pohon AVL, 1962; pohon merah-hitam dan pohon B pada tahun 1970-an) dan struktur canggih seperti tumpukan Fibonacci dan pohon splay (1980-an, sebagian besar karena Tarjan dan kolaborator) memperluas bidang ini, sementara analisis amortisasi memberikan penjelasan yang ketat tentang kinerjanya.

Key figures

Donald Knuth
Robert Sedgewick
Robert Tarjan
Rudolf Bayer

Seminal works

knuth1997vol1
cormen2009
sedgewick2011

Frequently asked questions

Bagaimana cara memilih antara tabel hash dan pohon pencarian seimbang?: Tabel hash memberikan pencarian dan penyisipan O(1) yang diharapkan tetapi tidak ada urutan, sementara pohon pencarian seimbang memberikan operasi O(log n) dan menjaga kunci tetap terurut, mendukung kueri rentang dan penelusuran terurut. Pilih hashing untuk pencarian kunci murni dan pohon ketika pengurutan atau operasi rentang penting.
Apa arti biaya amortisasi untuk struktur data?: Biaya amortisasi adalah biaya rata-rata per operasi selama urutan operasi kasus terburuk. Larik dinamis, misalnya, kadang-kadang membayar O(n) untuk mengubah ukuran tetapi rata-rata O(1) per penambahan karena perubahan ukuran jarang terjadi relatif terhadap penambahan yang murah.