B-Tree dan Heap-Deap Tree

B-Tree

B-Tree merupakan pengembangan dari 2-3 Tree. Sehingga aturan-aturan yang berlaku pun mirip.
Berikut beberapa hal yang perlu diketahui mengenai B-Tree:

• M adalah jumlah order tree tersebut. (Contoh: order 4 mempunyai maksimal 3 node dan 4 child).
• Semua "Leaf" berada level yang sama.
• Setiap Node (kecuali root) punya minimal M/2 children.
• Root memiliki paling tidak 2 children (bila bukan leaf)

Berikut contoh B-Tree (Order 4):
 

Insertion:

• Data yang ingin diinsert disebut "key".
• Insert sesuai aturan BST.
• Bila jumlah data pada Leaf tersebut kurang dari 4. Maka insert key di leaf tersebut.
• Jika tidak, push data tengah ke parent, belah sisi kiri dan sisi kanan.
• Lakukan rekusif pada parent.

Step 1:

Step 2:
       
Step 3:
        
Step 4:
         
Step 5:
         
         Penjelasan : Setelah data full, maka data tengah naik ke parent dan dipecah menjadi anak-kiri dan anak-kanan.

Step 6:
         
         Penjelasan : Bila data tidak full, maka hanya insert di leaf.

Deletion:

 Hal-hal yang perlu diperhatikan bila kita ingin menghapus (delete) "key" pada B-Tree:

         1. Cari "key"(data) pada leaf yang menggantikan "key yang ingin dihapus". Sehingga key node
    yang hapus berada pada leaf. (Misalkan leaf adalah p).
         2. Jika ukuran p > M/2, hapus key.
         3. Jika ukuran p = M/2:
                     a. Anggap Sibling menjadi q.
                     b. Jika ukuran q > M/2: Rotasi nilai ke p (melalui parentnya).
                     c. Jika ukuran q = M/2: Gabung p dan q (dan satu "key" dari parent).
                     d. Lakukan rekursif.

Contoh Deletion:

Step 1:

 

Step 2:

  

Step 3: 

 

 

 

Heap and Deap

Pengertian Heap : Complete Binary Tree yang mempunyai aturan Heap.

 Terdapat beberapa jenis Heap:
1. Min-Heap : Setiap node memiliki nilai yang lebih besar dibanding parentnya.
Contoh Min-Heap :
 

2. Max-Heap : Setiap node memiliki nilai yang lebih kecil dibanding perentnya.
 Contoh Max-Heap :


3. Min-Max-Heap : Mempunyai kombinasi selang-seling min-heap dan max-heap. Sehingga bila node mempunyai parent lebih kecil, maka childnya pun mempunyai nilai lebih kecil.
Contoh Min-Max-Heap :


4. Deap (Double ended Heap) : Gabungan dari Min-Heap dan Max-Heap. Nilai Root dikosongkan dan biasanya bagian kiri merupakan Min-Heap dan kanan merupakan Max-Heap.
Contoh Deap :

Bina Nusantara University                             skyconnectiva
 =============================End================================