Struktur Data: Panduan Komprehensif dengan Contoh Python

Struktur data ada di dunia digital maupun fisik. Kamus adalah contoh fisik struktur data, di mana data berupa definisi kata yang diatur secara alfabetis dalam sebuah buku. Pengorganisasian ini memungkinkan kueri spesifik: dengan diberikan sebuah kata, seseorang dapat mencari definisinya.

Pada intinya, struktur data adalah metode pengorganisasian data yang memfasilitasi jenis kueri dan operasi tertentu pada data tersebut.

Kita akan mulai dengan membahas struktur data linear seperti array, list, queue, dan stack. Lalu, kita akan kembali menjelaskan perbedaan antara struktur linear dan non-linear sebelum membahas hash table, tree, dan graph.

Jika Anda ingin belajar lebih lanjut, lihat kursus ini tentang struktur data dan algoritma di Python.

Array

Array adalah struktur data fundamental yang tersedia luas di berbagai bahasa pemrograman. Array memungkinkan penyimpanan sejumlah nilai tetap (N) secara berurutan di memori.

Elemen array diindeks dari elemen pertama pada indeks (0) hingga elemen terakhir pada indeks (N-1).

Array memungkinkan operasi berikut:

1. Membaca nilai pada indeks tertentu.
2. Memperbarui nilai pada indeks tertentu.
3. Melakukan iterasi atas semua nilai yang disimpan.
4. Memperoleh ukuran array.

Array sangat efektif dalam skenario di mana jumlah nilai yang akan disimpan diketahui sebelumnya, dan operasi utama melibatkan pembacaan dan penulisan data pada indeks tertentu.

Pertimbangkan skenario di mana Anda perlu menyimpan pembacaan suhu harian untuk bulan Desember. Anda mungkin ingin memungkinkan pengguna mengambil suhu untuk hari tertentu dan melakukan berbagai analisis statistik atas suhu sepanjang bulan.

Karena jumlah hari dalam Desember diketahui sebelumnya, yaitu 31, array merupakan pilihan yang sangat baik untuk menyimpan pembacaan suhu. Awalnya, kita membuat array dengan 31 posisi kosong. Lalu, setelah memperoleh setiap pembacaan suhu, suhu untuk hari tertentu ditetapkan ke indeks array yang sesuai: hari 1 disimpan pada indeks 0, hari 2 pada indeks 1, dan seterusnya hingga hari 31 pada indeks 30.

Mengakses indeks yang bersesuaian memungkinkan pengambilan suhu untuk hari tertentu. Statistik, seperti suhu rata-rata, dapat ditentukan dengan melakukan iterasi atas semua elemen, menjaga jumlah kumulatif, lalu membaginya dengan ukuran array.

Array tidak tersedia secara native di Python. Array digunakan di balik layar sebagai struktur dasar untuk berbagai tipe data, tetapi tidak didukung langsung dalam bahasa tersebut. Untuk menggunakan array secara eksplisit, Anda dapat memanfaatkan pustaka seperti array, yang menawarkan implementasi array. Namun, sering kali lebih praktis menggunakan list dengan ukuran tetap dalam situasi di mana array mungkin diperlukan. List menawarkan fleksibilitas dan merupakan bagian inti dari fungsionalitas Python, yang akan kita bahas selanjutnya.

Kita dapat membuat list untuk mensimulasikan array 31 elemen, masing-masing diinisialisasi ke None, dengan menggunakan [None] * 31. Di sini, None menunjukkan bahwa belum ada pembacaan suhu yang direkam.

december_temperatures = [None] * 31

Untuk menetapkan nilai pada indeks tertentu, kita menggunakan december_temperatures[index], di mana index adalah angka dari 0 hingga 30. Misalnya, untuk mencatat suhu pada hari pertama (disimpan pada indeks 0), kita melakukannya seperti ini:

december_temperatures[0] = 15

Mengakses suhu juga sama mudahnya, menggunakan december_temperatures[index].

print(december_temperatures[0])

15

List

Bayangkan sekarang, alih-alih berfokus pada Desember, kita memasang sensor untuk mengambil pembacaan suhu berkala selama periode yang tidak ditentukan. Dalam skenario ini, menggunakan array bukanlah pilihan terbaik karena kita bisa kehabisan ruang akibat ukurannya yang tetap saat dibuat.

Struktur data yang lebih sesuai dalam skenario ini adalah list. Ada dua jenis list:

