Struktur data dijelaskan

Setiap program menyimpan data di suatu tempat, dan cara menyimpannya menentukan apa yang cepat dan apa yang lambat. Daftar sejuta nama bisa diperiksa nama demi nama, atau ditata sehingga dua puluh perbandingan cukup untuk menemukan nama apa pun. Struktur data adalah penataan semacam itu: segelintir gagasan, kebanyakan lebih tua daripada komputer pribadi, yang ada di dalam setiap basis data, sistem operasi, browser, dan gim.

Pohon pencarian biner berwarna merah-hitam, tumpukan kotak, deretan ember hash dengan rantai kunci yang bertabrakan, dan panah yang menghubungkan simpul-simpul sebuah senarai
Pohon pencarian biner berwarna merah-hitam, tumpukan kotak, deretan ember hash dengan rantai kunci yang bertabrakan, dan panah yang menghubungkan simpul-simpul sebuah senarai

Untuk apa struktur data

Struktur data dipilih berdasarkan pertanyaan yang harus dijawabnya. Riwayat panggilan ponsel butuh panggilan terbaru lebih dulu, tugas printer butuh yang tertua lebih dulu, kamus butuh arti satu kata di antara seratus ribu, perencana rute butuh persimpangan terdekat yang belum dikunjungi. Setiap struktur mempercepat sebagian operasi dengan mengorbankan yang lain, dan notasi O besar menggambarkan tawar-menawar itu: O(1) berarti waktu tidak bertambah seiring jumlah butir n, O(log n) berarti melipatgandakan n menambah satu langkah, dan O(n) berarti waktu tumbuh sebanding dengan n.

Tumpukan, antrean, dan deque

Tumpukan menambah dan mengambil di ujung yang sama: terakhir masuk, pertama keluar. Riwayat urungkan, tombol kembali, dan panggilan fungsi program yang sedang berjalan adalah tumpukan. Antrean menambah di belakang dan mengambil di depan: pertama masuk, pertama keluar, seperti ketukan papan ketik atau antrean cetak. Deque mengizinkan keduanya di kedua ujung. Ketiganya butuh waktu konstan per operasi. Antrean sering disimpan dalam penyangga melingkar, sebuah larik tetap tempat depan dan belakang berputar kembali setelah slot terakhir; bila penuh, butir-butirnya disalin ke larik dua kali lebih besar. Penyalinan berbiaya O(n), tetapi begitu jarang terjadi sehingga setiap operasi tetap rata-rata O(1), yang disebut batas teramortisasi.

Senarai berantai

Senarai berantai menyimpan setiap nilai dalam simpul yang punya penunjuk ke simpul berikutnya. Menyisipkan atau menghapus hanya membelokkan satu atau dua penunjuk, tidak ada yang perlu digeser, tetapi kita tidak bisa melompat ke simpul kesepuluh: kita mengikuti tautan dari kepala. Senarai yang hanya menyimpan kepalanya mencapai ekor dalam O(n) langkah; senarai sungguhan biasanya juga menyimpan penunjuk ekor, dan senarai berantai ganda punya penunjuk ke belakang, begitulah riwayat browser atau cache LRU dibangun.

Pohon pencarian biner

Pohon pencarian biner menyimpan, di setiap simpul, nilai yang lebih kecil di subpohon kiri dan yang lebih besar di subpohon kanan. Pencarian membandingkan lalu ke kiri atau ke kanan, dan penelusuran in-order membaca nilai secara terurut. Menghapus daun cukup dengan mencabutnya, simpul dengan satu anak digantikan oleh anak itu, dan simpul dengan dua anak digantikan oleh penerus in-order-nya, nilai terkecil di subpohon kanannya. Semua ini butuh waktu sebanding dengan tinggi pohon: sekitar log n bila pohonnya rimbun, tetapi n bila nilai datang terurut dan pohon merosot menjadi senarai.

Pohon AVL dan merah-hitam

Pohon yang menyeimbangkan diri memperbaiki bentuknya setelah setiap perubahan. Pohon AVL, yang ditemukan Adelson-Velsky dan Landis pada 1962, menjaga tinggi kedua subpohon setiap simpul berselisih paling banyak satu; bila faktor keseimbangan sebuah simpul mencapai ±2, satu rotasi (kasus LL dan RR) atau dua (LR dan RL) memulihkannya. Pohon merah-hitam mewarnai simpulnya sehingga akarnya hitam, tidak ada simpul merah yang punya anak merah, dan setiap jalur ke bawah melewati jumlah simpul hitam yang sama, yang menjaga jalur terpanjang paling banyak dua kali jalur terpendek. Ia memperbaiki diri dengan mewarnai ulang dan paling banyak beberapa rotasi, dan inilah pohon di dalam TreeMap Java, std::map C++, dan penjadwal Linux.

