Rangkuman Final Data Structure

Ringkasan Final Data Structure

Data Structure

Nama : Isaac Andrean Yoshua

NIM : 2301927046

Kelas : CB01-CL

Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)   

    

Binary Search Tree

Pengertian

Sebelum masuk kedalam konsep Binary Search Tree, ada baiknya kita memahami konsep Tree itu sendiri. Tree adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (relasi one to many). 

Lalu apa perbedaannya dengan Binary Search Tree? Binary Search Tree adalah tree yang memiliki maksimal 2 percabangan saja, dan terdapat beberapa aturan. Child node sebelah kiri selalu lebih kecil daripada root node. Child node sebelah kanan selalu lebih besar daripada rootnode. Binary Search Tree biasa dikenal sebagai Sorted Version of Binary Tree.

Seperti pada gambar diatas, root node adalah 50, child node seblah kiri adalah 17, dan child node sebelah kanan adalah 76. Ini artinya child node sebelah kiri selalu lebih kecil dibandingkan root, dan child node kanan selalu lebih besar daripada root.

Operasi Binary Search Tree

Insert:

1. Selalu dimulai dari root.
2. Jika angka yang akan dimasukkan lebih kecil daripada sub tree, maka cek sebelah kiri dari sub tree. Bila kosong masukkan angka tersebut.
3. Bila angka yang akan dimasukkan lebih besar daripada sub tree, maka cek sebelah kanan dari sub tree. Bila kosong, masukkan angka tersebut.
4. Lakukan terus sampai menemukan node yang kosong untuk ditaruh sebuah nilai.

Deletion:

Untuk melakukan delete terdapat 3 situasi.

1. Bila yang ingin dihapus di bagian leaf, dapat langsung dihapus. Pada gambar diatas, 12 dapat langsung dihapus.
2. Bila yang akan dihapus memiliki satu child, hapus node tersebut dan gabungkan antara parent node tersebut dan child dari node tersebut. Pada gambar diatas, bila 72 dihapus, maka 54 menjadi parent 67.
3. Bila yang akan dihapus memiliki dua child, cari sub tree bagian kiri kemudian dibandingkan dengan yang kanan. Pada gambar diatas, apabila angka 17 dihapus maka, angka 14 akan naik menggantikan posisi 17, angka 9 akan menjadi parent 12. Bila angka 50 yang dihapus, maka angka 23 akan naik menggantikan posisi 50, dann17 akan menjadi parent 19.

AVL Tree

Definisi

AVL Tree adalah subtipe dari BST atau yang biasa disebut sebagai Binary Search Tree. AVL sendiri diciptakan oleh tiga orang, yaitu Adelson, Velskii, dan Landis. AVL sendiri diciptakan untuk melakukan "self-balancing" antara anak kanan dengan anak kiri, agar waktu yang dibutuhkan dalam melakukan proses searching lebih singkat, sehingga program dapat berjalan lebih cepat. Untuk menetapkan tingginya dapat menggunakan rumus O(log n)

Syarat AVL

AVL Tree sendiri memiliki satu syarat penting yaitu perbedaan level atau kedalaman antara ruas kiri dengan kanan tidak boleh melebihi dari satu. Bila melebihi dari satu, maka akan melakukan "rebalancing" secara otomatis. Untuk menghitung perbedaan antara ruas kiri dengan ruas kanan, dapat dilakukan dengan menghitung balance factor (BF). 

Balance Factor sendiri memiliki rumus sebagai berikut:

BalanceFactor(N) = Level (Subtree bagian kiri (N)) -  Level (Subtree bagian kanan (N))

BalanceFactor(N) merupakan elemen dari {-1, 0, 1}

Berikut adalah contoh dari Balance Factor

Insert

Insert sendiri memiliki prinsip yang sama dengan Binary Search Tree, dimana node yang baru masuk, dijadikan sebagai leaf. Namun terdapat perbedaan dengan BST, bila dimasukkin node baru, maka akan melakukan penyeimbangan antara ruas kanan dengan ruas kiri. 

Contohnya sebagai berikut:

1. 

Pada gambar diatas, terdapat sebuah tree yang ditambahkan node yang berisi nilai 45. Node 45 menjadi anak kanan dari 40, karena 45 lebih besar dari 40. Namun bila terjadi hal tersebut, maka balance factor di root akan menjadi +2 atau -2, dikarenakan ruas kanan dari root memiliki kedalaman 3, sedangkan ruas kiri dari root memiliki kedalaman 1. Karena tidak seimbang, maka dilakukan self-balancing dengan cara mencari bagian yang rusak. Seperti yang diketahui, di root mengalami balance factor yang berbeda, dan angka 45 sangatlah mengganggu. Oleh karena itu, 3 node teratas dilakukan rotation ke left atau yang biasa disebut dengan left rotate. 30, 35, dan 40 di rotater ke arah kiri, sehingga 35 menjadi root, anak kirinya adalah 30, dan anak kanannya adalah 45. Ini sudah balance, dan dapat disebut sebagai single rotation.