• Array list
• Linked list

Array list

Array list dapat dipandang sebagai versi array yang lebih fleksibel. Array list dapat melakukan semua fungsi yang dilakukan array, tetapi juga dapat menambahkan nilai baru, sehingga ukurannya tidak tetap saat dibuat. Array list berkaitan dengan penggunaan list() di Python.

Implementasinya bergantung pada penggunaan array yang diperluas ketika ruang habis, oleh karena itu disebut array list. Namun, seperti yang kita pelajari sebelumnya, array tidak dapat bertambah, jadi bagaimana hal ini mungkin?

Ketika array dasar dari sebuah array list penuh dan kita ingin menambahkan nilai baru, array yang lebih besar dibuat di balik layar. Semua nilai sebelumnya disalin ke array baru yang lebih besar ini. Lalu, nilai baru ditambahkan pada posisi pertama yang tersedia di array baru tersebut.

Bayangkan kita ingin menambahkan nilai 71 ke array ini:

Hal ini dapat dilakukan seperti berikut:

Jumlah ruang baru yang dialokasikan setiap kali kita melakukan operasi ini sangat krusial bagi kinerja array list. Jika pada setiap penambahan elemen kita membuat array dengan hanya satu posisi baru untuk nilai yang ditambahkan, itu berarti setiap operasi append memerlukan penyalinan seluruh data yang sudah ada. Ini akan sangat tidak efisien—bayangkan harus menyalin jutaan record hanya untuk menambahkan satu yang baru.

Sebagai gantinya, strategi umum adalah menggandakan ukuran array setiap kali dibutuhkan ruang lebih. Pendekatan ini terbukti menetralkan dampak langkah penyalinan ekstra ini seiring waktu.

Untuk menambahkan elemen ke list Python, kita menggunakan metode .append(). Berikut contoh cara membuat list kosong dan menambahkan satu pembacaan suhu ke dalamnya:

temperatures = []
temperatures.append(35)

Linked list

Untuk menstrukturkan data di komputer, kita memerlukan cara untuk mengaitkan nilai satu sama lain. Array melakukannya dengan mengalokasikan lokasi memori yang bersebelahan—artinya lokasi memori yang berurutan—dan menyimpan nilai secara sekuensial. Bayangkan seperti deretan rumah di sebuah jalan: setiap rumah memiliki alamat unik (indeks), dan lokasinya bersebelahan secara fisik.

Namun, ini bukan satu-satunya metode untuk mengorganisasi data. Alternatifnya adalah menggunakan struktur berbasis node.

Node adalah objek yang menyimpan sebuah nilai bersama dengan referensi ke node lain. Misalnya, untuk membuat struktur mirip list menggunakan node, kita dapat memiliki sebuah node yang menyimpan nilai dan referensi ke elemen berikutnya dalam list. Di Python, ini dapat diimplementasikan dengan sebuah kelas:

class Node:
    def __init__(self, value, next_node):
        self.value = value
        self.next_node = next_node

Dengan pendekatan ini, seseorang dapat membuat list dengan menautkan nilai-nilai melalui referensi next_node. Berikut cuplikan kode yang membuat list dengan nilai 42, 17, dan 37:

node_37 = Node(37, None) # There's no node after 37 so next_node is None
node_17 = Node(17, node_37)
node_42 = Node(42, node_17)

Menautkan node secara manual seperti ini tidaklah praktis. Implementasi sesungguhnya memerlukan pembuatan kelas lain yang mempertahankan referensi ke node pertama dan terakhir dari list. Untuk menambahkan nilai baru, kita:

1. Membuat node dengan nilai yang diinginkan.
2. Menetapkan node baru ini sebagai node berikutnya dari node terakhir saat ini.
3. Memperbarui referensi node terakhir ke node yang baru ditambahkan ini.

Bayangkan kita ingin menambahkan nilai 71 ke array contoh kita:

Ini dapat dilakukan seperti berikut:

class LinkedList:
    def __init__(self):
        self.first_node = None
        self.last_node = None

    def append(self, value):
        node = Node(value, None)
        if self.first_node is None:
            self.first_node = node
            self.last_node = node
        else:
            self.last_node.next_node = node
            self.last_node = node

