ALGORITMA DAN STRUKTUR DATA : BAB 11

11. 1 HEAP (COMPLETE BINARY TREE )

Heap atau sering juga disebut Complete Binary Tree harus memenuhi karakteristik ini :
• Jika suatu node mempunyai child, maka jumlah childnya harus selalu dua.
• Semua node dalam heap harus memenuhi persamaan :

  • r[i] < r[2] dan r[i] < r[2i+1] untuk minimum Heap, yang mempunyai arti bahwa nilai
    parent harus selalu lebih kecil dari kedua anaknya.
  • r[i] > r[2i] dan r[i] > r[2i+1] untuk maximum Heap, yang mempunyai arti bahwa nilai
    parent harus selalu lebih besar dari kedua anaknya.

Gambar di bawah ini memperlihatkan contoh minimum Heap

Gambar
Gambar 11.1: Minimum heap

Representasi dengan menggunakan ARRAY akan menghasilkan

Gambar

Sedangkan gambar di bawah ini merupakan contoh untuk maksimum Heap

Gambar
Gambar 11.2: Maximum heap

Representasi dengan menggunakan ARRAY akan menghasilkan

Gambar

 

11. 2 OPERASI HEAPCREATE

Operasi HeapCreate berfungsi untuk menciptakan heap, dengan cara mengurutkan nilai dari
nodanya, Prosedur untuk melakukan HeapCreate adalah sebagai berikut :
1. Mulai dari LEAF,yang mana semua LEAF telah memenuhi persyaratan HEAP.

2. Ambil salah satu parent dari LEAF, teliti apakah sudah memenuhi syarat HEAP (harus
ditentukan terlebih dahulu apakah yang ingin diciptakan adalah maksimum HEAP atau
minimum HEAP ).

3. Bila belum memenuhi persyaratan, maka lakukan tukar tempat :
• Untuk maksimum HEAP, tukar tempat parent dengan child yang paling BESAR.
• Untuk minimu HEAP, tukar tempat Parent dengan child yang paling kecil.

Contoh :
Apabila diketahui TREE di bawah ini, yang masih belum memenuhi persyaratan Maksimum HEAP,
lakukan operasi HeapCreate.

Gambar

Bila ditambahkan angka 90 ke dalam Tree yang berada di dalam kotak, maka Tree tersebut menjadi
tidak maksimum Heap lagi, yang harus dilakukan adalah tukar tempat antara 90 (parent) dengan 450
(Child yang mempunyai nilai paling besar), sehingga Tree tetap menjadi Maksimum Heap, Hasilnya
ditunjukan oleh gambar di bawah ini :

Gambar

Apabila ditambahkan angka 110 ke dalam Tree yang berada kotak, maka kembali Tree menjadi tidak
maksimum heap, lakukan hal sama seperti diatas, yaitu dengan menukarkan angka 110 (parent )
dengan angka 550 (Child dengan nilai paling besar), hasilnya ditunjukkan oleh gambar di bawah ini

Gambar

Apabila diteruskan dengan menambahkan angka 40 (parent) maka lakukan tukar tempat antara angka
40 dengan angka 450 (child dengan nilai paling besar). Ternyata setelah dilakukan tukar tempat,
masih belum menghasilkan maksimum Heap, karena masih ada child dari 40 yang nilainya lebih
besar. Lakukan lagi pertukaran tempat antara angka 40 dengan angka 90 hasilnya adalah sebagai
berikut :

Gambar

Langkah terakhir yang dilakukan adalah dengan menambahkan angka 80, yang harus tukar tempat
dengan angka 550, dilanjutkan dengan tukar tempat antara 80 dengan 330. Hasil akhir berupa
maksimum heap seperti ditunjukkan gambar di bawah ini:

Gambar

 

11. 3 B-TREE

B-Tree merupakan satu-satunya Tree yang mana Nodenya bisa berisi lebih dari 1 elemen. Jumlah
elemen dalam suatu node tergantung kepada Order dari B-Tree tersebut, dengan ketentuan:
Node ROOT :
• Jumlah minimum elemen 1
• Jumlah maksimum adalah 2d

Node lain yang bukan ROOT :
• Jumlah minimu elemen dalam setiap node (kecuali ROOT) adalah d.
• Jumlah maksimumnya adalah 2d, dimana d adalah order.

Hal ini yang dapat ditentukan pada B-Tree adalah jumlah children dari suatu node, yaitu minimunya
adalah 0 (berarti node tersebut adalah LEAF), dan maksimumnya adalah jumlah maksimumnya
elemen dalam node tersebut ditambah satu.

11.3.1 Operasi INSERT

Pada setiap kali penambahan (insert) elemen ke dalam node, harus dijaga agar jumlah elemen di
dalam node maksimunya adalah 2d. Ada 2 kasus yang dapat terjadi pada saat dilakukan insert
elemen ke dalam node yaitu :
Kasus 1 : Insert langsung

> jika node belum penuh yang berarti jumlah elemen dalam node masih < 2d, maka elemen
baru bisa langsung diinsert ke dalam node tersebut

Contoh :
Bila diketahui order dari B-Tree=2, yang berarti maksimum elemen pada sebuah node adalah = 2d =
4 elemen.
B-Tree sebelum di insert

Gambar

Kasus 2 :Insert dengan Split Node
􀃆 Jika node sudah penuh, yang berarti jumlah elemen dalam node sudag 2d. Maka
penambahan elemen baru mengakibatkan jumlah elemen menjadi > 2d hal ini tidak
diperkenankan karena maksimum elemen dalam node hanya 2d. Apabila terjadi hal ini,
maka perlu dilakukan Node Split dengan langkah:
• Split node menjadi 2
• Letakkan d elemen terkecil di node kiri
• Letakkan d elemen terbesar di node kanan
• Letakkan d elemen ditengah ke node parentnya
Contoh :
Diketahui B-Tree dengan Order = 2, dengan kondisi sebelum diinsert sebagai berikut ;

Gambar

 

11. 3. 2 Operasi DELETE
Kebalikan dari operasi Insert, maka dalam Operasi Delete harus dijaga agar dijumlah elemen dalam
node tidak lebih kecil dari d (atau untuk ROOT, minimal 1 elemen dalam node). Terdapat 3 kasus
yang dapat terjadi pada saat penghapusaan elemen yaitu :
Kasus 1 : Delete langsung
􀃆 Jika target node yang akan dihapus berisi elemen > d, maka elemen bisa langsung
dihapus tanpa perlu diregenerate. Dalam hal ini dapat langsung dihapus karena jumlah
elemen dalam node tersebut belum mencapai jumlah minimum.
Contoh :
Diketahui B-Tree dengan Order =2, dengan kondisi sebelum didelete sebagai berikut :

Gambar

 

Kasus 2: Delete dengan peminjaman elemen
􀃆 jika target node yang akan dihapus berisi d elemen , maka target elemen tidak bisa
langsung dihapus karena penghapusan langsung akan menyebabkan underflow. Untuk
mencegah terjadinya underflow maka harus dilakukan regenerasi yang akan dilakukan
dengan meminjam elemen dari node yang berada di kiri atau berada di kanan, yang
memiliki jumlah elemen > d. Langkah pengerjaannya adalah sebagai berikut :
• Delete target elemen dari node ybs.
• Pinjam elemen dari node yang memiliki jumlah elemen > d
• Jadikan elemen yang dipinjam menjadi parent ( ditarik ke atas).
• Parent yang semula dijadikan elemen dalam node ybs.

Contoh :
Bila diketahui B-Tree dengan Order =2 dengan kondisi seperti ditunjukan oleh gambar di bawah ini :

Gambar

 

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s