2. 

Pada gambar diatas, terdapat sebuah tree yang ditambahkan node yang berisi nilai 7. Node 7 menjadi anak kanan dari 6, karena 7 lebih besar dari 6. Namun bila terjadi hal tersebut, maka balance factor di root akan menjadi +2 atau -2 dan di anak kiri root balance factor akan menjadi +2 atau -2, dikarenakan ruas kiri dari root memiliki kedalaman 4, sedangkan ruas kanan dari root memiliki kedalaman 2 dan juga ruas kanan dari anak kiri root memiliki kedalaman 1, sedangkan ruas kiri dari anak kiri root memiliki kedalaman 4. Karena tidak seimbang, maka dilakukan self-balancing dengan cara mencari bagian yang rusak. Bagian yang pertama yang rusak adalah anak kiridari root, dan yang mengganggu adalah leaf yang memiliki nilai 7. Oleh karena itu angka 5, 6 ,7, kira rotate ke arah kiri atau yang biasa disebut sebagai left rotation untuk memperbaiki rantai. Setelah itu untuk memperbaiki 10 yang memiliki balance factor 2 atau -2, maka dilakukan rotasi kearah kanan atau yang biasa disebut sebagai right rotation. Ambil 3 node diatas dari 10, yaitu 10, 6 , dan 5 setelah itu melakukan right rotation. Setelah itu, 6 menjadi anak kiri dari root, dan tree sudah balance. Inidapat disebut sebagai double rotation.

Delete

Delete memiliki prinsip yang sama dengan Binary Search Tree. Bila ingin menghapus leaf, maka langsung hapus saja. Bila yang ingin dihapus memiliki child, maka child tersebut yang akan menggantikan node yang dihapus. Setelah melakukan delete, maka langkah berikutnya adalah melakukan self-balancing. Prosesnya sama seperti Insert, yaitu melakukan right rotation ataupun left rotation, dan juga bisa melakukan single rotation, maupun double rotation.

Heap and Tries

Pengertian Heap

Heap adalah binary tree yang sudah lengkap yang telah memenuhi persyaratan heap. Berbeda dari AVL Tree, B-Tree, dan Red-Black Tree, Heap tidak memiliki balance factor ataupun warna dalam melakukan rebalancing.

Bentuk Heap

Heap sendiri memiliki dua bentuk umum:

1. Min Heap
2. Max Heap

Min Heap

Min Heap adalah heap dengan nilai parent lebih kecil dibandingkan nilai childnya. Di dalam tree Min Heap, nilai terkecil terdapat di root, sedangkan nilai terbesarnya terdapat di bagian leaves. Implementasi Min Heap dapat dilakukan di linked list, namun lebih mudah dilakukan dengan menggunakan array. Berikut adalah contoh Min Heap:

Dapat dilihat bahwa nilai parent lebih kecil dibandingkan nilai child nya. Nilai terkecil terdapat pada root, nilai terbesar terdapat di leaves, yaitu 83.

Cara Insert

Berikut adalah cara insert menggunakan Min Heap yang saya pelajari dari kelas kecil saya. Setiap node yang baru masuk dijadikan leaf. Setelah masuk, maka akan melakukan pengecekan dengan parentnya atau biasa disebut sebagai uphead atau heapify up. Bila nilai child lebih kecil daripada parent, maka akan melakukan balancing dengan cara menukar nilai child dengan nilai parent. Pengecekan ini dilakukan secara rekursif. Ini dilakukan sampai tree menjadi balance.

Cara Delete

Berikut adalah cara delete menggunakan Min Heap yang saya pelajari dari kelas kecil saya. Berbeda dengan Binary Search Tree ataupun AVL, dalam heap nilai yang dihapus SELALU ROOT. Setelah root dihapus maka, ARRAY TERAKHIR akan menggantikan posisi root. Kita tidak menggunakan predecessor ataupun successor. Setelah menjadi root, maka akan melakukan pengecekan dengan childrennya. Ini dapat disebut sebagai down heap atau heapify down. Bila nilai child lebih kecil dari parent, maka akan melakukan balancing dengan cara menukar parent dengan child. Pengecekan ini dilakukan secara rekursif.

Max Heap