Berbeda dengan array list, kita tidak dapat mengakses nilai langsung berdasarkan indeksnya. Untuk membaca nilai tertentu pada suatu indeks, kita harus mulai dari node pertama dan bergerak berurutan dari satu node ke node berikutnya hingga mencapai indeks yang diinginkan. Proses ini jauh lebih lambat daripada akses langsung. Jika kita memiliki jutaan nilai yang disimpan dalam list, kita perlu membaca jutaan nilai di memori untuk mencapai indeks tertentu.

Keunggulan linked list terletak pada kemampuan untuk menambahkan dan menghapus elemen secara instan dari bagian depan atau belakang list. Kemampuan ini membuka kemungkinan untuk mengimplementasikan dua struktur data baru: queue dan stack, yang akan kita bahas selanjutnya.

Queue

Bayangkan Anda mengembangkan aplikasi restoran yang mencatat pesanan pelanggan dan meneruskannya ke dapur. Saat pelanggan tiba di restoran, mereka akan mengantre untuk memesan, dengan harapan dilayani sesuai urutan kedatangan. Ini berarti pelanggan pertama dalam antrean harus menerima pesanannya terlebih dahulu, dan pelanggan terakhir akan menerima pesanannya terakhir.

Di dapur, koki lebih suka fokus pada satu pesanan dalam satu waktu, jadi aplikasi sebaiknya hanya menampilkan pesanan saat ini. Setelah sebuah pesanan selesai dan dikirim, pesanan berikutnya dalam antrean harus ditampilkan.

Kita dapat menafsirkan kebutuhan di atas sebagai perlunya struktur data yang mendukung operasi berikut:

1. Menambahkan elemen.
2. Melihat elemen yang ditambahkan pertama kali.
3. Menghapus elemen yang ditambahkan pertama kali.

Operasi ini persis seperti yang ditawarkan oleh queue. Queue dapat diimplementasikan menggunakan linked list, di mana elemen ditambahkan dengan menempelkannya ke list. Karena elemen diurutkan berdasarkan waktu kedatangan, node pertama selalu menjadi yang harus dilayani berikutnya.

Berikut cara pesanan di atas akan disimpan dalam queue:

Setelah sebuah pesanan siap, pesanan tersebut dapat dihapus dengan memperbarui elemen pertama ke next_node-nya, dengan asumsi ada node berikutnya. Node pertama yang baru menjadi node kedua sebelumnya:

Queue digambarkan sebagai struktur data first-in, first-out (FIFO) karena elemen yang pertama kali ditambahkan juga yang pertama kali dihapus. Dalam contoh restoran kita, pelanggan yang pertama datang juga yang pertama dilayani (dan dihapus dari daftar koki).

Untuk menggunakan queue di Python, kita dapat memanfaatkan koleksi deque dari modul collections. Impor modul ini dan buat queue kosong seperti di bawah:

from collections import deque
orders = deque()

Menambahkan elemen baru ke belakang queue dapat dilakukan menggunakan metode .append():

orders.append("burger")
orders.append("sunday")
orders.append("fries")

Untuk mengambil dan menghapus pesanan berikutnya dari depan queue, kita menggunakan metode .popleft():

orders.append("burger")
orders.append("sunday")
orders.append("fries")

burger
sunday
fries

Stack

Dalam situasi tertentu, kita menginginkan perilaku yang berlawanan dengan queue—kita justru ingin melacak elemen yang paling terakhir ditambahkan.

Sebagai contoh, bayangkan Anda diminta menambahkan fitur undo ke editor gambar. Ini memerlukan cara untuk memantau tindakan pengguna, dengan menyediakan akses ke operasi yang paling baru. Hal ini karena fungsionalitas undo biasanya membalikkan tindakan mulai dari yang terakhir dilakukan dan bergerak ke arah yang pertama.

Stack adalah tepatnya struktur data yang mendukung operasi berikut:

1. Menambahkan elemen.
2. Melihat elemen yang terakhir ditambahkan.
3. Menghapus elemen yang terakhir ditambahkan.

Seperti queue, stack juga dapat diimplementasikan menggunakan linked list. Menambahkan elemen tetap dilakukan dengan menempelkannya ke list. Namun, fokus kita beralih ke elemen terakhir dalam list, bukan yang pertama. Untuk mengambil elemen terbaru, kita melihat elemen terakhir list. Menghapus elemen terakhir mengharuskan kita menghapus elemen terakhir tersebut.

