BALANCED BINARY SEARCH TREE
Balanced Binary Search Tree memiliki anak yang memiliki height seimbang. Balanced Binary Search Tree yang pertama merupakan AVL. AVL berasal dari nama penemunya, yaitu G.M. Adelson-Veleskii dan E.M. Landis di tahun 1962.
Elemen dalam AVL:
- Height = MAX(H left, H right) + 1
- Balance Factor = (H left – H right)
Jika hasilnya:
(-) maka BST berat ke kanan
(+) maka BST berat ke kiri
Balance Factor yang ditoleransi dalam AVL adalah 1 dan -1. Apabila lebih dari 1 atau kurang dari -1, maka BST tidak balanced.
Proses balancing dalam AVL:
- Single Rotation
Apabila jalur violation berupa Left-Left (LL) atau Right-Right (RR), maka perlu dilakukan single rotation agar tree menjadi seimbang. - Double Rotation
Apabila jalur violation berupa Right-Left (RL) atau Left-Right (LR), maka perlu dilakukan rotation agar jalur violation menjadi Left-Left (LL) atau Right-Right (RR). Lalu dilakukan rotation sekali lagi agar tree menjadi seimbang.
Operasi dalam AVL:
- Insertion
Proses insertion sama seperti pada unbalanced BST, namun setiap kali ditemukan violation harus langsung dilakukan proses rotation hingga menjadi Balanced Binary Search Tree.
Contoh insert: 51, 26, 11, 6, 8, 4, 31
Deletion
Proses deletion sama seperti pada unbalanced BST, namun setiap kali ditemukan violation harus langsung dilakukan proses rotation hingga menjadi Balanced Binary Search Tree.
Contoh:
_______________________________________________________________________
GUEST LECTURE – Selvakumar Manickam
Mr. Manickam adalah seorang dosen dari Universitas Sains Malaysia. Beliau menjelaskan ulang mengenai elemen-elemen dari tree, yaitu parents, child, leaf dan sebagainya. Beliau juga membahas tentang AVL, Data Structure Complexity dan M-ary tree.
Data Structure Complexity:
M-ary Tree
M-ary Tree merupakan sebuah tree yang anaknya berjumlah lebih kecil atau sama dengan M (<=M). Suatu tree dapat disebut m-ary tree apabila setiap vertex memiliki child tidak lebih dari m.
Contoh:
