AVL Tree dan Binary Tree

Nama:Vincentius Arianto
NIM:2301921061

Hari:Selasa, 16 Juni 2020

Kelas besar: CB01-CL

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

Kelas kecil: LC04-LEC

Lecturer: Julian Wesley ( D5320 ) dan Renaldy ( RX192 )

Balanced Binary Tree (AVL Tree)

AVL Tree adalah sebuah  balanced binary search tree yang memiliki perbedaan tinggi

maksimal satu diantara subtree di kiri dan subtree di kanan. AVL Tree digunakan untuk

menyeimbangkan binary search Tree yang tidak seimbang. Dengan menggunakan AVL

Tree, waktu pencarian dalam tree akan lebih cepat karena seimbang.

Cara menentukan tinggi dan Keseimbangan

Tinggi :

- Jika node (root) tidak memiliki subtree tingginya = 0

- Jika node adalah leaf, tinggi =  1

- Jika node internal, maka tinggi =  tinggi tertinggi dari anak node + 1

Keseimbangan :

-selisih tinggi diantara anak di kiri dan di kanan, jika node tidak memiliki anak, maka

dianggap 0.

Kalau keseimbangan bukan 1,0, atau -1 maka tidak balance

ada 4 case:

Case 1 : LL the deepest node is located at the left sub tree of the left child of T.

Case 2 : RR the deepest node is located at the right sub tree of the right child of T.

Case 3 : RL the deepest node is located at the right sub tree of the left child of T.

Case 4 : LR the deepest node is located at the left sub tree of the right child of T.

Jika case 1 and 2 (left-left atau right-right) dibenarkan oleh single rotation.

Jika case 3 and 4 (left-right atau right-left) dibenarkan oleh double rotation.

B-Tree

B-Tree atau dikenal istilah order adalah sebuah self balancing search tree.Order

dalam B-Tree menentukan jumlah maksimum/minimum anak yang dimiliki oleh

setiap node. 2-3 Tree merupakan salah satu B-Tree yaitu 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