Dalam struktur node kita, kita hanya melacak node berikutnya. Untuk memfasilitasi penghapusan elemen terakhir, kita perlu mengakses elemen yang mendahuluinya, menghapus next_node-nya, dan menjadikan node tersebut sebagai yang terakhir. Kita dapat mencapainya dengan memodifikasi struktur node agar juga melacak node sebelumnya dari setiap node. Linked list seperti ini disebut doubly linked list.

Stack digambarkan sebagai struktur data last-in, first-out (LIFO) karena elemen yang terakhir ditambahkan juga yang pertama kali dihapus.

Untuk menggunakan stack di Python, kita dapat memanfaatkan koleksi yang sama, deque. Kita menggunakan metode .append() untuk menambahkan elemen baru:

from collections import deque
actions = deque()

actions.append("crop")
actions.append("desaturate")
actions.append("resize")

Untuk mengambil dan menghapus perintah berikutnya dari puncak stack, kita menggunakan metode .pop():

print(actions.pop())
print(actions.pop())
print(actions.pop())

resize
desaturate
crop

Struktur Data Linear vs. Non-linear

Sejauh ini, kita telah mengeksplorasi lima struktur data: array, array list, linked list, queue, dan stack. Masing-masing adalah struktur data linear karena elemennya diatur dalam urutan, dengan setiap elemen memiliki elemen sebelumnya dan berikutnya yang jelas.

Selanjutnya, kita akan beralih fokus ke struktur data non-linear. Tidak seperti tipe linear, struktur ini tidak mengorganisasi elemen bersebelahan secara linear. Akibatnya, mereka tidak memiliki konsep elemen sebelumnya dan berikutnya yang terdefinisi. Sebagai gantinya, mereka membangun jenis hubungan yang berbeda di antara elemen.

Karakteristik ini membuatnya sangat cocok untuk mengeksekusi kueri khusus pada data dengan efisiensi tinggi, alih-alih sekadar menjadi sarana menyimpan data di memori.

Hash table

Kita memulai artikel ini dengan membahas contoh nyata dari struktur data: kamus. Ternyata, mengorganisasi data sehingga dapat dicari berdasarkan suatu kolom spesifik (misalnya, mencari definisi berdasarkan kata) sangat berguna secara umum, sehingga ilmuwan komputer juga menciptakan struktur data yang memfasilitasi hal ini.

Untuk memahami struktur data ini, mari kita lihat bagaimana kita dapat membuat kamus virtual—yakni, struktur data di mana kita dapat:

1. Menambahkan kata beserta definisinya.
2. Dengan diberikan sebuah kata, mencari definisinya.

Ingat contoh pencatatan suhu sepanjang Desember. Kita menggunakan array dengan 31 elemen yang bersesuaian dengan setiap hari dalam bulan untuk menyimpan suhu pada indeks masing-masing. Pendekatan ini memungkinkan pencarian suhu untuk hari apa pun secara efisien.

Skenario ini mirip dengan menangani pasangan data (day, temperature), di mana tujuannya adalah mengambil temperature dengan menentukan hari. Demikian pula, dalam kasus kamus, kita menangani pasangan data (word, definition) dan bertujuan menemukan definition ketika diberikan sebuah word.

Pasangan seperti itu disebut pasangan key-value atau entri. Key adalah parameter yang digunakan dalam kueri pencarian, dan value adalah hasil dari kueri tersebut.

Yang menghalangi kita menggunakan array untuk masalah kamus adalah bahwa key kita berupa string, bukan angka. Dengan key numerik, kita dapat langsung menggunakan array untuk mengasosiasikan key dan value dengan menempatkan value pada indeks yang sesuai.

Untuk menyelesaikan masalah ini, pertama-tama kita perlu mengonversi kata menjadi angka. Fungsi yang melakukan konversi ini disebut fungsi hash. Ada banyak pendekatan untuk membuat fungsi semacam itu. Misalnya, kita bisa menetapkan nilai numerik ke huruf, dengan a sebagai 1, b sebagai 2, c sebagai 3, dan seterusnya, lalu menjumlahkan nilai-nilai ini.

Sebagai contoh, kata data akan dihitung sebagai 4 + 1 + 20 + 1 = 26. Namun, fungsi ini memiliki kekurangan, yang akan kita bahas sebentar lagi. Rincian tentang bagaimana merancang fungsi hash yang efektif berada di luar tujuan artikel ini, tetapi Python secara praktis menyediakan fungsi hash() yang menangani tugas ini secara efisien untuk kita.

hash("data")

-6138587229816301269

