struktur data

Variabel dan Tipe Data
Sebuah program sewajarnya membutuhkan sebuah tempat penampung untuk data yang digunakan oleh program tersebut. Dari sisi programmer, penampung tersebut berbentuk variabel. Bergantung pada bahasa pemrograman yang dipergunakan, variabel dapat memiliki tipe data atau tidak.
Berbeda pada sisi komputer. Program yang berjalan akan menggunakan memori sebagai penampung data. Bagi komputer, data apa pun yang terdapat pada memori akan diperlakukan sama. (Ingat, bahwa komputer hanya dapat mengolah data binary, yang hanya terdiri dari 0 dan 1) Jadi bagi komputer tidak ada gambar, tulisan, suara atau yang lainnya.
Lalu bagaimana hubungan antara penampung pada bahasa pemrograman dan komputer?
Variabel pada dasarnya adalah suatu cara untuk memberi label / nama / alias pada suatu alamat memori. Penggunaan variabel bertujuan untuk mempermudah programmer dalam mengakses memori. Sekaligus karena programmer tidak tahu akan menggunakan memori pada alamat yang mana (karena hal ini diatur oleh OS, dan bukan oleh bahasa pemrograman).
Sementara tipe data adalah cara suatu bahasa pemrograman untuk mengartikan data yang terletak pada memori. Jadi data yang sama dapat diartikan berbeda oleh bahasa pemrograman ketika memiliki tipe data yang berbeda.

Contoh
Data 1 pada memori, pada pemrograman .NET dapat memiliki arti
- 1 pada tipe data integer.
- 1 Januari 1753 pada tipe data DateTime.
Array
Pada beberapa kasus dibutuhkan data yang sifatnya array. Data yang memiliki beberapa tipe data yang sama yang berurutan. Berurutan di sini berlaku baik pada pengaksesan dari bahasa pemrograman, mau pun pada pengaturan memori.
Beberapa sifat dari array, antara lain
- Hanya menggunakan satu variabel.
- Diakses secara berurutan dengan menggunakan index (nomor urut).
- Untuk menampung data dengan tipe data yang sama.
- Memiliki jumlah elemen yang tetap, tanpa menghiraukan apakah elemen tersebut ‘isi’ atau ‘kosong’.
Pencarian Dalam Array (Searching)
Ada beberapa algoritma standar dalam melakukan searching, tetapi hampir semua tidak mampu untuk melakukan pencarian secara baik pada semua kondisi. Suatu algoritma dapat lebih baik pada kondisi tertentu tapi akan tidak baik pada kondisi lainnya.
Pada bagian ini hanya akan dibahas 2 metode searching.
1. Sequential Searching
Sequential searching melakukan pencarian dengan cara mencari urut dari elemen pertama dari array hingga elemen terakhir. Jika sebelum elemen terakhir maka pencarian dihentikan. Karena apa pun yang terjadi pencarian berakhir, maka dibutuhkan variabel untuk mengetahui apakah pencarian berhasil atau tidak.
Teknik ini sebenarnya adalah pencarian yang paling ‘bodoh’. Performa yang dilakukan juga tidak baik, karena pada kasus terburuk, dibutuhkan waktu sebanyak jumlah data dan tidak ditemukan data. Hanya saja pada akhirnya, teknik ini adalah teknik yang paling efektif.
Beberapa program pada akhirnya menggunakan cara ini karena dianggap paling berhasil. Untuk menambah performa biasanya ditambahkan teknik tambahan, misalnya dengan membuat index dari data atau membuat dictionary terlebih dahulu.
2. Binary Searching
Pada binary searching, pencarian dilakukan dengan membagi data menjadi 2 bagian, lalu melakukan searching ke masing-masing bagian. Jika data yang dicari sudah ditemukan maka selesai. Jika data yang dicari lebih kecil, maka pergi ke bagian kiri dari data. Jika data yang dicari lebih besar, maka pergi ke bagian kanan dari data.
Binary searching sangat efektif dan efisien dalam melakukan pencarian data. Dengan n kali pencarian maka dapat dilakukan pencarian data sebanyak maksimum 2n -1.
Kelemahan utama dari binary searching adalah bahwa data harus sudah terurut terlebih dahulu. Jika data belum terurut maka harus diurutkan (sorting) terlebih dahulu. Masalahnya proses sorting adalah proses yang memakan banyak waktu. Belum lagi bahwa data tertentu harus dibiarkan tetap dalam urutan seperti apa adanya (misal data kependudukan).