Heap dan antrean prioritas

Heap biner adalah pohon biner lengkap yang disimpan dalam larik tanpa penunjuk: anak dari posisi i ada di 2i + 1 dan 2i + 2. Dalam min-heap, setiap induk paling besar sama dengan anak-anaknya, jadi nilai terkecil selalu ada di akar. Nilai baru diletakkan di akhir dan naik melewati induk yang lebih besar; mengambil akar memindahkan nilai terakhir ke puncak lalu menurunkannya. Keduanya berbiaya O(log n), dan seluruh larik bisa dijadikan heap dalam O(n). Heap menggerakkan antrean prioritas dalam jalur terpendek Dijkstra, simulasi kejadian, dan penjadwal sistem operasi, serta menghasilkan heap sort.

Tabel hash

Tabel hash mengubah kunci menjadi indeks larik dengan fungsi hash dan langsung menuju ke sana. Kunci yang berbeda bisa jatuh di indeks yang sama: itulah tabrakan. Rantai menyimpan senarai kecil di setiap ember; pengalamatan terbuka, seperti probing linear, mencoba slot-slot berikutnya sampai menemukan yang bebas, dan saat sebuah kunci dihapus harus meninggalkan batu nisan agar pencarian berikutnya terus melakukan probe. Dengan fungsi hash yang baik dan faktor muatan (kunci per ember) yang dijaga rendah dengan memperbesar tabel, penyisipan, pencarian, dan penghapusan rata-rata berbiaya O(1). Fungsi yang buruk, seperti menjumlahkan kode karakter sebuah kata, mengirim anagram ke ember yang sama. Tabel hash ada di balik dict Python, objek JavaScript, dan indeks basis data.

Trie dan union-find

Trie, atau pohon prefiks, menyimpan untai dengan satu karakter per tingkat, sehingga kata dengan awal yang sama berbagi jalur dan sebuah simpul menandai tempat kata berakhir. Menemukan kata sepanjang L butuh L langkah, berapa pun banyaknya kata yang tersimpan, dan semua kata dengan prefiks tertentu berada dalam satu subpohon; begitulah pelengkapan otomatis dan pemeriksa ejaan bekerja. Union-find menyimpan elemen dalam himpunan saling lepas, masing-masing sebuah pohon yang akarnya menamai himpunan itu. Find mengikuti tautan induk sampai ke akar; union menggantung satu akar di bawah akar lain. Dengan gabung menurut peringkat dan kompresi jalur, serangkaian panjang operasi berbiaya hampir konstan per operasi, yaitu fungsi Ackermann invers α(n), yang paling banyak 4 untuk n realistis mana pun. Algoritma Kruskal untuk pohon rentang minimum bertumpu padanya.

Pertanyaan yang sering diajukan

Apa beda larik dan senarai berantai?

Larik menyimpan butirnya berdampingan di memori, jadi setiap posisi bisa dicapai seketika, tetapi menyisipkan di tengah berarti menggeser semua yang ada di belakangnya. Senarai berantai bisa menyisipkan di mana saja dengan mengubah penunjuk, tetapi mencapai sebuah posisi berarti berjalan dari kepala. Larik juga jauh lebih baik memanfaatkan cache prosesor, itulah sebabnya dalam praktik biasanya lebih cepat.

Apa arti waktu teramortisasi?

Biaya rata-rata per operasi atas serangkaian panjang operasi, walaupun satu operasi kadang mahal. Penyangga melingkar yang berlipat ganda saat penuh sesekali menyalin semua n butir, tetapi karena penyalinan makin jarang seiring penyangga membesar, n penambahan berbiaya total O(n), jadi rata-rata O(1) per penambahan.

Apakah heap sama dengan pohon pencarian biner?

Tidak. Pohon pencarian biner menempatkan setiap subpohon kiri sebelum simpulnya dan setiap subpohon kanan sesudahnya, jadi ia bisa mendaftar semua nilai secara terurut dan menemukan nilai apa pun dengan cepat. Heap hanya menjanjikan bahwa setiap induk datang sebelum anak-anaknya, yang cukup untuk langsung menemukan minimum atau maksimum, tetapi tidak untuk mencari sembarang nilai.

Bagaimana union-find tahu apakah dua elemen terhubung?

Ia mengikuti tautan induk dari setiap elemen sampai ke akar pohonnya. Jika keduanya tiba di akar yang sama, mereka berada di himpunan yang sama. Setelah itu kompresi jalur membuat setiap simpul di jalur itu menunjuk langsung ke akar, sehingga pertanyaan berikutnya tentang mereka cukup satu langkah.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka visualisasi struktur data