Dalam contoh di atas, Anda mungkin memperhatikan bahwa fungsi hash menghasilkan angka negatif. Perlu dicatat bahwa indeks array yang positif berkisar dari 0 hingga N - 1. Setelah kita mengonversi key menjadi angka, kita dapat memetakannya ke rentang 0 hingga N - 1 menggunakan operator modulo % (yang menghasilkan sisa pembagian—misalnya, 10 % 3 menghasilkan 1).

Sebagai catatan sampingan, fungsi hash() Python dapat mengembalikan nilai yang berbeda di berbagai eksekusi program. Fungsi ini hanya deterministik dalam satu kali eksekusi program yang sama, artinya Anda mungkin mengamati nilai hash yang berbeda untuk objek yang sama jika Anda menjalankan program beberapa kali.

Pertimbangkan sebuah array yang berisi 100 elemen. Untuk menemukan indeks yang bersesuaian dengan string "data", kita lakukan hal berikut:

hash("data") % 100

31

Struktur data hash table pada dasarnya adalah array besar yang menyimpan pasangan key-value pada indeks yang ditentukan dengan menerapkan fungsi hash pada key.

Karena keterbatasan ruang, diagram di atas hanya menyertakan singkatan "def" untuk mewakili definisi. Namun, dalam praktiknya, elemen kedua dari setiap entri adalah definisi lengkap dari kata tersebut.

Ada aspek penting lain yang perlu dipertimbangkan. Mengingat jumlah kata jauh lebih dari 100, jika kita terus menambahkan kata, kata-kata berbeda pada akhirnya akan menghasilkan nilai hash yang sama. Untuk mengatasinya, alih-alih membatasi setiap elemen array pada satu pasangan key-value, kita memanfaatkan linked list untuk menyimpan semua entri yang memiliki nilai hash yang sama.

Ketika dua entri menghasilkan hash yang sama, ini disebut collision. Skenario ini sedikit memodifikasi proses pencarian. Setelah menghitung kode hash, perlu menelusuri list untuk menemukan entri yang benar. Meskipun pendekatan ini memperlambat operasi pencarian, dapat ditunjukkan bahwa menggunakan ukuran array awal yang cukup besar (lebih besar dari 100) dan fungsi hash yang dirancang dengan baik dapat sangat mengurangi dampak collision. Akibatnya, efisiensinya tetap hampir setara dengan array.

Untuk fungsi hash yang dirancang secara efektif, menemukan nilai berbeda yang menghasilkan hash yang sama seharusnya jarang terjadi. Inilah mengapa fungsi hash sederhana yang hanya menjumlahkan nilai numerik karakter dalam sebuah kata tidak ideal. Dua kata mana pun yang tersusun dari huruf yang sama, terlepas dari urutannya, akan menghasilkan kode hash yang identik. Misalnya, “listen” dan “silent” akan menghasilkan hash yang sama. Sebaliknya, fungsi hash bawaan Python jauh lebih andal dan dirancang khusus untuk meminimalkan collision.

Hash table bisa dibilang merupakan struktur data terpenting yang tersedia. Struktut ini sangat efisien dan serbaguna. Di Python, hash table diimplementasikan melalui kelas dict(). Karena kemiripannya dengan kamus, di Python struktur data ini memang disebut dictionary alih-alih hash table.

Demi kesederhanaan, contoh kita berfokus pada penambahan dan pencarian entri. Secara umum, dictionary menawarkan fleksibilitas lebih dan mendukung operasi tambahan, termasuk penghapusan. Untuk membuat dictionary (hash table) kosong di Python, Anda dapat menggunakan {} seperti ini:

word_definitions = {}
word_definitions["data"] = "Facts or information."

Anda dapat mengakses definisi sebuah kata dengan menggunakan kata tersebut sebagai key, seperti ini:

print(word_definitions["data"])

Facts or information.

Tree

Bayangkan Anda mengembangkan situs web untuk agen real estat. Tugas Anda adalah membuat fitur yang memungkinkan pengguna memfilter listing berdasarkan harga. Fitur tersebut harus memungkinkan pengguna untuk:

1. Menemukan listing termurah.
2. Menemukan listing termahal.
3. Menemukan semua listing di bawah harga tertentu.

Biasanya, proses ini melibatkan penelusuran semua listing rumah dan menyaring yang berada di luar rentang harga yang diinginkan. Namun, tujuan kita adalah mengembangkan solusi yang dapat diskalakan lebih efisien, yang tidak memerlukan pemeriksaan seluruh dataset untuk menemukan listing yang relevan. Tree adalah struktur data yang tepat untuk menjawab jenis kueri ini.