Sorting

Sama halnya dengan searching, pada sorting juga terdapat beberapa algoritma pencarian yang standar, tapi tidak ada yang benar-benar ideal. Bahkan pada beberapa kasus, hasil sorting tidak harus urut, hanya ‘cukup terurut’, biasanya hal ini dilakukan untuk mendapatkan kecepatan sorting.
Berbeda dengan algoritma searching yang maksimum pencarian adalah sebanyak banyaknya data (jadi untuk 8 data, maksimum pencarian dilakukan sebanyak 8 kali), proses sorting bisa menjadi sangat ‘melelahkan’. Karenanya proses sorting menjadi lebih sulit untuk dilakukan.
Berikut adalah beberapa algoritma sorting.
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
Value Type vs Reference Type
Nilai dari sebuah variabel dapat berupa value type atau pun reference type. Pada value type, variabel menyimpan nilai secara langsung. Sedang pada reference type variabel menyimpan alamat memori yang meyimpan nilai. Sehingga variabel tersebut hanya menyimpan referensi saja, dan bukannya nilainya sendiri.
Pada bahasa pemrograman tertentu, reference type dapat dilakukan dengan penggunaan pointer. Hanya saja kebanyakan bahasa pemrograman terkini tidak lagi mengijinkan penggunaan pointer sehubungan dengan kemungkinan terjadinya error akibat manajemen memori yang buruk.
Value Type
A 100  nilai dari variabel A
Reference Type
B 200  alamat dari memori yang menyimpan data
200 100  nilai yang disimpan pada lokasi memori yang beralamat 200
Linked List
Sekalipun array sangat berguna, tapi array memiliki beberapa kelemahan, yaitu
- Jumlah elemen yang tetap. Sehingga penggunaan memori tidak dapat optimal, karena baik terpakai atau tidak memori akan tetap dialokasikan.
- Jumlah elemen yang tetap juga menyulitkan programmer, karena banyak data yang tidak diketahui banyaknya.
- Array harus berurutan. Sehingga sekalipun total jumlah memori bebas mencukupi, tapi jika memori bebas tersebut terbagi-bagi maka bisa saja memori dianggap tidak mencukupi.

Linked list dapat berarti menggabungkan / ‘mengaitkan’ satu data dengan data lainnya. Dengan cara ini maka ukuran / jumlah elemen dapat berubah-ubah. Demikian pula pemakaian memori dapat lebih fleksibel karena tidak harus berurutan.
Hanya saja kelebihan array harus dibayar dengan operasi yang lebih rumit.
Menghapus data di akhir linked list. (variabel bantuan B mengacu pada node SEBELUM node yang dicari. )
Menghapus data di tengah linked list. (variabel bantuan B mengacu pada node SEBELUM node yang dicari.)
Stack

Stack adalah salah satu struktur data yang cukup tua. Stack memiliki implementasi yang sangat sederhana, dan masih dipertahankan untuk beberapa hardware, karena keterbatasan dari hardware yang bersangkutan.
Pada stack, penambahan data (push) dilakukan pada awal stack, dan pengambilan data (pop) juga dilakukan dari awal stack pula. Dengan arsitektur seperti ini maka operasi data pada stack bersifat LIFO (Last In First Out).
Queue

Queue berarti antrian. Berbeda dengan stack, proses penambahan data (enqueue) dilakukan pada akhir queue dan pengambilan data (dequeue) dilakukan pada awal antrian. Karena bekerja dengan cara yang sama persis dengan antrian maka operasi data pada queue bersifat FIFO (First In First Out).
Queue banyak diimplementasikan pada manajemen process, routing dan sebagainya.
Tree

