Review 2-3 Tree

Review 2-3 Tree , 2-3 Tree mempunyai 2-node atau 3-node

Rule :

2-node : mempunyai 1 data dan memiliki 2 anak ( kiri dan tengah )
3-node : mempunyai 2 data dan memiliki 3 anak ( kiri , tengah dan kanan )
semua data harus di sortir , jika A adalah parent maka anak kiri harus lebih kecil dari A , anak tengah harus lebih besar dari A
jika A dan B parent , maka anak kiri harus lebih kecil dari A anak tengah harus lebih besar dari A dan lebih kecil dari B, anak kanan harus lebih besar dari B

Insertion :

Sebelum insert kita harus mencari di mana node akan di input dalam 2-3 tree menggunakan search algorithm, akan menjadi leaf
Jika leaf adalah 2-node , input node jadi ( 3-node )
if leaf sudah 3-node push middle data , contoh A,B,C , B ke atas dan A dengan C di split menjadi 2-node (recrusive ke parent) #case1

contoh :

terjadi #case1 jadi kita harus push 80 ke atas , dan split 75 dengan 90

70|80

60| – 75| – 90| –

Deletion :

Jika leaf adalah 3-node , delete sehingga menjadi 2-node

Jika left adalah 2-node :

jika parent adalah 3 node, ambil 1 value , jika sibling adalah 3-node maka push 1 value ke parent agar menjadi 3-node lagi , jika sibling adalah 2-node dan parent 2-node maka merge current node ke sibling
jika parent 2=node dan jika sibling 3-node dapatkan 1 value dari parent dan push 1 value dari sibling ke parent , atau merge parent with sibling

Contoh :

delete(23)

karena node(23) adalah leaf , tinggal delete

delete(50) , ganti 50 dengan 40 dan hapus node(40)

karena sibling nya 2-node jadi merge parent ke sibling

Abdillah Muhamad