Tugas Pra UAS : 2-3 Tree

NURAHMAN
1401137755
02PVT

2-3 Tree adalah pohon struktur data yang mempunyai 2 jenis node, yaitu 2-node dan 3-node. Jika anda sudah mengenal B-tree maka 2-3 Tree adalah B-tree dengan order 3.

Node dalam 2-3 Tree :
• 2-node : Node yang berisi 1 data dan mempunyai 2 child.

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

Properti 2-3 Tree :
1. Setiap internal node (node yang bukan leaf / node yang mempunyai child)
   pasti salah satu dari 2-node atau 3-node.
2. Semua data dalam keadaan terurut secara ascending dari kiri ke kanan.
3. Semua leaf berada pada level yang sama.
4. Node baru diinsert dalam node leaf, dan setelah insert tree harus tetap
   memenuhi syarat-syarat 2-3 tree.

2-3 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 :
Disediakan tree berikut ini :

Insert 40, 75, 38 ke dalam tree !

1. Insert 40, Langsung saja masukkan 40 karena masuk dalam 2-node.

2. Insert 75, Karena masuk ke dalam 3-node maka kita jadikan 70 atau data
   tengah dari 60, 70, 75, menjadi parent. Split 60 dan 75 masing-masing
   menjadi 2-node. Karena parent adalah 2-node (hanya berisi data 50) maka
   selesai.

3. Insert 38, Karena masuk ke dalam 3-node maka kita jadikan 40 (data tengah)
   menjadi parent.

    Split 38 dan 45 masing-masing menjadi 2-node. Karena parent adalah 3-node
   (berisi data 50 & 70) maka kita jadikan lagi data tengah dari 40, 50, dan
   70, menjadi parent.

Simulasi insert dapat dilihat di : http://nurahman11.blogspot.com/2011/06/blog-post.html

Sedangkan penjelasan delete dan contoh soal 2-3 tree ada di post saya yang selajutnya :
http://nurahman11.blogspot.com/2011/06/deletion-2-3-tree.html