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 :
- 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.
- 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.
Insertion pada 2-3 Tree
ketika kita ingin memasukkan data baru ke 2-3 Tree, maka kita harus melakukan beberapa tahapan :
- Misalkan kita memasukkan data baru.
- 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.
- Jika leaf yang dituju adalah 2-node, maka kita cukup letakkan data baru tersebut, sehingga menjadi 3-node).
- 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.
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
Insert(24)
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 :
- Kita masukkan kunci untuk mencari data yang kita ingin hapus dari 2-3 Tree.
- Seperti di Binary Search Tree (BST), pertama-tama kita harus mencari leaf yang terdapat data yang kita cari.
- Jika leaf-nya sudah 3-node, maka kita tinggal menghapus saja data tersebut dan menjadikannya 2-node.
- 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.
Delete(23), angka 23 terdapat pada leaf, dan leaf tersebut adalah 3-node. Jadi, kita tinggal menghapus saja angka 23.
Contoh Deletion lainnya :
________________________________________________________________
Nama : Alexander
NIM : 1401111806
Kelas : 02PGT
________________________________________________________________
sumber : bina nusantara, en.wikipedia.org/wiki/2-3_tree, youtube