Max Heap adalah heap dengan nilai parent lebih besar dibandingkan nilai childnya. berbeda dengan  tree Min Heap, dalam tree Max Heap, nilai terkecil terdapat di leaves, sedangkan nilai terbesarnya terdapat di bagian root. Implementasi Max Heap dapat dilakukan di linked list, namun lebih mudah dilakukan dengan menggunakan array. Berikut adalah contoh Min Heap:

Dapat dilihat bahwa nilai parent lebih besar dibandingkan nilai child nya. Nilai terbesar terdapat pada root, nilai terkecil terdapat di leaves, yaitu 23.

Cara Insert

Berikut adalah cara insert menggunakan Max Heap yang saya pelajari dari kelas kecil saya. Setiap node yang baru masuk dijadikan leaf. Setelah masuk, maka akan melakukan pengecekan dengan parentnya atau biasa disebut sebagai uphead atau heapify up. Bila nilai child lebih besar daripada parent, maka akan melakukan balancing dengan cara menukar nilai child dengan nilai parent. Pengecekan ini dilakukan secara rekursif. Ini dilakukan sampai tree menjadi balance.

Cara Delete

Berikut adalah cara delete menggunakan Max Heap yang saya pelajari dari kelas kecil saya. Berbeda dengan Binary Search Tree ataupun AVL, dalam heap nilai yang dihapus SELALU ROOT. Setelah root dihapus maka, ARRAY TERAKHIR akan menggantikan posisi root. Kita tidak menggunakan predecessor ataupun successor. Setelah menjadi root, maka akan melakukan pengecekan dengan childrennya. Ini dapat disebut sebagai down heap atau heapify down. Bila nilai child lebih besar dari parent, maka akan melakukan balancing dengan cara menukar parent dengan child. Pengecekan ini dilakukan secara rekursif.

Pengertian Tries

Tries atau prefix tree adalah tree yang terurut yang dapat menyimpan data array, biasanya berupa strings ataupun char. Kata TRIE berasal dari kata RETRIEVAL karena tries dapat mencari satu kata dalam kamus hanya dengan kata awalan saja. Berikut adalah gambaran tries:

Refrensi:

• https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
• https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
• https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
• https://www.geeksforgeeks.org/avl-tree-set-2-deletion/
• https://www.google.com/url?sa=i&url=http%3A%2F%2Fbtechsmartclass.com%2Fdata_structures%2Ftries.html&psig=AOvVaw39rWJuHg1x0nZIGQLHTz8O&ust=1589618170135000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCMj53aa7tekCFQAAAAAdAAAAABAD
• Binus Maya

Heap and Tries

Pengertian Heap

Heap adalah binary tree yang sudah lengkap yang telah memenuhi persyaratan heap. Berbeda dari AVL Tree, B-Tree, dan Red-Black Tree, Heap tidak memiliki balance factor ataupun warna dalam melakukan rebalancing.

Bentuk Heap

Heap sendiri memiliki dua bentuk umum:

1. Min Heap
2. Max Heap

Min Heap

Min Heap adalah heap dengan nilai parent lebih kecil dibandingkan nilai childnya. Di dalam tree Min Heap, nilai terkecil terdapat di root, sedangkan nilai terbesarnya terdapat di bagian leaves. Implementasi Min Heap dapat dilakukan di linked list, namun lebih mudah dilakukan dengan menggunakan array. Berikut adalah contoh Min Heap:

Dapat dilihat bahwa nilai parent lebih kecil dibandingkan nilai child nya. Nilai terkecil terdapat pada root, nilai terbesar terdapat di leaves, yaitu 83.

Cara Insert

Berikut adalah cara insert menggunakan Min Heap yang saya pelajari dari kelas kecil saya. Setiap node yang baru masuk dijadikan leaf. Setelah masuk, maka akan melakukan pengecekan dengan parentnya atau biasa disebut sebagai uphead atau heapify up. Bila nilai child lebih kecil daripada parent, maka akan melakukan balancing dengan cara menukar nilai child dengan nilai parent. Pengecekan ini dilakukan secara rekursif. Ini dilakukan sampai tree menjadi balance.

Cara Delete

Berikut adalah cara delete menggunakan Min Heap yang saya pelajari dari kelas kecil saya. Berbeda dengan Binary Search Tree ataupun AVL, dalam heap nilai yang dihapus SELALU ROOT. Setelah root dihapus maka, ARRAY TERAKHIR akan menggantikan posisi root. Kita tidak menggunakan predecessor ataupun successor. Setelah menjadi root, maka akan melakukan pengecekan dengan childrennya. Ini dapat disebut sebagai down heap atau heapify down. Bila nilai child lebih kecil dari parent, maka akan melakukan balancing dengan cara menukar parent dengan child. Pengecekan ini dilakukan secara rekursif.

