AVL Tree dan B-Tree
AVL Tree & B-Tree
AVL Tree
AVL Tree salah merupakan salah satu jenis dari Binary Search Tree. AVL Tree merupakan self balancing BST dimana perbedaan antara subtree kiri dan subtree kanan maksimal 1 level dan tidak boleh lebih. AVL Tree ini bertujuan untuk menyederhanakan Tree dan mempercepat waktu pencarian.
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
T adalah note yang harus diseimbangkan
Contoh AVL Tree :
sumber : https://socs.binus.ac.id/files/2016/12/vio-2-1.jpg
B-Tree
B-Tree merupakan Tree yang mana data nya disimpan secara berurutan sehingga memungkinkan terjadinya pencarian. B-Tree adalah pengembangan 2-3 Tree. Jadi aturab pada B-Tree mirip dengan 2-3 Tree.
Aturan-aturan dalam B-Tree m order
1. “Key” adalah Daya yang ingin di insert.
2. Sesuai dengan aturan BST untuk insert
3. Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
4. Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
5. Root memiliki anak minimal 2, selama root bukan leaf
6. Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
7. Data yang tersimpan pada node harus terurut secara inorder
8. Semua leaf berada pada level yang sama, level terbawah
Contoh B-Tree ordo 4
sumber : https://media.geeksforgeeks.org/wp-content/cdn-uploads/BTreeIntro1.png
Referensi :
https://www.geeksforgeeks.org/introduction-of-b-tree-2/
http://sysbreaker.blogspot.com/2014/05/b-tree-dan-heap-deap-tree.html
http://suciantinovi.blogspot.com/2014/05/b-tree-and-heap-deap.html
https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
https://www.google.com/search?q=geeksforgeeks+avl+tree&oq=geeks&aqs=chrome.1.69i57j69i59l2j0l2j69i60l3.1962j0j4&sourceid=chrome&ie=UTF-8
AVL Tree
AVL Tree salah merupakan salah satu jenis dari Binary Search Tree. AVL Tree merupakan self balancing BST dimana perbedaan antara subtree kiri dan subtree kanan maksimal 1 level dan tidak boleh lebih. AVL Tree ini bertujuan untuk menyederhanakan Tree dan mempercepat waktu pencarian.
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
T adalah note yang harus diseimbangkan
Contoh AVL Tree :
B-Tree
B-Tree merupakan Tree yang mana data nya disimpan secara berurutan sehingga memungkinkan terjadinya pencarian. B-Tree adalah pengembangan 2-3 Tree. Jadi aturab pada B-Tree mirip dengan 2-3 Tree.
Aturan-aturan dalam B-Tree m order
1. “Key” adalah Daya yang ingin di insert.
2. Sesuai dengan aturan BST untuk insert
3. Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
4. Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
5. Root memiliki anak minimal 2, selama root bukan leaf
6. Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
7. Data yang tersimpan pada node harus terurut secara inorder
8. Semua leaf berada pada level yang sama, level terbawah
Contoh B-Tree ordo 4
Referensi :
https://www.geeksforgeeks.org/introduction-of-b-tree-2/
http://sysbreaker.blogspot.com/2014/05/b-tree-dan-heap-deap-tree.html
http://suciantinovi.blogspot.com/2014/05/b-tree-and-heap-deap.html
https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
https://www.google.com/search?q=geeksforgeeks+avl+tree&oq=geeks&aqs=chrome.1.69i57j69i59l2j0l2j69i60l3.1962j0j4&sourceid=chrome&ie=UTF-8
Comments
Post a Comment