Tree adalah struktur data berbasis node, seperti linked list. Namun, alih-alih memiliki referensi previous dan next, setiap node akan menyimpan sebuah nilai dan dua referensi: node kiri dan node kanan.

Dalam contoh situs web agen real estat kita, setiap node akan merepresentasikan sebuah listing properti. Untuk mengoptimalkan kueri terkait harga, kita akan menetapkan aturan: listing dengan harga lebih rendah selalu disimpan di sisi kiri sebuah node, sedangkan listing dengan harga lebih tinggi selalu disimpan di sisi kanan.

Sebagai contoh konkret, pertimbangkan tree berikut yang menyimpan nilai 42, 17, 73, 4, 22, dan 89.

Untuk setiap node, semua node di kiri memiliki nilai yang lebih kecil, dan semua yang di kanan memiliki nilai yang lebih besar. Tree yang memenuhi properti ini disebut binary search tree (BST). Disebut binary karena setiap node merujuk ke paling banyak dua node lain, yang disebut child. Kata search berasal dari fakta bahwa properti pengurutan pada child kiri dan kanan memungkinkan pencarian tree secara efisien.

Kita sudah dapat melihat bagaimana BST membantu dengan cepat menemukan listing termurah dan termahal. Karena pengurutan nilai, yang termurah selalu merupakan node paling kiri, dan yang termahal adalah node paling kanan.

Ini menyiratkan bahwa kita dapat menemukannya tanpa memeriksa sebagian besar data. Mulai dari node teratas, yang juga disebut node root, kita secara konsisten mengikuti tautan ke kiri untuk mengidentifikasi nilai minimum dan ke kanan untuk mengidentifikasi nilai maksimum. Artinya, hanya node di sepanjang jalur yang menghubungkan root ke node minimum dan maksimum yang perlu diperiksa.

Bayangkan kita ingin menemukan semua node dengan nilai setidaknya 50. Langkah-langkah berikut dapat kita ambil untuk mencapainya:

• Mulai dari root, kita bandingkan target, 50, dengan nilai root, yakni 42.
• Melihat bahwa 50 lebih besar, kita paham bahwa root dan semua node di kirinya berisi nilai yang lebih kecil. Konsekuensinya, kita dapat mengabaikannya.
• Kemudian kita berlanjut ke node di kanan root, yaitu 73. Setelah dibandingkan, kita dapati bahwa 50 lebih kecil dari 73. Ini menunjukkan bahwa semua node di kanan node 73 memenuhi kriteria kita.
• Namun, karena 73 tidak memiliki child kiri, pencarian kita berakhir di sana.

Kita sudah dapat melihat bagaimana BST secara signifikan mempercepat kueri. Bahkan dalam contoh kecil ini, kita menghindari memeriksa setengah dari data.

Secara umum, mengidentifikasi semua node dalam BST yang sesuai dengan rentang tertentu memerlukan pemeriksaan sejumlah node yang mendekati jumlah hasil kueri. Ini adalah keuntungan besar dibandingkan harus memeriksa setiap titik data. Bayangkan memiliki 1.000.000 listing dan kueri yang menghasilkan hanya 10 hasil. Menggunakan list, seseorang harus memeriksa satu juta listing untuk menyaring yang tidak sesuai rentang. Dengan BST, seseorang hanya perlu memeriksa sekitar 10 listing. Ini merepresentasikan faktor percepatan sebesar 100.000.

Efisiensi BST sangat bergantung pada keseimbangan tree. Jika kita menambahkan nilai yang sama seperti sebelumnya, dari yang terkecil ke yang terbesar—4, 17, 22, 42, 73, kemudian 89—kita bisa berakhir dengan tree yang tidak seimbang, seperti berikut:

Ingat bahwa, untuk menemukan nilai maksimum dalam BST, kita mulai dari root dan menelusuri tautan ke kanan hingga mencapai node yang tidak memilikinya. Dalam kasus tree yang tidak seimbang, seperti yang diilustrasikan di atas, proses ini mengharuskan memeriksa setiap node. Idealnya, kita menginginkan node terdistribusi merata antara sisi kiri dan kanan. Menjelaskan detail tentang bagaimana penyeimbangan ini dapat dicapai secara konsisten berada di luar cakupan artikel ini. Jenis binary search tree yang dikenal menjaga keseimbangan seperti itu disebut AVL tree.