Max Heap

Max Heap adalah heap dengan nilai parent lebih besar dibandingkan nilai childnya. berbeda dengan  tree Min Heap, dalam tree Max Heap, nilai terkecil terdapat di leaves, sedangkan nilai terbesarnya terdapat di bagian root. Implementasi Max Heap dapat dilakukan di linked list, namun lebih mudah dilakukan dengan menggunakan array. Berikut adalah contoh Min Heap:

Dapat dilihat bahwa nilai parent lebih besar dibandingkan nilai child nya. Nilai terbesar terdapat pada root, nilai terkecil terdapat di leaves, yaitu 23.

Cara Insert

Berikut adalah cara insert menggunakan Max Heap yang saya pelajari dari kelas kecil saya. Setiap node yang baru masuk dijadikan leaf. Setelah masuk, maka akan melakukan pengecekan dengan parentnya atau biasa disebut sebagai uphead atau heapify up. Bila nilai child lebih besar daripada parent, maka akan melakukan balancing dengan cara menukar nilai child dengan nilai parent. Pengecekan ini dilakukan secara rekursif. Ini dilakukan sampai tree menjadi balance.

Cara Delete

Berikut adalah cara delete menggunakan Max Heap yang saya pelajari dari kelas kecil saya. Berbeda dengan Binary Search Tree ataupun AVL, dalam heap nilai yang dihapus SELALU ROOT. Setelah root dihapus maka, ARRAY TERAKHIR akan menggantikan posisi root. Kita tidak menggunakan predecessor ataupun successor. Setelah menjadi root, maka akan melakukan pengecekan dengan childrennya. Ini dapat disebut sebagai down heap atau heapify down. Bila nilai child lebih besar dari parent, maka akan melakukan balancing dengan cara menukar parent dengan child. Pengecekan ini dilakukan secara rekursif.

Pengertian Tries

Tries atau prefix tree adalah tree yang terurut yang dapat menyimpan data array, biasanya berupa strings ataupun char. Kata TRIE berasal dari kata RETRIEVAL karena tries dapat mencari satu kata dalam kamus hanya dengan kata awalan saja. Berikut adalah gambaran tries:

Refrensi:

1. https://www.google.com/url?sa=i&url=http%3A%2F%2Fbtechsmartclass.com%2Fdata_structures%2Ftries.html&psig=AOvVaw39rWJuHg1x0nZIGQLHTz8O&ust=1589618170135000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCMj53aa7tekCFQAAAAAdAAAAABAD
2. Binus Maya

AVL Tree

AVL TREE

Definisi

AVL Tree adalah subtipe dari BST atau yang biasa disebut sebagai Binary Search Tree. AVL sendiri diciptakan oleh tiga orang, yaitu Adelson, Velskii, dan Landis. AVL sendiri diciptakan untuk melakukan "self-balancing" antara anak kanan dengan anak kiri, agar waktu yang dibutuhkan dalam melakukan proses searching lebih singkat, sehingga program dapat berjalan lebih cepat. Untuk menetapkan tingginya dapat menggunakan rumus O(log n)

Syarat AVL

AVL Tree sendiri memiliki satu syarat penting yaitu perbedaan level atau kedalaman antara ruas kiri dengan kanan tidak boleh melebihi dari satu. Bila melebihi dari satu, maka akan melakukan "rebalancing" secara otomatis. Untuk menghitung perbedaan antara ruas kiri dengan ruas kanan, dapat dilakukan dengan menghitung balance factor (BF). 

Balance Factor sendiri memiliki rumus sebagai berikut:

BalanceFactor(N) = Level (Subtree bagian kiri (N)) -  Level (Subtree bagian kanan (N))

BalanceFactor(N) merupakan elemen dari {-1, 0, 1}

Berikut adalah contoh dari Balance Factor

Insert

Insert sendiri memiliki prinsip yang sama dengan Binary Search Tree, dimana node yang baru masuk, dijadikan sebagai leaf. Namun terdapat perbedaan dengan BST, bila dimasukkin node baru, maka akan melakukan penyeimbangan antara ruas kanan dengan ruas kiri. 

Contohnya sebagai berikut:

1. 

