Skip to main content

AVL

AVL TREE

AVL Tree merupakan bentuk sempurna / stabil dari struktur data BST dimana jumlah child di sebelah kiri dan kanan node selisihnya tidak lebih besar sama dengan 2

Contoh AVL

Pada gambar diatas dapat diihat bahwa tidak ada node yang jumlah left child dan right child yang selisihnya lebih besar dari satu sehingga struktur data ditas disebut AVL

Berikut merupakan contoh Skewed BST / BST yang dimana weight sebelah kiri dan kanannya tidak seimbang

Operasi yang dapat dilakukan di AVL sama dengan yang dapat dilakukan di BST : 
- Insert
- Update 
- Delete

Perbedaanya terletak pada setelah operasi tersebut sudah selesai dilakukan dimana akan melakukan pengecekan apakah bst nya balanced atau tidak 

Ada 4 kondisi yang mempengaruhi : 
- Single Left Rotation (LL Rotation)
Pada kondisi ini, setiap node berpindah posisi ke kiri dari posisi awal
- Single Right Rotation (RR Rotation)
Pada kondisi ini, setiap node berpindah posisi ke kanan dari posisi awal
- Left Right Rotation (LR Rotation)
Gabungan antara left rotation dan right rotation yaitu akan berpindah ke kiri dan kemudian ke kanan dari posisi semula
- Right Left Rotation (RL Rotation)
Gabungan antara right rotation dan left rotation dan, urutannya dari right rotation dan kemudian left rotation




Comments

Post a Comment

Popular posts from this blog

Review

Single Linked List  merupakan suatu sistem penyimpanan dimana memori yang digunakan untuk penyimpanan digunakan secara dinamis (memori yang digunakan sesuai dengan ukuran dari data yang ditampung) Struktur Single Linked List (node) :  - Data yang ditmapung, dapat berupa : char,int, bool dan sebagainya - Pointer next   yang merefernce ke alamat node setelahnya Pendeklarasian: struct Mahasiswa{ char nama[20]; char nim[20]; struct Mahasiswa * next; }; Dalam  Single Linked List  dapat dilakukan juga : Insert, Delete maupun Update Ada beberapa cara dalam menginsert node baru : - Insert di awal ( head ) - Insert di akhir ( tail ) - Insert di  next  dari node yang ditunjuk Double Linked List  merupakana salah satu perkembangan dari single linked list yaitu penyimpanan data secara dinamis (menggunakan memori secukupnya) Struktur Double Linked List :  - Data yang ditampung, dapat ...
Post a Comment
Read more

Heap dan Trie

HEAP heap merupakan algoritma yang konsepnya hampir sama dengan Tree yaitu memilki satu buah root yang akan becabang menampung node node lain yang memliki datanya masing - masing. Heap memilki dua struktur, yaitu :  - Max Heap  merupakan heap yang rootnya mempunyai value terbesar dan menampung node node yang memilki nilai value yang lebih kecil. - Min Heap merupakan heap yang rootnya mempunyai value terkecil dan menampung node node yang lebih besar dari value si root. Pengimplementasian heap digunakan pada Heap Sort (Heapify) :  - Descending membentuk max heap dari data yang diinput dan kemudian mereplace elemen terakhir dengan elamen terbesar di heap, heapify treenya dan kemudian ulangi prosesnya sampai arraynya tersorted - Ascending membentuk  min heap  dari data yang diinput dan kemudian mereplace elemen terakhir dengan elamen terkecil di heap, heapify treenya dan kemudian ulangi prosesnya sampai arraynya tersorted ...
Post a Comment
Read more

Stack and Queue

Stack & Queue Stack adalah konsep dimana dalam suatu linked list akan dilakukan penghapusan pada node terakhir baru node sebelumnya atau biasa orang menyebutnya dengan konsep "LIFO" (Last In First Out) Konsep Stack : - Pop : untuk menghapus data  - Push : untuk menambah data baru - Insert dan delete dari awal data 'top' Queue adalah konsep dimana node pertama yang masuk akan meninggalkan node tersebut duluan atau bisa dibilang sesuai dengan artinya yaitu 'antri'. Jadi Queue menggunakan konsep 'FIFO' (First In First Out) Konsep Queue: - Enqueue : menambah data - Dequeue : menghapus data - Insert dimulai dari data terakhir - Delete dimulai dari data pertama  References : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/ cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html
Post a Comment
Read more