Linked list - Binery Search Tree

LINKED LIST

Linked list adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu computer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibuthkan. Linked list mirip dengan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time). Didalam banyak aplikasi, ukuran dari data tidak diketahui data compile, hal ini bisa merupakan suatu atribut yang baik juga. Setiap node akan berbentuk struct dan memiliki  satu buah field yang bertipe struct yang sama, yang berfungsi sebagai pointer. Dalam menghubungkkan setiap node, kita dapat menggunakan cara first-create-first-access maupun first-create-last-access. Linked list saling terhubung dengan bantuan variable pinter. Masing-masing data dalam linked list disebut dengan node (simpul) yan menempati alokasi memori secar dinamis dan biasanya berupa struct yang terdiri dari beberapa field.

List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. 

Biasanya didalam suatu linked list, terdapat istilah head dan tail:

-Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

-Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Merupakan suatu struktur data pengembangan dari konsep ADT (Abstrak Data Type) yang bersifat dinamis. Linked List dapat dimanfaatkan secara effektif sesuai dengan keperluan. Linked List juga dapat benar – benar dihapus / dibersihkan dari memory.Linked List sebenarnya merupakan suatu typedata tersendiri. Di bahasa Java, Linked List bisa berupa suatu Class ataupun Record. Ciri – ciri utama dari Linked List adalah, dia mempunyai minimal dua elemen utama.

Ada beberapa macam Linked List, yaitu :

-        Single Linked List:

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

-        Double Linked List:

 Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

-        Circular Linked List:

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu : Circular Single Linked List dan Circular Double Linked List.

-        Multiple Linked List:

Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer.

STACK & QUEUE

Stack merupakan tumpukan, sedangkan queue merupakan antrian.

Pengertian keduanya, yaitu:

     Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Stack (tumpukan) sebenarnya secara mudah dapat diartikan sebagai list (urutan) dimana penambahan dan pengambilan elemen hanya dilakukan pada satu sisi yang disebut top (puncak) dari stack.

Dengan melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan LIFO (Last In First Out), yaitu elemen yang terakhir masuk akan pertama kali diambil atau dilayani. Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau barang lain. Pada saat kita hendak menumpuk piring-piring tersebut tentulah yang kita lakukan adalah meletakkan piring pertama pada tempatnya, selsnjutnya meletakkan piring kedua di atas piring pertama dan demikian seterusnya. Pada saat kita hendak mengambil satu piring dari tumpukan tersebut, tentu yang diambil adalah piring teratas (yang terakhir kali ditaruh), bukan yang terbawah (yang pertama kali diletakkan).

Dua operasi dasar pada stack adalah PUSH (operasi pemasukan elemen ke dalam stack) dan POP (operasi pengambilan satu elemen dari dalam stack).

Contoh dalam Kehidupan sehari-hari :

-        Setumpuk koran, dimana koran yang paling terakhir ditambahkan dan ditaruh diatas adalah koran yang dapat dilihat

-        Seseorang yang sedang mencuci piring, piring yang dicuci pertama pasti akan diletakan dibawah dan akan terus berlanjut sampai tumpukan piring yang terakhir dicuci. Lalu, piring pasti akan di taruh di rak piring dan pasti yang diambil adalah piring yang paling atas yaitu piring yang terakhir dicuci dan yang pertama dicuci pasti akan terakhir.

-        Tumpukan Batu bata yang sedang diturunkan dari mobil pasti yang diambil adalah batu bata yang paling atas, padahal batu bata pertama yang dimasukkan kedalam mobil adalah batu bata yang berada dibawahnya.

Jadi, Stack yaitu sebuah koleksi objek yang menggunakan prinsip LIFO(Last In First Out) dan Stack dapat diimplementasikan sebagai representasi berkait atau kontinyu. Ciri-Ciri Stack diantaranya :

-        Elemen TOP/Puncak diketahui

-        Penyisipan dan Penghapusan selalu dilakukan di TOP

-        LIFO(Last In First Out) 

-        Pemanfaatan Stack yaitu :

Ø  Perhitungan Ekspresi Aritmatitika (posfix)

Ø  Algoritma Backtracking (runut balik)

Ø  Algoritma Rekursif

Operasi Stack yang biasa digunakan diantaranya yaitu :

1.      Push untuk memasukkan atau menginputkan data

2.      Pop  untuk mengeluarkan data

3.      IsFull untuk mengetahui jika tumpikan sudah penuh

4.      IsEmpety untuk mengetahui tumpukan yang kosong, dan

5.      Clear untuk menghapus seluruh data atau membersihkan data. 

     Queue atau antrian sebenarnya juga merupakan suatu list. Salah satu sifat yang membedakan queue dengan stack adalah bahwa pada queue penambahan elemen dilakukan pada salah satu ujung (ujung depan) dan pengambilan dilakukan pada ujung yang lain (ujung belakang) . Dengan demikian queue menggunakan prinsip FIFO (First In First Out), yaitu elemen yang pertama masuk akan pertama kali pula dikeluarkan. Seperti pada stack, operasi-operasi dasar pada queue adalah operasi penambahan elemen ( sebut "ADDQ") dan operasi pengambilan elemen (sebut DELQ). Di bawah ini diberikan contoh pemakaian operasi PUSH dan POP dan isi stack untuk setiap selesai eksekusi satu operasi.

Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru. Sebuah struktur data dari sebuah queue setidaknya harus mengandung dua tiga variabel, yakni variabel head yang akan berguna sebagai penanda bagian depan antrian, variabeltail yang akan berguna sebagai penanda bagian belakang antrian dan array dari yang akan menyimpan data-data yang dimasukkan ke dalam queue tersebut.

