HELLO

Red Black Tree 

Tree yang proses insertnya masih sama dengan binary tree

Binary tree yang nodenya memiliki warna,merah dan hitam

Memiliki root yang selalu berwatna hitam

Setiap node yang baru dimasukkan memiliki warna merah

Node externalnya berwarna hitam

Node berwarna merah tidak boleh memiliki child berwarna merah

External node merupakan leaf nodes yang secara fisik sebenarnya external nodes tidak ada.

External node ada untuk membantu mempermudah algoritma RBT.

Warna default external node adalah hitam.

Insertion

Bila node yang dimasukkan ternyata memiliki parent berwarna hitam, maka tidak terjadi violation

Bila node yang dimasukkan memiliki parent berwarna merah, lihatlah uncle dari node tersebut. Apabila unclenya juga berwarna merah maka lakukan

Bila node yang dimasukkan memiliki parent berwarna merah, lihatlah uncle dari node tersebut. Apabila unclenya berwarna hitam maka lakukan

single rotation bila

double rotation bila

Deletion

Cara penghapusannya memiliki step yang sama dengan BST namun terdapat beberapa ketentuan tambahan yaitu

Bila a adalah double black node dan memiliki saudara yang berwarna merah maka

Bila a adalah double black node dan memiliki saudara berwarna hitam, maka lihatlah terlebih dahulu anak dari saudara tersebut. Bila berwarna hitam maka

Bila a adalah double black node dan memiliki saudara berwarna hitam, maka lihatlah terlebih dahulu anak daru saudara tersebut. Bila berwarna merah maka

2-3 tree

2-3 tree bukanlah binary tree

ketentuan dalam 2-3 tree:

1. Bila node non-leaf memiliki 2 data maka node tersebut harus mamiliki 3 child

2. Bila node non-leaf memiliki 1 data maka node tersebut harus mamiliki 2 child

Insertion

bila node yang dimasukkan lebih kecil daripada parentnya maka node tersebut harus menjadi left child

bila node yang dimasukkan lebih besar daripada parentnya maka node tersebut harus menjadi right child

bila node yang dimasukkan berada di antara kedua node yang menjadi parentnya maka node tersebut harus menjadi middle child

apabila node telah terisi penut oleh 2 data dan harus dimasuki lagi oleh 1 data yang baru, seperti contou memasukkan angka 75

maka karena angka 80 berada di antara 75 dan 90, sehingga angka 80 harus dinaikkan ke atas, masuk ke dalam node yang telah berisi data 70

Sedangkan 75 dan 90 masing2 membentuk node baru yang berisikan oleh 1 data

(setiap ada 3 data memenuhi 1 node, 1 data yang bread di tengah dinaikkan ke atas, sedangkan 2 data lainnya masing2 membentuk node baru)

Deletion

Untuk deletion di dalam 2-3 tree boleh menggunakan cara apa saja asalkan masih tetap memenuhi persyaratan persaratan 2-3 tree seperti yang tertera di atas

Contoh delete 50 pada

Dapat dilakukan dengan mengganti angka 50 dengan menggunakan anak kiri yang memiliki angka paling besar (40) ataupun anak kanan yang memiliki angka paling kecil (60)

Setelah itu node yang berisikan data 20 dan 30 hanya memiliki 2 child, agar memenuhi start 2-3 tree yang berlaku maka salah satu dari mereka harus turun menjadi child (b0leh 20 maupun 30).

Bila yang diturunkan ialah 20 maka 20 harus berada di camping kanan angla 15 agar memenuhi persyaratan yang berlaku.