AVL TREE DAN B - TREE


AVL & B-TREE
AVL TREE :
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ levelmaksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untukmenyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian danbentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga tree tetapimbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru→ root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Prosespenyeimbangan dilakukan dengan: Single rotation dan Double rotation.
Penerapan struktur data AVL tree digunakan pada Binary Search Tree yangbertujuan untuk menyeimbangkan tree tersebut, sehingga waktu pencarian danstruktur tree dapat disederhanakan. AVL Tree dapat direpresentasikan denganmenggunakan Array maupun linked list. Contohnya untuk membuat programtingkatan pegawai dalam perusahaan dan silsilah keluarga.
Ø  AVL Tree
-        AVL Tree adalah height balanced 1-tree yang berarti maksimum perbedaanheight antara subtree kiri dan kanan adalah satu.
-        Path pencarian lokasi untuk dilakukan operasi insert dimulai dari Root.
-        Adanya node pada search path yang balancenya TallLeft (tanda -) atauTallRight (tanda +) dan terletak paling dekat dengan node yang baru

Insertion – AVL Tree
AVL Tree ditemukan oleh Adelson-Velskii dan Landis. AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.
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.
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
anggap T adalah node yang harus diseimbangkan kembali
– 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)
vio - 1
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation
Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root
vio - 2
Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insert node 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.
vio - 3



Deletion – 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.
Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
  • Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
  • anggap T adalah node yang harus diseimbangkan kembali
    – 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)
Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :
Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :
Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :
Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :






B-Tree :
Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree merupakan salah satu B-Tree berorder 3. Itu sebabnya setiap nodenya memiliki batasan anak, dengan minimal 2 anak dan maksimal 3 anak.

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

Berikut contoh B-Tree :

Operasi : Searching
Searching pada B-Tree mirip seperti 2-3 Tree. Pertama-tama kita bandingkan dengan rootnya terlebih dahulu kemudian cek apakah sama dengan rootnya atau lebih kecil atau lebih besar atau bahkan diantara rootnya (jika root memiliki lebih dari 1 data).

berikut ini adalah codingannya dalam C :
Operasi : Insertion
Aturan Insertion :
-        Anggap data yang mau di insert adalah key
-        Posisikan key pada node yang sesuai, seperti pada BST dan 2-3 Tree, anggap node tersebut A
-        Jika A adalah node dengan jumlah data kurang dari m-1, maka langsung masukan saja
-        Jika A adalah node dengan jumlah data m-1, maka masukan nilai tengah kemudian masukan ke parentnya. Kemudian anggaplah parent tersebut A. Kemudian periksa kembali sesuai aturan point ke 3 dan 4.

contoh :

gambar dibawah ini adalah operasi insertion pada b-tree berorder 5

Operasi : Deletion 
Aturan Deletion :
-        Anggap node yang mau di delete adalah key
-        Delete dilakukan pada leaf. Meskipun pada saat menghapus node parent, kita tetap menganggapnya menghapus leaf, karena ketika parent dihapus lalu digantikan oleh anak terbesar subtree kiri atau anak terkecil subtree kanan sama saja kita seolah-olah menghapus anak yang menggantikannya. dimana anak tersebut selalu berada pada posisi leaf. maka leaf tersebut dianggap P.
-        Jika ukuran P > m/2 maka langsung delete saja data yang ingin dihapus
-        Jika ukuran P = m/2 maka : perhatikan siblingnya (anggap sibling adalah Q)
-        Q > m/2, maka rotasi pada P
-        Q = m/2, satukan P dan Q

contoh :
delete pada b-tree order 5



CONTOH SOAL :
AVL dan B-Tree :
* insert: 5,6,7,0,4,3,8
* delete: 3,4,8
Jawaban :
AVL TREE- INSERT :
AVL TREE – DELETE :
B TREE – INSERT :
B TREE – DELETE :

Komentar

Posting Komentar

Postingan populer dari blog ini

Linked list - Binery Search Tree

LINKED LIST Linked list adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu computer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibuthkan. Linked list mirip dengan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time). Didalam banyak aplikasi, ukuran dari data tidak diketahui data compile, hal ini bisa merupakan suatu atribut yang baik juga. Setiap node akan berbentuk struct dan memiliki  satu buah field yang bertipe struct yang sama, yang berfungsi sebagai pointer. Dalam menghubungkkan setiap node, kita dapat menggunakan cara first-create-first-access maupun first-create-last-access. Linked list saling terhubung dengan bantuan variable pinter. Masing-masing data dalam linked list disebut dengan node (simpul) yan menempati alokasi memori secar dinamis dan biasanya berupa struct yang terdiri dari beberapa field. List atau diken...
Baca selengkapnya

Binary Search Tree

Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild 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. Binary Search Tree juga merupakan tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. D...
Baca selengkapnya