AVL Tree dan B-Tree

A. AVL Tree

AVL adalah balanced binary search tree yang memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal satu.


                                            

Untuk menentukan Height dan Balance Factor, gunakan cara berikut :

Height :
1. Jika node (root) tidak memiliki subtree heightnya = 0.
2. Jika node adalah leaf, height = 1.
3. Jika internal node, maka height = height tertinggi dari anak + 1.

Balance Factor :
1. Selisih height antara anak kiri dan kanan. Jika tidak memiliki anak dianggap 0.



Insertion
Insert suatu node pada AVL Tree sama dengan insert node pada Binary Search Tree. Node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di-insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di-insert.

Ada empat kondisi yang biasa terjadi saat melakukan operasi insert, yaitu :
(T = node yang harus diseimbangkan kembali)
1. Node terdalam terletak pada subtree kiri dari anak kiri T (left-left).
2. Node terdalam terletak pada subtree kanan dari anak kanan T (right-right).
3. Node terdalam terletak pada subtree kanan dari anak kiri T (right-left).
4. Node terdalam terletak pada subtree kiri dari anak kanan T (left-right).

Empat kondisi tersebut dapat diatasi dengan melakukan rotasi. Kondisi pertama dan kedua dapat diatasi dengan Single Rotation. Kondisi ketiga dan keempat dapat diatasi dengan Double Rotation.

Single Rotation
Single Rotation atau rotasi satu kali dilakukan apabila searah, left-left atau right-right.

                            


Double Rotation
Double Rotation atau rotasi dua kali dilakukan apabila dua arah, left-right atau right-left.








Deletion
Operasi penghapusan node pada AVL Tree sama seperti pada Binary Search Tree. Node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, periksa kembali apakah tree sudah seimbang atau belum. Jika belum seimbang, maka harus diseimbangkan kembali. Cara menyeimbangkannya sama seperti saat insert.



B. B-Tree

B-Tree adalah sebuah m-ary balanced search tree khusus yang digunakan dalam basis data karena strukturnya memungkinkan data yang disimpan untuk disisipi, dihapus, dan diambil dengan jaminan proses dengan waktu terburuk, di mana simpulnya terdiri dari (m/2) sampai m buah simpul anak, di mana m > 1 merupakan bilangan bulat. m adalah orde. Akar pohon B-Tree paling sedikit memiliki 2 simpul anak. Ini adalah struktur yang baik jika pohon digunakan pada memori yang lambat, karena ketinggian dan jumlah akses dapat diperkecil dengan mengambil bilangan m yang besar. Balanced Tree atau pohon seimbang adalah pohon di mana tidak ada simpul daun yang lebih panjang terhadap daun yang lain.


Insertion


                                
                                         




Deletion






LATIHAN SOAL

AVL dan B-Tree dengan soal :
Insert : 5, 6, 7, 0, 4, 3, 8
Delete : 3, 4, 8



AVL Tree (Insertion)

1. Insert(5)








2. Insert(6)


3. Insert(7)

4. Insert(0)

5. Insert(4)

6. Insert(3)

7. Insert(8)





AVL Tree (Deletion)

1. Delete(3)

2. Delete(4)

3. Delete(8)




B-Tree (Insertion)

1. Insert(5)

2. Insert(6)

3. Insert(7)

4. Insert(0)

5. Insert(4)

6. Insert(3)

7. Insert(8)



B-Tree (Deletion)

1. Delete(3)

2. Delete(4)

3. Delete(8)









Comments

Post a Comment

Popular posts from this blog

Hashing and Hash Tables, Trees & Binary Tree

A. HASHING      Hashing merupakan metode yang digunakan untuk menyimpan data dalam sebuah array agar dapat menyimpan data, mencari data, menambah data, dan menghapus data dengan cepat. Pengertian hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Dalam hashing, yang dilakukan adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array.      Hash Function atau Fungsi Hash merupakan fungsi yang mengembalikan nilai atau kunci. Hash Table atau Tabel Hash merupakan array yang digunakan. B. HASH TABLE      Hash Table merupakan sebuah struktur data, terdiri atas sebuah tabel dan fungsi. Fungsi pada Hash Table bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.      Kelebihan dari Hash Table adalah waktu mengakse...
Read more

Binary Search Tree

A. BINARY SEARCH TREE      Binary Search Tree adalah tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory.      Ciri-ciri Binary Search Tree : 1. Setiap node mempunyai value dan tidak ada value yang double. 2. Value yang ada di kiri tree lebih kecil dari rootnya. 3. Value yang ada di kanan tree lebih besar dari rootnya. 4. Kiri dan kanan tree bisa menjadi root lagi atau bisa mempunyai child. 5. Memiliki sifat rekursif.      Binary Search Tree memiliki tiga operasi dasar : 1. Find(x) : menemukan value x di dalam Binary Search Tree (Search) 2. Insert(x) : memasukkan value baru x ke Binary Search Tree (Push) 3. Remove(x) : menghapus key x dari Binary Search Tree (Delete) B....
Read more