Paket avltree menyediakan implementasi AVL tree. Cuplikan kode di bawah menunjukkan bagaimana kita dapat menggunakannya pada dataset listing rumah ini, subset yang telah dibersihkan dari USA Real Estate Dataset ini.

import csv
from avltree import AvlTree as Tree

# Load the listings CSV data
with open("listings.csv", "rt") as f:
    reader = csv.reader(f)
    listings = list(reader)

# Create the tree based on the price column (column index 2)
tree = Tree()
for listing in listings[1:]:
    price = float(listing[2])
    tree[price] = listing

# Display the cheapest listing price
print("Cheapest:", tree.minimum())

# Display the most expensive listing price
print("Most expensive:", tree.maximum())

# Display the number of listings whose price is between 100,000 and 110,000
listings_in_range = list(tree.between(100000, 110000))
print("Num listings between 100000 and 110000:", len(listings_in_range))

Cheapest: 50017.0
Most expensive: 19999900.0
Num listings between 100000 and 110000: 403

Pertama, kita menggunakan modul csv untuk membaca dataset listings.csv. Selanjutnya, kita membuat AVL tree berdasarkan kolom harga. Lalu, kita menggunakan metode minimum(), maximum() dan between() untuk menentukan harga minimum, harga maksimum, dan jumlah listing yang harganya antara $100.000 dan $110.000.

Graph

Struktur data terakhir yang akan kita bahas dalam artikel ini adalah graph.

Misalkan Anda menganalisis data dari sebuah platform media sosial. Data ini terdiri dari daftar pengguna dan pertemanan di antara mereka, dan tujuan Anda adalah mengidentifikasi komunitas dalam jejaring sosial tersebut. Meskipun konsep komunitas dapat didefinisikan dengan berbagai cara, secara umum mengacu pada sekelompok pengguna yang memiliki sejumlah besar hubungan pertemanan di dalam kelompok itu.

Graph adalah struktur data ideal untuk merepresentasikan data ketika kita memiliki entitas dan hubungan antar pasangan entitas tersebut. Dalam contoh kita, entitasnya adalah pengguna, dan hubungannya adalah pertemanan mereka.

Graph adalah struktur berbasis node. Namun, tidak seperti linked list dan tree yang menunjukkan koneksi linear atau hierarkis antar node, sebuah graph memungkinkan node mana pun terhubung ke banyak node lain. Koneksi antar node, yang disebut edge, menunjukkan adanya hubungan di antara mereka.

Dalam contoh jejaring sosial kita, setiap pengguna dapat divisualisasikan sebagai sebuah node. Sebuah edge dapat digambar di antara dua node untuk menandakan pertemanan antara pengguna yang bersangkutan.

Diagram di atas menggambarkan sebuah graph yang merepresentasikan pertemanan dalam jejaring sosial kecil. Node merepresentasikan pengguna dan diberi label nama mereka, sementara edge merepresentasikan hubungan pertemanan. Misalnya, Anna berteman dengan Steve, Claire, dan Jack, yang berarti ada edge yang menghubungkan node Anna ke node ketiga orang tersebut.

Operasi yang seharusnya didukung oleh struktur data graph meliputi:

1. Menambahkan node baru.
2. Menghubungkan dua node dengan sebuah edge.
3. Mengambil semua node yang terhubung ke node tertentu.

Cara umum untuk mengimplementasikan graph adalah dengan menggunakan hash table dan list. Sebuah hash table dibuat dengan satu entri untuk setiap node. Key dari setiap entri adalah node, dan value-nya adalah list yang berisi semua node yang terhubung ke node tersebut.

Paket networkx menawarkan implementasi Python untuk membuat dan memanipulasi graph. Selain itu, pustaka networkx mencakup beragam algoritma graph, termasuk untuk deteksi komunitas. Mari kita gunakan untuk membangun graph yang disebutkan sebelumnya dan menerapkan algoritma deteksi komunitas yang populer untuk melihat hasilnya.

Untuk memulai pembuatan graph, kita mulai dengan mengimpor pustaka networkx dan menginisialisasi graph kosong:

import networkx as nx
G = nx.Graph()

Node dapat ditambahkan menggunakan metode add_node().