Pada gambar diatas, terdapat sebuah tree yang ditambahkan node yang berisi nilai 45. Node 45 menjadi anak kanan dari 40, karena 45 lebih besar dari 40. Namun bila terjadi hal tersebut, maka balance factor di root akan menjadi +2 atau -2, dikarenakan ruas kanan dari root memiliki kedalaman 3, sedangkan ruas kiri dari root memiliki kedalaman 1. Karena tidak seimbang, maka dilakukan self-balancing dengan cara mencari bagian yang rusak. Seperti yang diketahui, di root mengalami balance factor yang berbeda, dan angka 45 sangatlah mengganggu. Oleh karena itu, 3 node teratas dilakukan rotation ke left atau yang biasa disebut dengan left rotate. 30, 35, dan 40 di rotater ke arah kiri, sehingga 35 menjadi root, anak kirinya adalah 30, dan anak kanannya adalah 45. Ini sudah balance, dan dapat disebut sebagai single rotation.

2. 

Pada gambar diatas, terdapat sebuah tree yang ditambahkan node yang berisi nilai 7. Node 7 menjadi anak kanan dari 6, karena 7 lebih besar dari 6. Namun bila terjadi hal tersebut, maka balance factor di root akan menjadi +2 atau -2 dan di anak kiri root balance factor akan menjadi +2 atau -2, dikarenakan ruas kiri dari root memiliki kedalaman 4, sedangkan ruas kanan dari root memiliki kedalaman 2 dan juga ruas kanan dari anak kiri root memiliki kedalaman 1, sedangkan ruas kiri dari anak kiri root memiliki kedalaman 4. Karena tidak seimbang, maka dilakukan self-balancing dengan cara mencari bagian yang rusak. Bagian yang pertama yang rusak adalah anak kiridari root, dan yang mengganggu adalah leaf yang memiliki nilai 7. Oleh karena itu angka 5, 6 ,7, kira rotate ke arah kiri atau yang biasa disebut sebagai left rotation untuk memperbaiki rantai. Setelah itu untuk memperbaiki 10 yang memiliki balance factor 2 atau -2, maka dilakukan rotasi kearah kanan atau yang biasa disebut sebagai right rotation. Ambil 3 node diatas dari 10, yaitu 10, 6 , dan 5 setelah itu melakukan right rotation. Setelah itu, 6 menjadi anak kiri dari root, dan tree sudah balance. Inidapat disebut sebagai double rotation.

Delete

Delete memiliki prinsip yang sama dengan Binary Search Tree. Bila ingin menghapus leaf, maka langsung hapus saja. Bila yang ingin dihapus memiliki child, maka child tersebut yang akan menggantikan node yang dihapus. Setelah melakukan delete, maka langkah berikutnya adalah melakukan self-balancing. Prosesnya sama seperti Insert, yaitu melakukan right rotation ataupun left rotation, dan juga bisa melakukan single rotation, maupun double rotation.

Refrensi:

• https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
• https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
• https://www.geeksforgeeks.org/avl-tree-set-2-deletion/

Summary Data Structures

Linked List

Pengertian

Linked List atau yang biasa disebut dengan senarai berantai adalah struktur data yang terdiri dari record data dimana setiap record mempunyai field yang menyimpan alamat/refrensi dari record selanjutnya dalam urutan.

Macam-macam Linked list

1. Circular Single Linked List
2. Doubly Linked List
3. Circular Doubly Linked List
4. 
   

Circular Single Linked List

Dalam Circular Single Linked List, tidak ada pointer yang menunjukkan NULL yang artinya semua pointer pada setiap node pasti menunjuk pada node lainnya. Proses ini dapat juga disebut sebagai siklus. Head dapat dimulai dimanapun dan cara menentukan ini berhenti dengan cara melewati satu putaran. Seperti pada gambar diatas, pointer yang terdapat pada node terakhir akan menunjuk pada head dan setelah itu berhenti. Bila hanya terdapat satu node, maka node tersebut akan menunjuk dirinya sendiri.

Doubly Linked List

Double/Doubly Linked List adalah linked list yang memiliki dua pointer yang memiliki kegunaan untuk menunjukkan untaian data, yaitu data sebelumnya (previous data) dan data setelahnya (next data). Keunggulan dari linked list ini disaat kita mengaksesnya secara terbalik, yaitu bila kita mengakses list dari data akhir ke data awal. Disamping keungguuan ini, terdapat kelemahan yang ditimbulkan oleh Doubly Linked List. Doubly Linked List memebutuhkan ukuran data yang lebih besar dibandingkan sible linked list dikarenakan memiliki dua pointer. Oleh karena itu, bila tidak menggunakan akses dua arah, single linked list saja sudah cukup.

Berikut adalah contoh codingan Doubly Linked List dalam bahasa C++

struct node {

          int nilai;

          struct node *next;

          struct node *prev;

};

struct node *head=0;

struct node *tail=0;

Proses Insert  dalam Doubly Linked List:

