AVL-BTREE
AVL Tree and B-Tree
AVL Tree
AVL Tree merupakan bagian dari Binary Tree Search (BST), di mana AVL Tree memiliki depth untuk subtree sebelah kiri dan kanan memiliki perbedaan depth yaitu lebih kurang sama dengan satu.
Sehingga AVL Tree memiliki depth yang lebih stabil dibandingkan Binary Search Tree.
Untuk mempertahankan keseimbangannya AVL Tree memiliki method untuk menyeimbangkan tree, method ini disebut rotation.
Method rotation ini memiliki 4 macam, yaitu
1. Right Rotation
5 2
/ / \
2 ------------------> 1 5
/ Right Rotate
1
2. Left Rotation
5 8
\ / \
8 --------------------> 5 9
\ Left Rotate
9
3. Left - Right Rotation
5 5 4
/ / / \
2 ----------------> 4 ---------------> 2 5
\ Left Rotate / Right Rotate
4 2
4. Right - Left Rotation
7 7 8
\ \ / \
9 ---------------> 8 --------------> 7 9
/ Right Rotate \ Left Rotate
8 9
Contoh :
5 5 5 6
\ \ / \
---------> ---------> 6 ---------> 6 ---------> 5 7
Insert 5 Insert 6 Insert 7 \ Left
7
6 6 6
/ \ / \ / \
---------> 5 7 ---------> 5 7 --------------> 4 7 --------->
Insert 0 / Insert 4 / Left - Right / \ Insert 3
0 0 0 5
\
4
6 4 4
/ \ / \ / \
4 7 0 6 0 6
/ \ ----------------> \ / \ ---------> \ / \ ---------->
0 5 Left - Right 3 5 7 Insert 8 3 5 7 Delete 3
\ \
3 8
4 6 6
/ \ / \ / \
0 6 ---------> 4 7 ----------> 0 7 ----------->
/ \ Left / \ \ Delete 4 \ \ Delete 8
5 8 0 5 8 5 8
6
/ \
0 7
\
5
B-Tree
B-Tree merupakan salah satu self-balancing search tree, di mana di dalam B-Tree untuk satu node dapat menampung lebih dari satu data, sehingga depth untuk B-Tree lebih kecil dibanding dengan tree yang lain. Untuk ukuran dari nodenya dapat kita tentukan, dan jumlah untuk sub node harus sesuai dengan jumlah data dari node ditambah satu.
 |
| https://media.geeksforgeeks.org/wp-content/cdn-uploads/BTreeIntro1.png |
Contoh untuk max 3:
5 5 6 6 6
/ \ / \
---------> ---------> ----------> 5 7 ---------> 0 5 7 ---------->
Insert 5 Insert 6 Insert 7 Insert 0 Insert 4
4 6 4 6 4 6 4 6
/ | \ --------> / | \ ---------> / | \ ----------> / | \
0 5 7 Insert 3 0 3 5 7 Insert 8 0 3 5 7 8 Delete 8 0 5 7 8
6 6
---------> / \ ----------> / \
Delete 4 0 5 7 8 Delete 8 0 5 7
Reference:
Komentar
Posting Komentar