Mengetahui lebih dalam tentang 2-3 Tree

Sehubungan dengan tugas yg diberikan,maka mari kita pelajari bersama-sama!
Penjelasan awal,

2-3 Tree adalah sebuah data structure dimana setiap node yang memiliki children memiliki setidaknya 2 children dan satu data elemen atau tiga children dan dua data elemen. Leaf node tidak memiliki children tetapi memiliki satu atau dua data elemen.

Syarat-syarat 2-3 Tree:

• Setiap non-leaf adalah sebuah 2 node atau 3 node.

• Sebuah 2 node mengandung satu data elemen dan dua children.

• Sebuah 3 node mengandung dua data elemen dan memiliki tiga children.

• Semua leaf berada pada level yang sama(level paling bawah).

• Semua data disimpan secara berurutan.

Keterangan :Jika A adalah data yang ada didalam 2 node. Sub-tree kiri seharusnya mengandung data yang lebih kecil daripada A, sub-tree tengah seharusnya mengandung data lebih dari A.Jika A dan B adalah data yang ada didalam 3 node. Sub-tree kiri seharusnya mengandung data lebih kecil daripada A, subtree tengah seharusnya mengandung data lebih besar daripada A dan kurang dari B, sub-tree kanan seharusnya mengandung data lebih besar daripada B.• Contoh 2-node : Node yang berisi 1 data dan mempunyai 2 child.

•Contoh 3-node : Node yang berisi 2 data dan mempunyai 3 child.

Ada 3 macam bentuk organisasi dalam 2-3 tree:

1. tree 2-3 yg kosong.
2. tree 2-3 yg terdiri dari 1 ROOT 2- node dan memiliki 2 children.(contoh dambar di ats)
   
3. tree 2-3 yg terdiri dari 1 ROOT 3- node dan memiliki 3 children.(contoh gambar di ats)
   

2-3 TREE INSERTION :
syarat tree insertion:
1. Pertama tentukan dahulu dimana key akan diletakkan menggunakan algoritma
search, key pasti ditempatkan pada node leaf.
2. Jika node tadi adalah 2-node, maka letakkan saja key tersebut disitu.
3. Jika nodenya adalah 3-node, maka jadikan data tengah dari key, A, dan B (A
dan B adalah data yang sudah ada sebelumnya di dalam node), menjadi
parent, dan split 2 data tersisa menjadi 2 buah 2-node. Cek apakah parent
adalah 3-node, jika iya maka ulangi langkah 3 sampai parent menjadi 2-
node.
Contoh Insertion:














Gambar a. Insert A,L,G,O & R,saat memasukkan R,O naik ke ats sehingga menjadi 3-node.















Gambar b. Insert I,T,H,M & S.

Deletion dalam 2-3 Tree:
Syarat Deletion:

• Jika kita ingin meng-delete sebuah data elemen dari 2-3 Tree.

• Seperti BST(Binary Search Tree), kita harus mencari sebuah leaf dimana ada key yang mau kita delete. Artinya deletion selalu terjadi didalam sebuah leaf node.

• Jika leafnya berupa 3 node, maka delete datanya agar menjadi 2 node.

• Jika leafnya berupa 2 node:

• Jika parenya berupa 3 node, ambil satu nilai darinya. Jika siblingnya 3 node, push salah satu nilai dari siblingnya ke parentnya(untuk menjadikan parentnya menjadi 3 node lagi).

• Jika siblingnya adalah 2 node, maka parentnya adalah 2node dan digabungkan ke node yang sekarang dengan siblingnya.

• Jika parentnya adalah 2 node. Jika siblingnya 3 node maka ambil satu nilai dari parentnya dan push satu nilai dari sibling ke parentnya. Yang lain digabungkan ke parentnya dengan siblingnya.

Contoh Deletion:














Gambar c. Delete 70,90 dan 60. saat mendelete 60,node tgh menjadi kosong sehingga 50 harus turun menggantikan posisi 60.















Gambar d. Delete 95(80 harus mengisi node tgh sesuai syarat yg berlaku),50(delete saja),10. saat mendelete 10,80 harus naik mengisi posisi semula karena sudah tidak ada node kiri maupun kanan.

Untuk Video 2-3 Tree:

http://www.youtube.com/watch?v=bhKixY-cZHE