1. Push Head: data baru yang akan dimasukkan diletakkan paling depan.
2. Push Tail: data baru yang akan dimasukkan diletakkan paling akhir atau belakang.
3. Push Mid: data baru yang akan dimasukkan diletakkan dibagian tengah, tidak selalu tepat di tengah, namun diantara bagian head dan tail.

Kondisi proses Delete dalam Doubly Linked List:

1. Bila hanya ada satu data dalam linked list.
2. Data yang ingin dihilangkan adalah head.
3. Data yang ingin dihilangkan adalah tail.
4. Data yang ingin dihilangkan adalah bukan head maupun tail, tetapi daerah mid.

Circular Doubly Linked List

Sama seperti Doubly Linked List, Circular Doubly Linked List memiliki dua pointer yang memiliki kegunaan untuk menunjukkan untaian data, yaitu data sebelumnya dan data setelahnya, hanya saja terdapat sedikit tambahan. Pada list ini, tidak ada pointer yang menunjukkan NULL, yang artinya semua node pasti menunjukkan ke node lainnya. Dalam list ini node pertama menunjuk kepada node terakhir, node terakhir juga menunjuk ke node pertama. Bila hanya terdapat satu node, pointer previous dan pointer next akan menujuk pada dirinya sendiri.

Perbedaan antara Single Linked List dengan Double Linked List

Single Linked List merupakan sekumpulan data data yang dihubungkan dengan satu pointer dalam satu elemen yang bergerak dari depan ke belakang, atau sebaliknya. Pada Single Linked List, data tidak bisa bergerak ke data sebelumnya, karena hanya memiliki satu tangan/ satu pointer. Berbeda dengan Double Linked List. Setiap data dihubungkan dengan dua pointer. Maksudnya adalah informasi data dapat dihubungkan ke data yang sebelumnya dan juga dapat dihubungkan ke data setelahnya. 

Seperti gambar diatas, informasi data  yang berisi sepuluh dapat saling berhubungan dengan data yang berisi lima dan data yang berisi lima belas.

Cara Insert dan Delete Data pada Single Linked List

Berikut ini adalah cara mendefinisikan sebuah Linked List dalam bahasa C++. 

Insert Front

Berikut ini adalah cara Insert /push Front. Insert Front adalah data yang baru masuk akan langsung menjadi head.

Maksud dari Push Front adalah bila ada data baru yang masuk, maka data tersebut akan menjadi head dalam rantai tersebut. Bila ada data yang berisi 10, 5, 4, 7 maka hasil dari push front akan menjadi 7, 4, 5 ,10 baru NULL.

Insert Back

Berikut adalah cara insert back atau push back.

Maksud dari Push Back adalah bila ada data baru yang masuk, maka data tersebut akan menjadi tail dalam rantai tersebut. Bila ada data yang berisi 10, 5, 4, 7 maka hasil dari push back adalah 10, 5, 4, 7 baru NULL.

Pop Front

Berikut adalah cara Delete/Pop Front 

Maksud dari Pop Front adalah menghapus data yang pertama dan menjadikan data ke dua sebagai head. Bila ada data yang berisi 10, 5, 4, 7 maka hasil dari pop front adalah 5, 4, 7 baru NULL.

Pop Back

Berikut adalah cara Delete/ Pop Back

Maksud dari Pop Back adalah menghapus data terakhir dan menjadikan data sebelum terakhir sebagai tail. Bila ada data yang berisi 10, 5, 4, 7 maka hasil pop back adalah 10, 5, 4 baru NULL.

Hashing and Hash Table, Tree and Binary Tree

1. Hashing

Hashing dapat diartikan sebagai teknik untuk menyimpan dan mengambil kunci dengan cepat. Biasanya ini juga dapat disebut sebagai proses memetakan sejumlah besar item data ke tabel yang lebih kecil.

2. Hash Table

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

Keuntungan dari hash table ini adalah waktu aksesnya yang cukup cepat. Namun pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Operasi yang digunakan dalam Hash Table:

1. insert = memasukkan nilai dalam tabel
2. find= mencari nilai dalam tabel
3. remove= mencari nilai dalam tabel, lalu dihapus
4. getIterator= memeriksa nilai satu per satu

3. Hash Function

Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode untuk membangun fungsi hash:

1. Mid-square

Kuadratkan string lalu gunakan jumlah bit yang sesuai dari tengah kotak agar mendapatkan hash-key. Jika kuncinya adalah string, dikonversi ke angka.

2. Division

Membagi string dengan operator modulus. Metode hashing integer ini merupakan metode yang paling sederhana.

3. Folding

Partisi string atau identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4. Digit Extraction

Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap alamat hash.

5. Rotating Hash

