| Operasi | Rata-rata | Kasus terburuk |
|---|
* teramortisasi: dirata-ratakan atas serangkaian panjang operasi
Visualisasi struktur data
Struktur data adalah cara menyimpan data sehingga pertanyaan yang paling sering diajukan bisa dijawab dengan cepat. Pilih salah satu dari sebelas struktur klasik, dari tumpukan sampai pohon merah-hitam, ketik nilai, lalu tekan sebuah operasi. Setiap langkah berlangsung di layar: simpul mana yang dibandingkan, tautan mana yang berubah, mengapa pohon berotasi atau nilai naik, disertai kalimat yang menyebutkan apa yang terjadi. Ubin menghitung kerja setiap operasi, dan tabel memberikan waktu jalannya. Pilih sebuah struktur, ketik nilai, lalu tekan sebuah operasi. Setiap operasi diputar langkah demi langkah: simpul yang disorot menunjukkan apa yang dibandingkan, dipindahkan, atau diubah, dan baris di bawah gambar menjelaskan apa yang terjadi dan mengapa. Mundur, Langkah, Putar, dan Akhir menelusuri langkah-langkah itu lagi. Isi acak dan Kosongkan memulai dari awal, dan Urungkan membatalkan satu operasi. Ubin menampilkan ukuran, tinggi pohon, kerja operasi terakhir (perbandingan, probe, atau tautan induk yang diikuti) dan satu angka yang penting bagi struktur itu; tabel memberikan waktu jalan setiap operasi.
Cara kerjanya
- Pilih sebuah struktur, misalnya pohon pencarian biner, tabel hash, atau trie. Ia dimulai dengan isi acak; Isi acak dan Kosongkan memulai dari awal.
- Ketik nilai dan tekan sebuah operasi: push, masukkan ke antrean, sisipkan, hapus, cari, penelusuran, union, atau find. Langkah-langkahnya berputar sendiri; Mundur, Langkah, Putar, dan Akhir menelusurinya lagi.
- Baca di baris bawah gambar apa yang dilakukan setiap langkah, perhatikan ukuran, tinggi, dan kerja operasi terakhir di ubin, lalu bandingkan waktu jalan di tabel.
Senarai, tumpukan, dan antrean
Struktur paling sederhana menyimpan butir dalam satu baris. Tumpukan hanya bekerja di satu ujung, jadi butir yang terakhir masuk keluar paling dulu, seperti tumpukan piring; antrean menambah di belakang dan mengambil di depan, seperti antrean di loket. Antrean di sini tinggal di penyangga melingkar: depan dan belakang berputar di sebuah larik tetap dan kembali ke awal setelah ujungnya, dan bila penuh, butir-butirnya disalin ke penyangga dua kali lebih besar. Senarai berantai menghubungkan simpul dengan penunjuk, jadi menyisipkan di kepala nyaris tanpa biaya, tetapi untuk menemukan ekor atau sebuah indeks kita harus mengikuti tautan satu per satu.
Pohon, heap, tabel hash, dan himpunan
Pohon pencarian biner menyimpan nilai yang lebih kecil di kiri dan yang lebih besar di kanan, sehingga pencarian memangkas separuh kandidat di setiap langkah, selama pohonnya tetap rimbun. Pohon AVL dan merah-hitam memastikannya dengan rotasi yang bisa Anda saksikan dan yang dinamai menurut kasusnya. Heap hanya menyimpan nilai terkecil atau terbesar di atas, dan hanya itu yang dibutuhkan antrean prioritas. Tabel hash langsung melompat ke ember yang dihitung dari kunci dan harus menangani tabrakan; trie berbagi prefiks kata; union-find menjawab dalam waktu hampir konstan apakah dua elemen termasuk himpunan yang sama.
Pertanyaan yang sering diajukan
Struktur data mana yang sebaiknya saya pakai?
Tergantung pertanyaan yang paling sering Anda ajukan. Tumpukan atau antrean bila butir diproses sesuai urutan datang atau kebalikannya; tabel hash untuk mencari kunci; pohon pencarian seimbang seperti pohon AVL atau merah-hitam bila Anda juga butuh kunci terurut atau kunci terdekat; heap bila Anda hanya pernah butuh butir terkecil atau terbesar; trie untuk kata dan prefiks; union-find untuk melacak kelompok yang bergabung.
Apa beda pohon AVL dan pohon merah-hitam?
Keduanya menjaga pohon pencarian biner tetap dangkal, sehingga setiap pencarian, penyisipan, dan penghapusan butuh waktu sebanding dengan log n. Pohon AVL diseimbangkan lebih ketat, dengan tinggi kedua sisi setiap simpul berselisih paling banyak satu, sehingga pencarian sedikit lebih cepat. Pohon merah-hitam memberi kelonggaran lebih dan butuh lebih sedikit rotasi saat berubah, itulah sebabnya banyak pustaka standar memakainya untuk map dan set terurut.
Mengapa tabel hash bisa lambat pada kasus terburuk?
Jika banyak kunci jatuh ke ember yang sama, pencarian harus memeriksanya satu per satu, persis seperti senarai. Fungsi hash yang baik menyebarkan kunci secara merata dan tabel membesar sebelum terlalu penuh, sehingga pencarian rata-rata butuh waktu konstan. Coba ukuran tabel 10 dengan bilangan yang berakhiran angka sama, atau kata-kata yang saling anagram, lalu lihat tabrakan menumpuk.
Apa arti angka di samping simpul AVL?
Itu faktor keseimbangan: tinggi subpohon kiri sebuah simpul dikurangi tinggi subpohon kanannya. Dalam pohon AVL, setiap faktor keseimbangan harus −1, 0, atau +1. Bila penyisipan atau penghapusan membuat salah satunya +2 atau −2, pohon berotasi di simpul itu; kasusnya (LL, RR, LR, atau RL) menunjukkan ke arah mana tinggi berlebih itu condong dan menentukan apakah perlu satu atau dua rotasi.
Apakah ada yang dikirim ke server?
Tidak. Setiap operasi berjalan di browser Anda, dan isi setiap struktur disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor