Selasa,9 juni 2020
Nama : Syarief Kamal
NIM : 2301899250
Kelas : CB01
Lecturer : Ferdinand Ariandy Luwinda -D4522 dan Henry Chong -D4460
Selasa 25 februari 2020.
Linked List
1. Circural Single Linked List
2. Doubly Linked List
3.Circular Doubly Linked List
Semoga Blog ini dapat membantu,selamat membaca!
1. CIRCULAR SINGLE LINKED LIST.
Circular single linked list merupakan linked list dimana node terakhirnya selalu menunjuk ke node pertama,kami melintasi circular linked list hingga mencapai node yang sama dengan tempat kami memulai
2. DOUBLY LINKED LIST
Doubly linked list merupakan linked list yang terdiri dari node yang memiliki dua pointer,pointer ini menunjuk ke node selanjutnya dan sebelumnya,berikut adalah istilah penting untuk memahami konsep Doubly linked list
Contoh :
3. CIRCULAR DOUBLY LINKED LIST
Circular Doubly linked list adalah data structure yang mirip dengan Circular single linked list,namun dalam doubly linked list as circular ini pointer selanjutnya dari node yang terakhir menunjuk ke node yang pertama dan node sebelumnya dari node pertama menunjuk ke node yang terakhir yang akan membuat lingkaran di kedua arah.
Hash Tables adalah sebuah struktur data yang terdiri dari tabel yang berfungsi untuk memetakan nilai untuk setiap baris menjadi angka dalam sebuah tabel.
Operasi pada Hash Table
Salah satu keunggulan dalam hash table ini adalah kecepatannya dalam mencari data,dengan menggunakan hash function,sebuah lokasi dari record yang dicari bisa di perkirakan,jika lokasi tersebut berisi nilai yang dicari, maka pencarian berhasil
Collision (Tabrakan)
Kekurangan pada hash tables ini adalah keterbatasannya table hash yang jika ada dua angka di masukkan ke dalam fungsi table(hash) maka akan menghasilkan nilai yang sama.
Contoh :
B . Binary Tree
Tree adalah bentuk struktur data yang menggambarksn hubungan antar elemen-elemennya,sebuah node dalam tree biasanya memiliki percabangan lagi atas dirinya
Lalu ada yang namannya Binary Tree, konsep nya sama dengan Tree namun kita akan mengambil sifat bilangan biner yang selalu bernilai 1 atau 0,berarti Binary Tree adalah tree yang hanya bisa mempunyai 2 percabangan saja
Ada tiga jenis cara untuk penelusuran data
Berikut adalah contoh implementasi Binary Tree
Binary search tree merupakan semacam container struktur data, yang menyimpan informasi seperti bilangan atau nama yang ada di dalam memory. 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.
Searching
Pencarian dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive maupun dengan proses iterative. Langkah pertama dalam pencarian ialah dengan melakukan identifikasi root node. Bila root node null maka key yang dicari tidak ada. Sebaliknya bila root tersebut exist, maka langkah selanjutnya ialah membandingkan nilai key dengan node root tersebut. Bila nilai root node sama seperti key yang dicari, maka nilai root node tersebut akan dikembalikan sebagai hasil. Bila nilai key lebih kecil dari node, maka pencarian diarahkan ke subtree di sisi kiri dari node, proses ini dilakukan terus berulang hingga key ditemukan. Sebaliknya bila nilai key lebih besar dari node, maka langkah selanjutnya ialah memilih subtree di sisi kanan node tersebut. Dalam kasus terburuk, pencarian ini akan mencapai ujung subtree terjauh dari root, atau setara dengan tinggi dari tree tersebut.
Insertion
Proses insertion (memasukkan suatu data) dilakukan mulai secara bersamaan dengan proses pencarian data. Bila key tidak sesuai dengan nilai yang ada di root, pencarian dilakukan ke subtree kanan atau kiri. Hingga berada pada node luar, untuk kemudian dilakukan penambahan data key baru. Dengan kata lain dilakukan proses pemeriksaan root dan secara recursive memasukkan suatu node baru di sisi kiri bila nilainya lebih kecil, atau di sisi kanan bila nilainya lebih besar (atau bisa juga sama besar) dibandingkan dengan nilai dari root tersebut.
Deletion
Referensi
https://lang8088.blogspot.com/2015/06/memahami-pengertian-binary-search-tree.html
AVL Tree
VL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi antara subtree kiri dan subtree kanan.AVL Muncul untuk menyeimbangkan Binary Search Tree,dengan AVL Tree,waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
SINGLE ROTATION
Single Rotation dilakukan apabila kondisi AVL Tree searah
Contoh Gambar :
Pada contoh di atas gambar di sebelah kiri tidak Balance
dikarenakan 30 ke kanan memiliki 4 height sedangkan 30 ke kanan memiliki
2 height,4 - 2 = 2 <= tidak boleh lebih dari 1.
Heap Tries And Tries
HEAP
Heap adalah struktur data yang mirip dengan Binary Search Tree,namun Heap adalah complete binary tree yang memiliki properties sebagai berikut :
Insertion
1. Max Heap
Saat node baru diinsert, cek terhadap parentnya. Jika node baru bernilai lebih besar dibandingkan parent, tukar posisinya dengan parent.
2. Min Heap
Saat node baru diinsert, cek terhadap parentnya. Jika node baru bernilai lebih kecil dibandingkan parent, tukar posisinya dengan parent.
Deletion
Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.
- Jika min heap(elemen terkecil terletak di root):
a. Maka yang dihapus merupakan rootnya(elemen terkecil).
b. Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak < data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya).
b. Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmax(jika anak > data tsb, maka tukar,dst), sampai mentok dibawah atau node tsb>anaknya).
referensi : https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
Nama : Syarief Kamal
NIM : 2301899250
Kelas : CB01
Lecturer : Ferdinand Ariandy Luwinda -D4522 dan Henry Chong -D4460
Selasa 25 februari 2020.
Linked List
1. Circural Single Linked List
2. Doubly Linked List
3.Circular Doubly Linked List
Semoga Blog ini dapat membantu,selamat membaca!
1. CIRCULAR SINGLE LINKED LIST.
Circular single linked list merupakan linked list dimana node terakhirnya selalu menunjuk ke node pertama,kami melintasi circular linked list hingga mencapai node yang sama dengan tempat kami memulai
2. DOUBLY LINKED LIST
Doubly linked list merupakan linked list yang terdiri dari node yang memiliki dua pointer,pointer ini menunjuk ke node selanjutnya dan sebelumnya,berikut adalah istilah penting untuk memahami konsep Doubly linked list
- Link − Setiap link yang dapat menyimpan data yang disebut elemen.
- Next −Setiap link yang berisi link ke link berikutnya yang disebut next
- Prev −Setiap link daftar link berisi link ke tautan sebelumnya yg disebut Prev
Contoh :
3. CIRCULAR DOUBLY LINKED LIST
Circular Doubly linked list adalah data structure yang mirip dengan Circular single linked list,namun dalam doubly linked list as circular ini pointer selanjutnya dari node yang terakhir menunjuk ke node yang pertama dan node sebelumnya dari node pertama menunjuk ke node yang terakhir yang akan membuat lingkaran di kedua arah.
Linked List Stack & queue
A. Pengertian Stack (Tumpukan)
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.
Operasi - operasi pada Stack (Tumpukan)
Operasi yang sering diterapkan pada struktur data Stack ( Tumpukan) adalah Push dan Pop. Operasi-operasi yang dapat diterapkan adalah sebagai berikut :
1. Push : fungsinya untuk memasukan sebuah nilai atau data ke dalam stack pada tumpukan paling atas
Contoh :
2. Pop : Pop, kebalikan dari push, merupakan operasi delete, dimana di dalam linked list memiliki 2 kemungkinan delete, yaitu melalui depan (popDepan) dan melalui belakang (popBelakang).
Contoh :
B. Queue
Queue atau antrian adalah suatu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada satu ujung
Contoh :
Dalam penggunaannya, suatu queue memiliki beberapa operasi yang dapat diterapkan seperti, membuat queue, penambahan data/elemen ke dalam queue (enqueue), menghapus data/elemen di dalam queue (dequeue) dan operasi lain yang berhubungan dengan queue tersebut.
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.
Operasi - operasi pada Stack (Tumpukan)
Operasi yang sering diterapkan pada struktur data Stack ( Tumpukan) adalah Push dan Pop. Operasi-operasi yang dapat diterapkan adalah sebagai berikut :
1. Push : fungsinya untuk memasukan sebuah nilai atau data ke dalam stack pada tumpukan paling atas
Contoh :
2. Pop : Pop, kebalikan dari push, merupakan operasi delete, dimana di dalam linked list memiliki 2 kemungkinan delete, yaitu melalui depan (popDepan) dan melalui belakang (popBelakang).
Contoh :
B. Queue
Queue atau antrian adalah suatu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada satu ujung
Contoh :
Operasi pada Queue
Dalam penggunaannya, suatu queue memiliki beberapa operasi yang dapat diterapkan seperti, membuat queue, penambahan data/elemen ke dalam queue (enqueue), menghapus data/elemen di dalam queue (dequeue) dan operasi lain yang berhubungan dengan queue tersebut.
Hash Table & Binary Tree
A. Hash Tables
Pada pertemuan sebelumnya kita sudah mempelajari linked list,ada single
linked list,double linked list,circular single linked list dll,nah di
materi kali ini linked list juga akan terpakai dalam hash table maupun
binary tree,Selamat membaca!! Hash Tables adalah sebuah struktur data yang terdiri dari tabel yang berfungsi untuk memetakan nilai untuk setiap baris menjadi angka dalam sebuah tabel.
Operasi pada Hash Table
- Insert : insert nikai pada table
- Find : Temukan nilai
- Remove : Diberikan Key,temukan nilai yang berhubungan dengan key tersebut,lalu hapus(remove) nilai tersebut.
Salah satu keunggulan dalam hash table ini adalah kecepatannya dalam mencari data,dengan menggunakan hash function,sebuah lokasi dari record yang dicari bisa di perkirakan,jika lokasi tersebut berisi nilai yang dicari, maka pencarian berhasil
Collision (Tabrakan)
Kekurangan pada hash tables ini adalah keterbatasannya table hash yang jika ada dua angka di masukkan ke dalam fungsi table(hash) maka akan menghasilkan nilai yang sama.
Contoh :
Biarkan fungsi hash H (x) memetakan nilai x pada indeks x% 10 dalam sebuah array,
Sebagai contoh jika daftar nilai adalah [11,12,13,14,15]
itu akan disimpan di posisi {1,2,3,4,5},masing-masing dalam array atau tabel hash.
B . Binary Tree
Tree adalah bentuk struktur data yang menggambarksn hubungan antar elemen-elemennya,sebuah node dalam tree biasanya memiliki percabangan lagi atas dirinya
Lalu ada yang namannya Binary Tree, konsep nya sama dengan Tree namun kita akan mengambil sifat bilangan biner yang selalu bernilai 1 atau 0,berarti Binary Tree adalah tree yang hanya bisa mempunyai 2 percabangan saja
Ada tiga jenis cara untuk penelusuran data
- PreOrder : Print data,telusuri ke kiri,telusuri ke kanan
- InOrder : Telusuri ke kiri terlebih dahulu,print,lalu telusuri ke kanan
- Post Order : Telusuri ke kiri,telusuri ke kanan,lalu print data nya.
Berikut adalah contoh implementasi Binary Tree
Binary Search Tree
Binary search tree merupakan semacam container struktur data, yang menyimpan informasi seperti bilangan atau nama yang ada di dalam memory. 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.
Searching
Pencarian dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive maupun dengan proses iterative. Langkah pertama dalam pencarian ialah dengan melakukan identifikasi root node. Bila root node null maka key yang dicari tidak ada. Sebaliknya bila root tersebut exist, maka langkah selanjutnya ialah membandingkan nilai key dengan node root tersebut. Bila nilai root node sama seperti key yang dicari, maka nilai root node tersebut akan dikembalikan sebagai hasil. Bila nilai key lebih kecil dari node, maka pencarian diarahkan ke subtree di sisi kiri dari node, proses ini dilakukan terus berulang hingga key ditemukan. Sebaliknya bila nilai key lebih besar dari node, maka langkah selanjutnya ialah memilih subtree di sisi kanan node tersebut. Dalam kasus terburuk, pencarian ini akan mencapai ujung subtree terjauh dari root, atau setara dengan tinggi dari tree tersebut.
Insertion
Proses insertion (memasukkan suatu data) dilakukan mulai secara bersamaan dengan proses pencarian data. Bila key tidak sesuai dengan nilai yang ada di root, pencarian dilakukan ke subtree kanan atau kiri. Hingga berada pada node luar, untuk kemudian dilakukan penambahan data key baru. Dengan kata lain dilakukan proses pemeriksaan root dan secara recursive memasukkan suatu node baru di sisi kiri bila nilainya lebih kecil, atau di sisi kanan bila nilainya lebih besar (atau bisa juga sama besar) dibandingkan dengan nilai dari root tersebut.
Deletion
- Bila node tersebut tidak memiliki cabang, node tersebut dapat langsung dihapus
- Bila node tersebut memiliki cabang, maka node tersebut dihapus dan child dari node tersebut menggantikan posisi dari node parent
- Bila node tersebut memiliki dua cabang, maka langkah pertama yang dilakukan ialah mengganti nilai node parent dengan salah satu child, hapus nilai node parent awal, secara recursive hapus nilai node child yang telah digunakan untuk mengganti nilai node parent sebelumnya, kemudian lakukan seperti pada kasus pertama atau kedua
Referensi
https://lang8088.blogspot.com/2015/06/memahami-pengertian-binary-search-tree.html
AVL Tree
VL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi antara subtree kiri dan subtree kanan.AVL Muncul untuk menyeimbangkan Binary Search Tree,dengan AVL Tree,waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
SINGLE ROTATION
Single Rotation dilakukan apabila kondisi AVL Tree searah
Contoh Gambar :
DOUBLE ROTATION
Double rotation dilakukan apabila kondisi AVL Tree searah left-right atau right-left
Contoh Gambar :
Pada contoh di atas 30 ke kiri tidak balance karena memiliki 4
height sedangkan 30 ke kanan memiliki 2 height,jadi di pakai double
rotation yaitu 27 menggantikan posisi 22 setelah itu 30 di gantikan
posisinya oleh 27.
Heap Tries And Tries
HEAP
Heap adalah struktur data yang mirip dengan Binary Search Tree,namun Heap adalah complete binary tree yang memiliki properties sebagai berikut :
- Min Heap
- Setiap node lebih kecil dari masing-masing child nya
- Root merupakan node paling kecil
- Max Heap
- Setiap node lebih besar dari masing-masing child nya
- Min-Max Heap
- Min heap pada level ganjil dan max heap pada level genap
Insertion
1. Max Heap
Saat node baru diinsert, cek terhadap parentnya. Jika node baru bernilai lebih besar dibandingkan parent, tukar posisinya dengan parent.
2. Min Heap
Saat node baru diinsert, cek terhadap parentnya. Jika node baru bernilai lebih kecil dibandingkan parent, tukar posisinya dengan parent.
Deletion
Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.
- Jika min heap(elemen terkecil terletak di root):
a. Maka yang dihapus merupakan rootnya(elemen terkecil).
b. Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak < data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya).
b. -
Jika max
heap(elemen terkecil terletak di root):
a. Maka yang dihapus merupakan rootnya(elemen terbesar). b. Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmax(jika anak > data tsb, maka tukar,dst), sampai mentok dibawah atau node tsb>anaknya).
Tries
- Tries adalah tree yang dilakukan untuk menyimpan array
- Properties pada tries :
- Setiap node merepresentasikan satu huruf
- Root mempresentasikan karakter kosong
referensi : https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
Komentar
Posting Komentar