AVL Tree dan B-Tree

AVL Tree
AVL Tree adalah binary search tree yang telah disortir menjadi seimbang. AVL Tree merupakan nama dari kedua penemu AVL Tree yaitu G.M.Adelson Veleskii dan E.M.Landis.

Contoh AVL Tree:


Contoh Binary Search Tree yang belum di sortir:


Cara menentukan Height dan Balance Factor :
Height :
- Jika node (root) tidak memiliki subtree heightnya = 0
- Jika node adalah leaf, height =  1
- Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor :
-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

Ada 2 jenis rotation dalam AVL Tree:
1. Single Rotation


2. Double Rotation
Rotasi pertama:


Rotasi kedua:



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:
- 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

Contoh 2-3 Tree:
Lecture 10 - B-trees: Perfectly Height-balanced M-way search trees


Contoh Order 4-5:


Sumber:
http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html
http://suciantinovi.blogspot.com/2014/05/b-tree-and-heap-deap.html

Comments

Post a Comment

Popular posts from this blog

Heap and Tries

Image
Heap and Tries Heap Heap adalah struktur data khusus berbasis pohon di mana pohon adalah complete binary tree. Umumnya, Heaps dapat dua jenis: Max-Heap: dalam Max-Heap, key yang ada di node root harus terbesar di antara key yang ada di semua child. Properti yang sama harus dapat direkursif untuk semua sub-tree di binary tree. Min-Heap: dalam Min-Heap, key yang ada di node root harus minimum di antara key yang ada di semua child. Properti yang sama harus dapat direkursif  untuk semua sub-tree di binary tree. Min Heap Setiap node lebih kecil dari masing-masing childnya Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node Max Heap Setiap node lebih besar dari masing-masing childnya Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node Min-Max Heap Heap dengan Min heap pada level ganjil dan Max heap pada level genap Heap dapat diimplementasi dengan array maupun de
Read more

Summary of Data Structures

Image
Summary of Data Structures Nama      : Brian Eniko Singgih NIM        : 2301875074 Kelas       : CB01 Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460) Linked List 1. Circular Single Linked List Circular single linked list adalah single linked list yang tidak menerima value NULL yang dikarenakan node terakhir akan menunjuk ke head pointer sehingga circular single linked list tidak menerima value NULL. 2. Doubly Linked List Doubly linked list adalah single linked list yang memiliki 2 arah pointer dimana sebuah node memiliki 2 pointer yaitu next dan prev. Ada 2 cara untuk menyunting doubly linked list: a. Insert Insert digunakan untuk memasukan node baru ke dalam doubly linked list dan mengkoneksikan node tersebut dengan node yang sudah ada. struct tnode *node = (struct tnode*) malloc (sizeof (struct tnode); node->value = x; node->next  = NULL; node->prev  = tail; tail->next = node; tail = node; b. Delete Delete d
Read more