RBT(Red Black Tree)

RBT(Red Black Tree)

RBT merupakan salah satu balanced binary tree yang digunakan untuk membuat tree seimbang.
Akan tetapi, RBT merupakan tree yang memberikan kita worst time guarantee(waktu terburuk) untuk melakukan operasi-operasi nya yaitu insert, delete maupun searching, sehingga RBT cocok digunakan untuk mencari tau waktu terburuk dari suatu aplikasi.

Contoh RBT:

Ketentuan dasar RBT yaitu sebagai berikut :

1.       Setiap node memiliki warna baik hitam maupun merah.

2.       Root warnanya selalu hitam.

3.       Dibawah leaf ada external node yang berwarna hitam.

4.       Node merah tidak bisa punya anak node merah, tetapi node hitam bisa punya anak node itam dan node merah.

5.       Jumlah node berwarna hitam dari root ke external node melewati tiap cabang nya  jumlah nya harus sama.

Double black merupakan suatu kondisi dimana node hitam digantikan oleh node hitam.

Operasi pada RBT :

1.       Insert:

a.       Cara insert sama seperti pada BST dan AVL

b.      Node yang baru diinsert selalu berwarna merah.

c.       Jika node yang baru diinsert parentnya hitam maka, tidak apa-apa

d.      Jika node yang baru diinsert parentnya merah maka,terjadi violation:

                                                               i.      Jika uncle dari node baru berwarna hitam maka lakukan rotasi(single/double) ke arah uncle berwarna hitam tersebut dan lalu lakukan recolor menjadi parent dari hasi rotation tadi menjadi hitam dan kedua anaknya menjadi merah.
                                  
                                    dimana pada contoh dimasukkan angka 5, yang menyebabkan terjadi violation.

                                                             ii.      Jika uncle dari node baru berwarna merah, maka lakukan recolor, dimana parent dan uncle dari node baru tersebut ubah warnanya menjadi warna hitam dan grandparent dari node baru tersebut menjadi warna merah.

a

b

Seperti pada contoh dimasukkan angka 4, terjadi violation seperti pada pint 2 insert, dimana seharusnya angka 6 juga menjadi merah akan tetapi dikarenakan angka 6 merupakan root(lihat ketentuan RBT) sehingga root selalu hitam.

2.       Delete:

a.       Cara delete sama seperti pada BST.

b.      Jika sebuah node warna merah dihapus dan anaknya warna hitam, maka ganttin saja node yang dihapus tersebut dengan node hitam tersebut.

c.       Jika sebuah node warna hitam dihapus dan digantikan oleh node warna merah maka, gantiin node yang dihapus dengan node merah tersebut dan ubah warna nya jadi hitam

d.      Jika node hitam dihapus dan diganttin sama node hitam maka masuk kondisi double black.

                                                               i.      Jika sibling db nya warna hitam dan kedua anaknya hitam maka, ubah sibling jadi warna merah dan parentnya jadi warna hitam, klo sebelumnya parentnya warna hitam, maka parentnya masuk ke kondisi db.

                                       Jika x merupakan node merah, maka proses insertion selesai. Akan tetapi jika x merupakan nofe hitam, maka x akan menjadi double black.

                                                             ii.      Jika sibling db warna nya hitam dan anaknya ada yang berwarna merah, maka lihat parentnya:

1.       Jika parentnya warna merah maka lakukan rotasi(single/double) dan nanti ubah warna parent yang setelah di rotasi jadi merah dan kedua anak nya jadi hitam

2.       Jika parentnya warna hitam maka lakukan rotasi kemudian parent dan juga kedua anaknya menjadi warna hitam semuanya.

Jika x merupakan node merah maka setelah dirotasi node y akan menjadi merah 

tetapi jika x merupakan node hitam maka setelah dirotasi node y menjadi warna hitam.

                                                            iii.      Jika sibling db warna merah, maka lakukan rotasi ke arah db nya, lalu parentnya jadi warna hitam dan anak kanannya(yang sebelumnya jadi parent) jadi warna merah, tapi db nya belum hilang sehingga masih harus diselesaikan.

Gambar yang node nya ada kotak nya menandakan double black(db).