Queue mempunyai beberapa fungsi operasi diantaranya yaitu :

-        EnQueue untuk Memasukkan data kedalam Antrian

-        DeQueue untuk Mengeluarkan data kedalam Antrian.

-        IsFull untuk memeriksa apakah antrian Penuh

-        IsEmpety untuk memeriksa apakah antrian Kosong

-        Clear untuk Menghapus seluruh Antrian.

Dalam kehidupan sehari-hari, ada banyak sekali tentang Queue atau antrian. Contohnya adalah sebagai berikut:

·        Saat seseorang mengantri di sebuah Bank

·        Antrian Loket pembelian sebuah tiket Pesawat, Kereta Api, dan lainnya

·        Pembayaran Tol dan sebagainya.

Contoh dalam Pembelian Tiket Kereta Api :

·        Enqueue  : Seseorang membeli tiket melalui tempat pembayaran tiket yang disediakan.

·        Dequeue  : Setelah membeli tiket, langsung menuju tempat tunggu Kereta Api, dengan sebelumnya petugas memeriksa cek tiket tersebut.

·        Clear    : Pembeli tiket tersebut telah terhapus dari antrian karena sudah melewati pembayaran administrasi tersebut.

·        IsEmpty  : Petugas tiket Kereta  Api melihat tidak ada lagi yang ingin membeli tiket kereta.

·        IsFull       : Petugas Tiket Kereta Api melihat masih ada pembeli tiket kereta.

HASH TABLE & BINARY TREE

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

Hash table itu sebenarnya hanya array biasa saja, hanya penempatan posisi nilainya itu tergantung fungsi hash dari kuncinya.

Karena posisinya sudah ditentukan dengan fungsi hash, kita sudah tidak perlu mikir lagi taruh di posisi array sebelah mana. Pokoknya kita tahunya kunci dan nilainya.

class Map:

  def __init__(self):

    self.data = [None] * 30

  def set(self, key, value):

    self.data[hash(key) % len(self.data)] = value

  def get(self, key):

    return self.data[hash(key)]

Kita bisa menggunakan fungsi hash apapun yang dapat memastikan tiap kunci itu unik, tapi karena keterbatasan ukuran array, sangat mungkin terjadi tabrakan(collision). Maksudnya tabrakan itu, dua kunci atau lebih mendapat posisi yang sama. Okelah fungsi hash sudah unik, tapi karena kita menggunakan modulo untuk menyesuaikan ukuran array, bisa saja dua kunci yang jauh berbeda mendapat posisi yang sama.

 Pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.

Dalam ilmu komputer, sebuah pohon biner adalah struktur data pohon di mana setiap node memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif hanya menggunakan teori himpunan gagasan adalah bahwa (non-kosong) pohon biner adalah tiga (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah satu set tunggal. Beberapa penulis memungkinkan pohon biner menjadi himpunan kosong juga.

Dari perspektif teori grafik, biner (dan K-ary) pohon seperti yang didefinisikan di sini sebenarnya arborescences. Sebuah pohon biner sehingga dapat juga disebut bifurcating arborescence-istilah yang benar-benar muncul di beberapa buku-buku pemrograman yang sangat tua, sebelum terminologi ilmu komputer modern menang. Hal ini juga memungkinkan untuk menafsirkan sebuah pohon biner sebagai diarahkan, bukan grafik diarahkan, dalam hal pohon biner adalah memerintahkan, berakar pohon. Beberapa penulis menggunakan berakar pohon biner bukan pohon biner untuk menekankan fakta bahwa pohon berakar, tetapi seperti yang didefinisikan di atas, pohon biner selalu berakar. Sebuah pohon biner adalah kasus khusus dari pohon K-ary memerintahkan, di mana k adalah 2.

Operasi-operasi pada Binary Tree :

1.      Create : Membentuk binary tree baru yang masih kosong.

2.      Clear : Mengosongkan binary tree yang sudah ada.

3.      Empty : Function untuk memeriksa apakah binary tree masih kosong.

4.      Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

5.      Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

6.      Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

7.      Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

8.      DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

9.      Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

10.  Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.

Langkah-Langkahnya Traverse :

-        PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

-        InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.

-        PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi

BINARY SEARCH TREE

Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. Binary Search Tree juga merupakan tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list

Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.

Aturan Dalam Membangun BST Agar data benar-benar tersusun dalam struktur data BST, dua aturan yang harus dipenuhi pada saat data diatur dalam BST adalah sebagai berikut:

 1. Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.

 2. Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.

Pada dasarnya operasi dalam Binary Search Tree adalah sama dengan Binary Tree biasa, kecuali pada operasi insert, update dan delete.

• Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat.

• Update : Seperti pada Binary Tree biasa, namun jika update berpengaruh pada posisi node tersebut, sehingga menyebabkan Tree bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan cara melakukan rotasi supaya tetap menjadi Binary Search Tree kembali.

• Delete : Seperti halnya update, delete dalam binary search tree juga turut mempengaruhi struktur dari tree tersebut.

AVL Tree adalah binary search tree yang memiliki perbedaan tinggi/level antara subtree kiri dan subtree kanan maksimal adalah 1. AVL Tree muncul untuk menyeimbangkan binary search tree. Dengan AVL Tree waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Selain AVL Tree terdapat pula height balanced and Tree, yakni binary search tree yang memiliki perbedaan level antara subtree kiri dan subtree sehinga avl tree adalah height balanced 1 tree.