Menggunakan metode hashing lalu ketika mendapatkan kode atau alamat hash dari metode tersebut, maka lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

4. Collision

Ada dua cara untuk melakukan Collision :

1. Linear Probing, yaitu dengan mencari slot kosong berikutnya dan meletakkan string disana
2. Chainning, yaitu memasukkan string ke dalam slot sebagai linked list.

5. Tree Concept

1. Node A disebut sebagai root atau akar.
2. Garis yang menghubungkan induk ke anak adalah edge atau garis.
3. Node yang tidak memiliki anak disebut daun. Contohnya node E, F, G, dan H
4. Node memiliki orang tua yang sama disebut saudara. Contohnya node B.
5. Derajat simpul adalah total sub pohon simpul.
6. Tinggi atau kedalamanan tingkat maksimum node dalam pohon.
7. Jika ada garis yang menghubungkan A ke B, maka A leluhurnya B, dan B adalah keturunan A.

6. Binary Tree Concept

Sama seperti rooted tree, namun setiap node memiliki 2 anak. Node yang tidak memiliki anak disebut daun.

7. Type of Binary 

TreeTipe-tipe Binary Tree:

1. Perfect Binary Tree= setiap level memiliki kedalaman yang sama

.

2. Complete Binary Tree

3. Skewed Binary Tree

8. Property of Binary Tree

1. Jumlah maksimum node pada k di binary tree adalah 2k
2. Jumlah maksimum node pada pohon biner tinggi h adalah 2h+1 - 1.
3. Tinggi minimum biner dari n node adalah 2log(n).
4. Tinggi maksimum biner dari n nide adalah n-1.

9. Expression Tree Concept

1. Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menulis tanda kurung (). Contoh pemakaian prefix adalah +AB, – +ABC, * + AB – CD.
2. Infix adalah cara penulisan ungkapan dengan meletakkan operator diantara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi (). Contoh pemakaian infix adalah
A+B, A+B-C, (A+B)*(C-D).
3. Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung ().

10. Threaded Binary Tree Concept

Pohon biner berulir sama dengan pohon biner tetapi dengan perbedaan dalam menyimpan pointer NULL. Dalam representasi tertaut, sejumlah node berisi pointer NULL baik di bidang kanan atau kiri atau keduanya. Ruang yang terbuang untuk menyimpan tunjuk NULL ini dapat digunakan untuk menyimpan kedamaian informasi bermanfaat lainnya.

3.

Refrensi

http://suciantinovi.blogspot.com/2014/03/linked-list-i_14.html

https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/

Binus Maya

https://socs.binus.ac.id/2017/03/15/doubly-linked-list/
https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Binary Search Tree

Binary Search Tree

Pengertian

Sebelum masuk kedalam konsep Binary Search Tree, ada baiknya kita memahami konsep Tree itu sendiri. Tree adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (relasi one to many). 

Lalu apa perbedaannya dengan Binary Search Tree? Binary Search Tree adalah tree yang memiliki maksimal 2 percabangan saja, dan terdapat beberapa aturan. Child node sebelah kiri selalu lebih kecil daripada root node. Child node sebelah kanan selalu lebih besar daripada rootnode. Binary Search Tree biasa dikenal sebagai Sorted Version of Binary Tree.

Seperti pada gambar diatas, root node adalah 50, child node seblah kiri adalah 17, dan child node sebelah kanan adalah 76. Ini artinya child node sebelah kiri selalu lebih kecil dibandingkan root, dan child node kanan selalu lebih besar daripada root.

Operasi Binary Search Tree

Insert:

1. Selalu dimulai dari root.
2. Jika angka yang akan dimasukkan lebih kecil daripada sub tree, maka cek sebelah kiri dari sub tree. Bila kosong masukkan angka tersebut.
3. Bila angka yang akan dimasukkan lebih besar daripada sub tree, maka cek sebelah kanan dari sub tree. Bila kosong, masukkan angka tersebut.
4. Lakukan terus sampai menemukan node yang kosong untuk ditaruh sebuah nilai.

Deletion:

Untuk melakukan delete terdapat 3 situasi.

1. Bila yang ingin dihapus di bagian leaf, dapat langsung dihapus. Pada gambar diatas, 12 dapat langsung dihapus.
2. Bila yang akan dihapus memiliki satu child, hapus node tersebut dan gabungkan antara parent node tersebut dan child dari node tersebut. Pada gambar diatas, bila 72 dihapus, maka 54 menjadi parent 67.
3. Bila yang akan dihapus memiliki dua child, cari sub tree bagian kiri kemudian dibandingkan dengan yang kanan. Pada gambar diatas, apabila angka 17 dihapus maka, angka 14 akan naik menggantikan posisi 17, angka 9 akan menjadi parent 12. Bila angka 50 yang dihapus, maka angka 23 akan naik menggantikan posisi 50, dann17 akan menjadi parent 19.

