Deletion 2-3 Tree

2-3 TREE DELETION :

1. Tentukan di node mana data yang ingin dihapus

2. Jika berada dalam 3-node, langsung hapus saja datanya.

3. Jika berada dalam 2-node :

a.   Jika parent adalah 3-node : ambil satu data dari parent. 
Jika sibling adalah 3-node, ambil salah satu data nya untuk 
dijadikan data pada parent (agar parent menjadi 3-node lagi). 
Jika sibling adalah 2-node, buat parent menjadi 2-node 
dengan menggabungkan (merge) sibling dengan node tempat data didelete.

b.   Jika parent adalah 2-node : Jika sibling adalah 3-node, turunkan 
data parent ke node dan ambil satu data dari sibling untuk 
menggantikan parent. Jika sibling 2-node, gabungkan sibling 
dengan node yang dihapus datanya.

Contoh Deletion :

Disediakan tree berikut ini :

Delete 15 dan 35 !

1. Delete 15, karena 3-node maka langsung hapus saja 15.

2. Delete 35.

      Seperti BST, kita pilih data terbesar dari subtree kiri atau data 
      terkecil subtree kanan untuk menggantikan 35. Dalam contoh ini 
      saya menggunakan data terbesar subtree kanan (30).

Karena parent dari node 30 sebelumnya adalah 3-node, maka anaknya harus 3 buah. Karena tidak ada sibling yang 3-node maka kita jadikan parent menjadi 2-node dengan menurunkan salah satu datanya (25) menjadi child bergabung dengan data sebelumnya.

Contoh soal :

Insert data 10, 40, 70, 60, 80, 20, 50, 30, 55, 90 ke dalam 2-3 tree kemudian lakukan delete 50 80 70 !

1. Insert (10), Langsung masukkan 10 ke dalam node baru (2-node).

2. Insert (40), Letakkan 40 di node yang sama tetapi berada di sebelah 
   kanan 10, karena data harus berurut (secara ascending).

3. Insert (70), Karena node merupakan 3-node maka kita jadikan 40 atau 
   data tengah dari 10, 40, 70, menjari parent. Split 10 dan 70 masing-
   masing menjadi 2-node.

4. Insert (60), langsung saja letakkan di sebelah 70.

5. Insert (80), Bandingkan 60, 70, dan 80, kemudian jadikan data tengah

   menjadi parent.

6. Insert (20), Langsung saja diletakkan di kanan 10.

7. Insert (50), Langsung saja diletakkan di kiri 60.

8. Insert (30), Bandingkan 10, 20, dan 30. Jadikan data tengah menjadi 
   parent kemudian split 10 dan 30. Setelah kita naikkan 20 menjadi 
   parent, ternyata parent merupakan 3-node, sehingga kita bandingkan 
   lagi 20, 40, dan 70. 40 naik menjadi parent kemudian split 20 dan 70.

9. Insert (55), Bandingkan 50, 55, dan 60. Data 55 naik menjadi parent 

   kemudian split 50 dan 60.

10. Insert (90), Langsung letakkan di kanan 80.

11. Delete (50), Delete 50 lalu turunkan 55 menjadi child dan merge 
    dengan 60 menjadi sebuah 3-node.

12. Delete (80), Langsung saja delete 80 karena merupakan 3-node dan
    posisinya berada di child.

13. Delete (70), Delete 70 dan gantikan dengan data terbesar dari 
    subtree kiri atau data terkecil subtree kanan. Dalam kasus ini 60 
    lebih tepat untuk menggantikan 70 karena tidak perlu merubah 
    bentuk tree.

Untuk lebih jelasnya anda bisa mencoba applet 2-3 tree disini: 

http://slady.net/java/bt/view.php

® Believe n Never Give Up ®