2-3 Tree (Struktur Data)

Definisi
dalam bidang computer science, 2-3 Tree adalah salah satu tipe struktur data, dimana setiap node dengan anaknya, memiliki 2 children dan 1 elemen data (2 node) atau 3 children dan 2 elemen data (3 node). perlu diketahui, bahwa 2-3 Tree bukan Binary Tree.

2-node

3-node

 







Sifat-sifat 2-3 Tree :

• Setiap non-leaf terdapat 2-node atau 3-node. Sebuah 2-node berisi satu item data dan memiliki dua anak/children (anak kiri dan anak tengah). Sebuah 3-node berisi dua item data dan memiliki 3 anak/children (anak kiri, tengah, dan kanan).
• Semua leaf berada di level yang sama (level bawah/bottom level).
• Semua data yang disimpan akan diurutkan :
  1. Misalkan A adalah data yang tersimpan di 2-node. Subtree kiri harus berisi data yang nilainya lebih kecil dari A. Subtree tengah harus berisi data yang nilainya lebih besar dari A.
  2. Misalkan A dan B adalah data yang tersimpan di 3-node. Subtree kiri harus berisi data yang nilainya kurang dari A. Subtree tengah berisi nilai antara A dan B, dan subtree kanan berisi nilai yang lebih dari B.
    

contoh 2-3 Tree :

Insertion pada 2-3 Tree

ketika kita ingin memasukkan data baru ke 2-3 Tree, maka kita harus melakukan beberapa tahapan :

1. Misalkan kita memasukkan data baru.
2. Pertama-tama, kita harus mencari dimana data tersebut harus diletakkan di 2-3 Tree menggunakan algoritma pencarian, maka akan terdapat 1 leaf yang tepat untuk diletakkan.
3. Jika leaf yang dituju adalah 2-node, maka kita cukup letakkan data baru tersebut, sehingga menjadi 3-node).
4. Sedangkan, jika leaf yang dituju sudah 3-node. Maka simulasikan dengan memasukkan data baru diantara data A dan B (A dan B adalah dua data yang terdapat di 3-node tersebut). nilai data yang berada di tengah-tengah antara nilai A, B, dan data baru akan naik ke parent dan membagi 2 sisanya menjadi 2-node. secara rekursif memperbaiki pada parent-nya.

Contoh Insertion pada 2-3 Tree :

ketika insert(45) dilakukan. leaf yang dituju adalah 2-node. sehingga, letakkan saja nilai 45 tersebut.

contoh lainnya yaitu memasukkan di 3-node leaf.

ketika kita insert(75), maka kita akan membandingkan nilai 75-80-90. Nilai yang berada di tengah antara ketiga nilai tersebut akan didorong naik menuju parentnya. seperti gambar di bawah ini

 sehingga akan menjadi seperti gambar tree di bawah ini

 2-3 Tree setelah memasukkan nilai 75.

Insert(24)

nilai tengah (24) akan didorong ke parent diatasnya.

ternyata parent juga 3-node. dorong nilai tengah diantara 3 nilai tersebut menuju parent di atasnya lagi.

sehigga 2-3 Tree setelah di insert(24), maka akan tampak seperti gambar di atas.

saya sertakan video tutorial cara memasukkan angka / insertion pada 2-3 Tree. berikut cuplikannya :

Deletion pada 2-3 Tree.

beberapa tahapan deletion pada 2-3 Tree :

1. Kita masukkan kunci untuk mencari data yang kita ingin hapus dari 2-3 Tree.
2. Seperti di Binary Search Tree (BST), pertama-tama kita harus mencari leaf yang terdapat data yang kita cari.
3. Jika leaf-nya sudah 3-node, maka kita tinggal menghapus saja data tersebut dan menjadikannya 2-node.
4. Jika leaf-nya adalah 2-node :

• Jika parent-nya 3-node, maka ambil 1 nilai dari 3-node tersebut. Jika Sibling/Saudaranya adalah 3-node, maka push nilai tersebut dari sibling ke parent untuk membuat parent menjadi 3-node lagi. Jika sibling adalah 2-node, buat parent menjadi 2-node dan gabungkan node dengan sibling-nya.
• Jika parent-nya 2-node, Jika sibling-nya adalah 3-node, maka ambil satu nilai dari parent dan push satu nilai dari sibling ke parent-nya sendiri. Hal lainnya yaitu mengabunggkan parent dengan sibling.

Contoh Deletion pada 2-3 Tree :

Delete(23), angka 23 terdapat pada leaf, dan leaf tersebut adalah 3-node. Jadi, kita tinggal menghapus saja angka 23.

Contoh Deletion lainnya :

 ketika delete(50), maka ambil nilai 40 pada leaf paling bawah , dan gantikan dengan 50 pada parent atas, lalu delete/hapus nilai 40 pada leaf paling bawah. sehingga seperti gambar di bawah ini.

parent-nya adalah 3-node, sedangkan sibling-nya merupakan 2-node. Jadi, gabungkan (25) dan (30). Sehingga 2-3 Tree nya adalah pada gambar di bawah ini.

2-3 Tree setelah delete(50).
________________________________________________________________

Nama : Alexander

NIM : 1401111806

Kelas  : 02PGT

________________________________________________________________

sumber : bina nusantara, en.wikipedia.org/wiki/2-3_tree, youtube