Meruppakan suatu tree
dimana internal nodenya merupakan node-2 atau
node-3 dan semua leafnya berada pada level yang sama
.
Yang kiri merupakan contoh node 2 dimana pada node 2 akan ada 1 data dan mempunyai 2 anak, sedangkan yang kanan merupakan node 3 dimana pada node 3 akan ada 2 data dan mempunyai 3 anak.
Gambar dibawah ini merupakan contoh dari 2-3 Tree:
Satu hal yang paling penting pada 2-3 Tree adalah tree ini harus lah seimbang dalam arti jika ada node 3, maka ia harus punya 3 anak(kecuali root).
Operasi pada 2-3 tree:
1.
Insert
a. Kalau insert pasti data kita taruh terlebih dahulu di
leaf
b. Kalau data baru tersebut akan diinsert di 2-node maka
langsung taruh saja.
c. Kalau data baru tersebut diinsert di 3-node(2 data dlm
1 kotak) maka push nilai tengah diantara 3 data tersebut ke atas(parentnya) dan
nilai kiri dan nilai kanan di split/pisah, begitu seterusnya.
Contoh:
a
b
Pada gambar a dapat terlihat bahwa node nya sudah ppenuh, oleh karena itu diantara ketiga data tersebut kita push nilai tengah(2) ke parent, karena parent kosong maka ia menjadi root dan 1 serta 3 memisah jadi anak kiri dan anak kanan dari 2.
*Note biasanya digambarkan dengan kotak bukan dengan oval seperti gambar diatas.
2.
Delete
a.
Jika leafnya
node-2
:
i.
Jika parent
node-3
: ambil salah satu datanya.
1.
Jika kedua
siblingnya node-3 : masukan salah satu data sibling ke parent.
2.
Jika ada
sibling node-3 diapit oleh node-2&yg dhps node 2 nya,maka berlaku seperti
poin 1.
3.
Jika salah satu sibling
node-2 : Satukan data tersebut dengan siblingnya yg node-2
ii.
Jika parent
node-2 :
1.
Jika sibling node-3 : ambil satu data dari parent dan masukan salah satu data sibling
ke parent.
2.
Selain sibling node-3 : gabungkan parent dengan sibling
b.
Jika leaf node
3 maka hapus saja datanya.
Contoh delete:
Delete 1
*Dari kiri ke kanan lalu kebawah
Tidak ada komentar:
Posting Komentar