G.add_node("Anna")
G.add_node("Steve")
G.add_node("Jack")
G.add_node("Claire")
G.add_node("Bob")
G.add_node("Jane")
G.add_node("John")
G.add_node("Rute")
G.add_node("Alex")

Edge dapat ditambahkan menggunakan metode add_edge().

G.add_edge("Anna", "Steve")
G.add_edge("Anna", "Jack")
G.add_edge("Anna", "Claire")
G.add_edge("Steve", "Claire")
G.add_edge("Claire", "Jack")
G.add_edge("Jack", "Bob")
G.add_edge("Bob", "John")
G.add_edge("Bob", "Jane")
G.add_edge("John", "Jane")
G.add_edge("Rute", "Alex")

Dengan graph kita yang telah dibuat, kita dapat menghitung komunitas di dalamnya. Beberapa algoritma dirancang untuk deteksi komunitas, dan dalam hal ini, kita akan menggunakan metode Louvain. Algoritma deteksi komunitas dapat ditemukan di subpaket community dari networkx. Secara khusus, kita akan fokus pada fungsi louvain_communities().

Berikut cara menggunakannya:

communities = nx.community.louvain_communities(G)
print(communities)

[{'Jack', 'Claire', 'Anna', 'Steve'}, {'Bob', 'John', 'Jane'}, {'Rute', 'Alex'}]

Keluaran berupa list of set, dengan setiap set merepresentasikan sebuah komunitas. Kita mengamati bahwa algoritma mendeteksi tiga komunitas, yang sesuai dengan ekspektasi kita mengingat struktur graph-nya.

Untuk mempelajari lebih lanjut tentang graph, pelajari cara mengimplementasikan algoritme Dijkstra di Python.

Memilih Struktur Data yang Tepat

Saat memperkenalkan setiap struktur data, kami menyajikan daftar operasi yang didukung. Operasi ini menjadi panduan kapan harus menggunakan struktur data tersebut, karena struktur tersebut dirancang untuk menjalankan operasi ini secara efisien.

Sebagai contoh, Python list() juga mendukung operasi tambahan, seperti menghapus elemen. Namun, operasi ekstra ini bukanlah keunggulan array list. Secara khusus, menghapus elemen dari tengah list memerlukan penyalinan semua data (kecuali elemen yang dihapus) ke list baru, yang bisa sangat memakan waktu.

Ketika data secara alami diindeks dengan angka, dan jumlah entri diketahui (misalnya, hari dalam sebulan), array biasanya menjadi pilihan yang disukai. Untuk pengindeksan yang lebih umum atau set data dinamis, dictionary adalah solusi alternatif yang baik.

Untuk memproses data secara sekuensial, satu entri pada satu waktu, queue atau stack sering digunakan, tergantung pada urutan pemrosesan data yang diinginkan.

Tree biasanya menjadi jawaban ketika kita ingin melakukan kueri yang lebih kompleks pada data, seperti menemukan semua entri dalam rentang tertentu atau nilai ekstrem.

Terakhir, ketika ada relasi antar pasangan titik data, graph adalah cara efektif untuk menyimpan dan merepresentasikan relasi tersebut. Ada algoritma graph yang memungkinkan kita menjawab pertanyaan umum tentang dataset dengan relasi berpasangan seperti ini.

Struktur data merupakan domain yang sangat luas, dan kita baru membahas sebagian kecil saja. Dalam situasi tertentu, solusinya adalah merancang struktur data baru yang sepenuhnya disesuaikan dengan masalah yang dihadapi. Namun demikian, mengenal struktur data yang dibahas dalam artikel ini seharusnya mengarahkan Anda ke jalur yang tepat saat menyelesaikan masalah terkait data Anda.

Kesimpulan

Dalam artikel ini, kita telah mempelajari bahwa struktur data adalah metode mengorganisasi data dalam format tertentu untuk memfasilitasi pengambilan informasi yang efisien.

Ada dua jenis struktur data yang mendasar: struktur berbasis array (misalnya hash table) dan struktur berbasis node (misalnya graph).

Struktur linear, seperti array, queue, dan stack, mengorganisasi elemen secara berurutan. Sebaliknya, struktur non-linear, seperti hash table, tree, dan graph, mengorganisasi data berdasarkan hubungan di dalam data.

Pilihan struktur data yang tepat bergantung pada sifat kueri yang akan dijalankan.

Jika Anda ingin mempelajari berbagai struktur data di Python, lihat tutorial ini tentang struktur data Python.