Refrensi:

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Binus Maya

Hashing and Hash Table, Tree and Binary Tree

Materi Pembelajaran

1. Hashing
2. Hash Table
3. Hash Function
4. Collision
5. Tree Intoduction
6. Tree Concept
7. Binary Tree Concept
8. Type of Binary Tree
9. Property of Binary Tree
10. Expression Tree Concept
11. Threaded Binary Tree Concept

1. Hashing

Hashing dapat diartikan sebagai teknik untuk menyimpan dan mengambil kunci dengan cepat. Biasanya ini juga dapat disebut sebagai proses memetakan sejumlah besar item data ke tabel yang lebih kecil. 

2. Hash Table

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

Keuntungan dari hash table ini adalah waktu aksesnya yang cukup cepat. Namun pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Operasi yang digunakan dalam Hash Table:

1. insert = memasukkan nilai dalam tabel
2. find= mencari nilai dalam tabel
3. remove= mencari nilai dalam tabel, lalu dihapus
4. getIterator= memeriksa nilai satu per satu

3. Hash Function

Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode untuk membangun fungsi hash:

1. Mid-square

Kuadratkan string lalu gunakan jumlah bit yang sesuai dari tengah kotak agar mendapatkan hash-key. Jika kuncinya adalah string, dikonversi ke angka.

2. Division

Membagi string dengan operator modulus. Metode hashing integer ini merupakan metode yang paling sederhana.

3. Folding

Partisi string atau identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4. Digit Extraction

Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap alamat hash.

5. Rotating Hash

Menggunakan metode hashing lalu ketika mendapatkan kode atau alamat hash dari metode tersebut,  maka lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

4. Collision

Ada dua cara untuk melakukan Collision :

1. Linear Probing, yaitu dengan mencari slot kosong berikutnya dan meletakkan string disana
2. Chainning, yaitu memasukkan string ke dalam slot sebagai linked list.

5. Tree Concept

1. Node A disebut sebagai root atau akar.
2. Garis yang menghubungkan induk ke anak adalah edge atau garis.
3. Node yang tidak memiliki anak disebut daun. Contohnya node E, F, G, dan H
4. Node memiliki orang tua yang sama disebut saudara. Contohnya node B.
5. Derajat simpul adalah total sub pohon simpul.
6. Tinggi atau kedalamanan tingkat maksimum node dalam pohon.
7. Jika ada garis yang menghubungkan A ke B, maka A leluhurnya B, dan B adalah keturunan A.

6. Binary Tree Concept

Sama seperti rooted tree, namun setiap node memiliki 2 anak. Node yang tidak memiliki anak disebut daun.

7. Type of Binary Tree

Tipe-tipe Binary Tree:

1. Perfect Binary Tree= setiap level memiliki kedalaman yang sama.

2. Complete Binary Tree

3. Skewed Binary Tree

8. Property of Binary Tree

1. Jumlah maksimum node pada k di binary tree adalah 2k

2. Jumlah maksimum node pada pohon biner tinggi h adalah 2h+1 - 1.

3. Tinggi minimum biner dari n node adalah 2log(n).

4. Tinggi maksimum biner dari n nide adalah n-1.

9. Expression Tree Concept

1. Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menulis tanda kurung (). Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.

2. Infix adalah cara penulisan ungkapan dengan meletakkan operator diantara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi (). Contoh pemakaian infix adalah 

A+B, A+B-C, (A+B)*(C-D).
3. Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung ().

10. Threaded Binary Tree Concept

Pohon biner berulir sama dengan pohon biner tetapi dengan perbedaan dalam menyimpan pointer NULL. Dalam representasi tertaut, sejumlah node berisi pointer NULL baik di bidang kanan atau kiri atau keduanya. Ruang yang terbuang untuk menyimpan tunjuk NULL ini dapat digunakan untuk menyimpan kedamaian informasi bermanfaat lainnya.

3.

Refrensi : 

1. Binus Maya
2. https://www.google.com/url?sa=i&url=http%3A%2F%2Fyoutubesusanqenglmichelle.changeip.com%2Fuse-of-threaded-binary-tree.html&psig=AOvVaw0M4-eHdsIUnMmAPob31jtB&ust=1583950331759000&source=images&cd=vfe&ved=0CA0QjhxqFwoTCNDYnPnAkOgCFQAAAAAdAAAAABAP

Nama : Isaac Andrean Yoshua

NIM   : 2301927046