AVL Tree & B-Tree

AVL Tree
AVL Tree merupakan salah satu jenis BST (binary Search Tree) yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree dibentuk untuk menyeimbangkan Binary Search Tree, supaya waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. 

(Sumber: https://medium.com/@aksh0001/avl-trees-in-python-bc3d0aeb9150)

Metode penyeimbang ini dibagi menjadi 4 metode berdasarkan kondisi tree setelah melakukan insert, yaitu :

• Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
• Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
• Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
• Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

*T adalah node yang harus diseimbangkan kembali.

B-Tree
B-tree adalah suatu metode untuk menyimpan dan menemukan suatu file (disebut juga records atau keys) dalam suatu database. Algoritma b-tree meminimalkan jumlah dari media yang harus dilalui untuk mencapai suatu record database yang diinginkan sehingga akan mempercepat proses.

(Sumber: https://dzone.com/articles/database-btree-indexing-in-sqlite)

Aturan pada B-Tree : m = order

• Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
• Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
• Root memiliki anak minimal 2, selama root bukan leaf
• Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
• Data yang tersimpan pada node harus terurut secara inorder
• Semua leaf berada pada level yang sama, level terbawah

Dalam prakteknya b-tree bisa memiliki ribuan atau jutaan record. Tidak harus semua leaves memiliki suatu record, namun paling tidak adalah separuhnya harus memiliki. Perbedaan depth antara skema b-tree dan binary-tree adalah dalam penggunaan di sebuah sistem database dimana b-tree bisa memiliki order yang lebih tinggi, misalnya 32,64,128 atau lebih..

Contoh Insert dan Delete AVL Tree

Link :
https://drive.google.com/file/d/1C3H8-sHIGwofuIQzMR3DArwK22WrKfZ0/view?usp=sharing

Contoh Insert dan Delete B-Tree

Link :
https://drive.google.com/file/d/1Q0oz4jwEjYyulGO0fhvr0Y1uOQR4oxOJ/view?usp=sharing

Summary

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.

Linked List dan Array

(Sumber: https://www.pinterest.se/pin/741757001101474327/)

Array

Variable bertipe array adalah suatu tipe data yang bersifat statis (urutan dan ukuran sudah pasti). Kelemahan dari array statis adalah penggunaan ruang memori yang sudah digunakan tidak dapat dihapus apabila nama variable array tersebut sudah tidak digunakan kembali dalam suatu program (penyebab kemubaziran).

Circular Linked List

(Sumber: https://algorithms.tutorialhorizon.com/circular-linked-list-complete-implementation/)

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.

Doubly Linked List

(Sumber: https://www.studytonight.com/data-structures/doubly-linked-list)

Double Linked List adalah Linked List yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut Linked List yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika Linked List tersebut masih kosong.

Konsep Stack

(Sumber: https://dev.to/rinsama77/data-structure-stack-and-queue-4ecd)

Stack adalah metode atau teknik dalam menyimpan atau mengambil data ke dan dari memori. Stack dapat diibaratkan sebuah tumpukan dalam suatu tempat yang hanya memiliki suatu pintu diatasnya. kaidah stack adalah First In Last Out atau Last In First Out (LIFO), benda yang terakhir masuk akan menjadi benda yang pertama dikeluarkan.

Notasi Infix, Postfix, dan Prefix

(Sumber: http://risasisteminformasi.blogspot.com/2013/02/notasi-prefixinfix-dan-postfix.html)

Notasi ini terbentuk dari Operand dan Operator. Operand adalah data atau nilai yang membantu dalam proses,sedangkan Operasi adalah fungsi yang digunakan dalam proses. Setelah kita mengenal dan mengetahui dengan Operand dan Operator, maka mari kita mengenal juga tingkat/ level yang ada didalam notasi tersebut:

1.  ( ) (Kurung).

2.  ^ (Pangkat).

3.  * / (Perkalian / Pembagian).

4.  + - (Penjumlahan / Pengurangan).

1. Infix : notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.

2. Postfix : notasi yang membentuk atas operator dengan operand, dimana operator berada diantara operand.

3. Prefix : notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.

Contoh : A + B * C

  maka notasi postfix adalah ABC*+.

Konsep Queue

(Sumber: https://saungkode.wordpress.com/2014/04/10/konsep-queue-antrian-pada-struktur-data/)

Prinsip kerja Queue adalah FIFO (First In First Out), di mana data yang masuk terlebih dahulu akan keluar pertama.