DATA STRCUTURE FINAL RIVIEW

Nama: Muhammad Farhan Ghani Azhar
NIM  :2301945710
Class  : CB01
Dosen: Ferdinand Ariandy Luwinda (D4522) & Henry Chong (D4460)

Linked List

 Apa itu Linked list?....Linked 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. 

A.Double Linked list

 Double linked list atau list berkait double adalah suatu bentuk tipe data abstrak yang merupakan kumpulan dari data yang berbentuk record dengan ciri setiap elemen data memiliki karakteristik

yaitu : a.Antara satu elemen dengan elemen berikutnya.

           b.Antara satu elemen dengan elemn yang sebelumnya.

B.Circular Single 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. Kalau Circular Single Linked List tidak diakhiri dengan null, dia diakhiri dengan pointer di data paling terakhir yang menunjuk ke data pertama.

C.CIRCULAR DOUBLE LINKED LIST

Double Linked List Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut.
Double Linked List Circular pointer next dan prev nya menunjuk ke dirinya sendiri secara circular. Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke dirinya sendiri. Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya.

• STACK

Stack merupakan struktur data dengan konsep LIFO (Last in First Out), penerapan stack dapat dilakukan baik secara array ataupun linked list (pushDepan/head & popDepan/head).

• QUEUE

Queue merupakan struktur data dengan konsep FIFO (First in First Out), penerapan queue dapat dilakukan baik secara array ataupun linked list (pushBelakang/tail & popDepan/head).

HASH TABLE                                                                                                                        

       Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain. keunggulan dari Hash Table adalah waktu mengakses lebih cepat.

• Operasi pada Hash Table

                insert: diberikan sebuah key,insert nilai dalam tabel

                find   : diberikan sebuah key,menemukan nilai yang berhubungan dengan key

                remove: diberikan sebuah key,menemukan nilai yang berhubungan dengan key                                             kemudian  di hapus nilai tersebut.

                getiterator: mengembakikan iterator, yang memeriksa nilai satu demi satu. 

• Metode untuk membangun Hash function:

            1.Mid Square       :  Mengkuadratkan nilai yang di dapat lalu beberapa digit ditengah                                                         diambil yang nanti akan menjadi nilai hash nya.

            2.Division            :Sebuah String  dibagi menggunakan operasi Modulus.

            3.Folding             :Membagi nilai key ke beberapa bagian kemudian dijumlahkan. lalu itu                                                   sebagai  nilai hasnya.

            4.Digit Extraction: Dengan mengambil digit dari urutan nomor yang sudah ditentukan.

            5.Rotating Hash   :Menggunakan salah satu metode sebelumnya kemudian hasil dari nilai                                              di acak kembali untuk mendapatkan alamat hash yang baru.

BINARY TREE

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut  terpisah.  maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Jenis jenis Binary tree

1.Full Binary Tree: 

tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

2.Complete Binary tree: 

tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

3.Skewed Binary Tree:

Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Impelementasi Binary Tree

Create          : Membentuk binary tree baru yang masih kosong.

Clear            : Mengosongkan binary tree yang sudah ada.

Empty          : Function untuk memeriksa apakah binary tree masih kosong.

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.

Find              : Mencari root, parent, left child, atau right child dari suatu node.tree tak boleh kosong

Update          : Mengubah isi dari node yang ditunjuk oleh pointer current. tree tak boleh kosong

Retrieve         : Mengetahui isi dari node yang ditunjuk pointer current. tree tak boleh kosong

DeleteSub      : Menghapus sebuah subtree  yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

Characteristic : Mengetahui karakteristik dari suatu tree, yaitu: size, height, serta average lengthnya. Tree tidak boleh kosong. 

Traverse         : Mengunjungi seluruh node-node pada tree, masing-masing sekali.  Adatiga cara traverse : Pre Order, In Order, dan Post Order.

BINARY SEARCH TREE

Binary Search Tree adalah struktur data yang mengambil konsep Binary Tree namun terdapat aturan bahwa setiap child 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.

 

Operasi find

operasi untuk mencari nilai dalam binary search tree

• Memulai Find Dari Root
• Jika Root adalah value yang kita cari , maka berhenti
• Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
• Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan.

Operasi insert

operasi untuk mencari nilai dalam binary search tree

• Dimulai insert dari root
• jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara rekrusif 
• jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara rekrusif 
• Ulangi sampai menemukan node yang kosong untuk memasukan value X 

Operasi remove

Operasi untuk mengapus nilai

• Jika nilai yang ingin dihapus adalah Daun atau paling bawah , langsung delete
• Jika nilai yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan      anaknya ke parent value yang dihapus.
• jika nilai yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan).

AVL TREE

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

AVL TREE itu mempunyai 2 cara untuk merotasi nodenya yaitu:

A.SINGLE ROTATION

Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar . T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin .

B.DOUBLE ROTATION

Double rotasi dilakukan apabila searah yaitu right to left atau left to right

gambar diatas melakukan rotasi dari node 22 dan 27

Dan selanjutnya gambar diatas melakukan rotasi antara node 27 dan 30 dikarenakan tree belum stabil.

HEAP

Hari ini saya akan menyampaikan sebuah rangkuman tentang Heap dan Tries

Heap adalah sebuah Complete Binary Tree yang memenuhi persyaratan heap. Heap mempunyai porperties sebagai berikut:

• Min Heap

• Setiap node lebih kecil dari masing-masing childnya
• Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node
• 
• Max Heap

• Setiap node lebih besar dari masing-masing childnya
• Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node
• 

• Min-Max Heap
• Heap dengan Min heap pada level ganjil dan Max heap pada level genap
• 

TRIES

• Tries adalah tree yang dilakukan untuk menyimpan array asosiatif
• Properties pada tries:
• Setiap vertex/node merepresentasikan satu huruf
• Root merepresentasikan karakter kosong

Contoh:

       
           
Demikian rangkuman yang dapat saya sampaikan, Jika terdapat kesalahan dapat bantu disampaikan di kolom komen yaaa