2-3 Tree

2-3 Tree adalah sebuah struktur data dimana setiap internal nodenya (non leaf) adalah 2-node atau 3-node dan semua leafnya berada pada level yang sama.

• 2-node adalah suatu node yang memiliki 1 data dan 2 anak
• 3-node adalah suatu node yang memiliki 2 data dan 3 anak

Data-data yang disimpan setiap node pada 2-3 tree harus sudah berurutan

Insertion
Anggap node yang di insert adalah key. Key akan ditempatkan pada leaf.
a) Jika leaf adalah 2-node, maka key dimasukan kedalam leaf sehingga leaf tersebut menjadi 3-node.
b) Jika leaf adalah 3-node, maka ambil nilai tengah dari A, B, dan key, kemudian push nilai tengah tersebut pada parentnya

Jika pada saat aturan kedua parentnya bukanlah 2-node, melainkan 3-node, tentukan kembali nilai tengah lalu push kembali ke parentnya
Jika pada saat aturan ke 2 dan 3 tidak bisa dilakukan karena parent sampai ke rootnya adalah 3-node, maka tentukan kembali nilai tengah, kemudian nilai tengah tersebut akan dibuat root baru.


Deletion
Misal node yang dihapus adalah key,maka key tersebut digantikan oleh leafnya
Jika leaf 3-node, maka ambil salah satu data untuk menggantikan key, seperti BST, terbesar dari subtree kiri atau terkecil dari subtree kanan
Jika leaf 2-node, maka :

Jika parent dari leaf adalah 3-node, maka ambil satu data dari parent. kemudian kita perhatikan kembali siblingnya.
a) Jika sibling 3-node, maka ambil satu data kemudian push pada parent, agar parent kembali menjadi 3-node,
b) Jika sibling 2-node, maka biarkan parent menjadi 2-node, dan satukan node tersebut dengan siblingnya

Jika parent dari leaf adalah 2-node, kita perhatikan siblingnya.
a) Jika sibling 3-node, ambil satu data dari parent dan push satu nilai dari sibling ke parent.
b) Jika sibling 2-node, maka satukan sibling dengan parent.