Tree atau pohon adalah struktur data yang juga sangat sering digunakan pada sistem komputer. Ide dasarnya sebenarnya menyerupai linked list yang memanfaatkan reference type variabel untuk mengaitkan satu variabel dengan variabel lainnya. Hanya saja pada tree, satu variabel biasanya dikaitkan dengan lebih satu variabel lainnya.

Pada tree, suatu titik disebut dengan node. Bentuk tree mengembang ke bawah. Node paling atas disebut dengan nama root node (node akar). Sementara node yang paling bawah disebut dengan nama leave node (node daun). Node di atas node lain disebut dengan parent (induk), sementara node di bawah node lain disebut dengan child (anak).


File

Selain pada memory, data juga dapat pula disimpan secara lebih permanen (persistence) pada media penyimpanan seperti harddisk. Data dalam bentuk seperti disebut file. Pada kondisi ini data hanya memiliki satu bentuk, yaitu data serial. Data serial berarti data berbentuk urutan, sehingga data hanya dapat dibaca secara berurutan dari awal hingga akhir. File memiliki dua buah format, yaitu teks dan binary.
File teks, berarti bahwa file hanya dapat menyimpan data teks. Teks di sini dapat dalam encoding 1 byte (ASCII) atau 2 byte (Unicode / UTF).
Sementara file binary berarti bahwa data disimpan dalam bentuk binary. Encoding yang digunakan dapat sangat beragam, dan tidak ada format yang tetap.
Berikut adalah perbandingan antara keduanya
File Teks :
- Mudah untuk ‘dibaca’ baik oleh program maupun oleh manusia
- Hanya dapat diisi data teks murni (plain text). Misal file txt, xml, html dsb.
- Satuan data terkecil memiliki ukuran tetap. Biasanya 1 byte / 2 byte.
- Bersifat universal, dapat dipindahkan pada platform yang berbeda tanpa banyak masalah.
File Binary
- Lebih sulit untuk dibaca. Bagi manusia, dibutuhkan program tambahan untuk dapat ‘membaca’ data pada file binary.
- Dapat menyimpan bentuk data yang lebih beragam. Misal exe, doc, mp3, jpg, mpg dsb.
- Satuan data terkecil memiliki ukuran yang dinamis. Beberapa menggunakan Huffman Code sebagai metode penentuannya
- Bersifat proprietary, pemindahan data pada platform yang berbeda dapat mengakibatkan data tidak terbaca, bahkan rusak.
TREE (Pohon)
Dalam ilmu komputer, tree adalah sebuah struktur data yang secara bentuk menyerupai
sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan. Node-
node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat memiliki 0 atau lebih node
anak (child). Sebuah node yang memiliki node anak disebut node induk (parent). Sebuah
node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer, tree bertumbuh
ke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node
anak akan digambarkan berada di bawah node induknya.Node yang berada di pangkal tree disebut node root (akar), sedangkan node yang berada paling ujung pada piramida tree disebut node leaf (daun).Binary Tree (Pohon Biner)Dalam mata kuliah struktur data, secara khusus akan dipelajari mengenai pohon biner. Pohon biner adalah sebuah tree yang pada masing-masing simpulnya hanya dapat memiliki maksimum 2 (dua) simpul anak. Tidak boleh lebih. Pada pohon biner, umumnya kedua node anak disebut dengan posisinya, yaitu kiri dan kanan.
Beberapa istilah pada pohon biner:
- Size (ukuran): jumlah total node yang terdapat pada pohon biner tersebut.
- Depth (kedalaman): panjang jalur yang menghubungkan sebuah node sampai ke
node anaknya yang paling ujung (leaf). Depth biasa juga disebut height.
Full Binary Tree (Pohon Biner Penuh) adalah pohon biner yang setiap nodenya pasti memiliki
0 atau 2 node anak.
Perfect Binary Tree (Pohon Biner Sempurna) adalah pohon biner yang semua node leafnya
berada pada kedalaman yang sama dari node root. Juga disebut sebagai Complete Binary
Tree (Pohon Biner Lengkap)
Almost Complete Binary Tree (Pohon Biner Hampir Lengkap) adalah pohon biner yang setiap
nodenya dapat memiliki 0 node anak, atau memiliki kiri, atau jika memiliki kanan harus
memiliki kiri. Tidak boleh memiliki kanan saja.
Implementasi
Implementasi dalam pemrograman, dalam pokok bahasan ini akan dibicarakan untuk pohon
biner saja. Asumsi awal adalah data yang hendak dimasukkan ke dalam node, bertipe data
integer.
1. Deklarasi Tree
Karena tree tersusun oleh node-node, maka yang perlu kita deklarasikan adalah
komponen node itu sendiri. Dalam contoh dibawah, akan kita namai Node.
Sebelumnya perlu kita lihat bahwa untuk mewujudkan implementasi node ke dalam
bahasa pemrograman, diperlukan sebuah struktur yang memiliki susunan berikut ini:
Variabel data digunakan untuk menyimpan nilai angka node tersebut, sedangkan kiri dan
kanan, bertipe pointer, masing-masing mewakili vektor yang akan menunjuk ke node
anak kiri dan kanan.
2. Inisialisasi Tree
Untuk pertama kali, saat kita akan membuat sebuah pohon biner, asumsi awal adalah
pohon itu belum bertumbuh, belum memiliki node sama sekali, sehingga masih kosong.
Oleh karena itu perlu kita tambahkan kode berikut pada baris awal prosedur Main:
3. Menambahkan Node Pada Tree
Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk
menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan
penambahan node pada pohon biner:
1. Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.
2. Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan
berikut:
a. Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke
kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node
baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi,
lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini
dilakukan seterusnya hingga node baru dapat ditempatkan.
b. Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke
kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan),
maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan
node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan
tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat
ditempatkan.
4. Membaca dan Menampilkan Node Pada Tree
Untuk membaca dan menampilkan seluruh node yang terdapat pada pohon biner,
terdapat 3 macam cara, atau yang biasa disebut kunjungan (visit). Semua kunjungan
diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan
perulangan proses yang sama namun untuk depth yang berbeda, maka ketiganya
diimplementasikan dengan prosedur rekursif.
a. Kunjungan Pre-Order.
Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan:
1. Cetak isi (data) node yang sedang dikunjungi
2. Kunjungi kiri node tersebut,
- Jika kiri bukan kosong (NULL) mulai lagi dari langkah pertama, terapkan untuk
kiri tersebut.
- Jika kiri kosong (NULL), lanjut ke langkah ketiga.
3. Kunjungi kanan node tersebut,
- Jika kanan bukan kosong (NULL) mulai lagi dari langkah pertama, terapkan
untuk kanan tersebut.
- Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses
yang sama untuk node yang dikunjungi sebelumnya.
b. Kunjungan In-Order.
1. Kunjungi kiri node tersebut,
- Jika kiri bukan kosong (NULL) mulai lagi dari langkah pertama, terapkan untuk
kiri tersebut.
- Jika kiri kosong (NULL), lanjut ke langkah kedua.
2. Cetak isi (data) node yang sedang dikunjungi
3. Kunjungi kanan node tersebut,
- Jika kanan bukan kosong (NULL) mulai lagi dari langkah pertama, terapkan
untuk kanan tersebut.
- Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses
yang sama untuk node yang dikunjungi sebelumnya.
c. Kunjungan Post-Order.
1. Kunjungi kiri node tersebut,
- Jika kiri bukan kosong (NULL) mulai lagi dari langkah pertama, terapkan untuk
kiri tersebut.
- Jika kiri kosong (NULL), lanjut ke langkah kedua.
2. Kunjungi kanan node tersebut,
- Jika kanan bukan kosong (NULL) mulai lagi dari langkah pertama, terapkan
untuk kanan tersebut.
- Jika kanan kosong (NULL), lanjut ke langkah ketiga.
3. Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai,
tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.
Variabel **root pada setiap fungsi diatas menunjukkan node mana yang sedang
dikunjungi saat ini, untuk itu saat pemanggilan, variabel **root kita beri nilai pointer yang
menunjuk ke node akar, yaitu pohon.