(RBT) Red Black Tree

Red Black Tree merupakan Binary Search Tree yang terdiri dari 2 warna. Sebuah BST dikatakan RBT apabila memenuhi kondisi berikut :

1. setiap node memiliki warna, baik merah atau hitam
2. root adalah hitam secara default / otomatis
3. semua external node adalah hitam
4. jika sebuah node berwarna merah, maka kedua anaknya berwarna hitam. itu berarti tidak ada child merah yang memiliki parent merah
5. setiap node ke external node keturunan memiliki jumlah node hitam yang sama

Terdapat 2 operasi pada RBT yaitu Insert dan Delete

- Insert
insert pada RBT sama seperti pada konsep BST dan setiap node baru berwarna merah. jika parent berwarna hitam maka tidak ada violation dan tinggal insert saja node tersebut, tetapi jika parent berwarna merah maka violation terjadi (sesuai aturan nomor 4).
untuk memperbaiki violation tersebut maka:
  - misalkan:
Q = node baru
P = parentnya
S = sibling P (parent Q)
jika parent tidak memiliki sibling, S  = hitam (external node)
jika S = merah, ganti P dan S menjadi hitam dan parent P menjadi merah
jika S hitam maka lakukan rotasi seperti rotasi pada AVL, lalu ubah pivot rotasi terakhir menjadi hitam dan anaknya menjadi merah.

contoh 1 (node baru X): recolor

 contoh 2 (node baru X): single rotate

 contoh 3 (node baru Y): double rotate

- Delete

delete pada RBT juga sama seperti BST, hanya pada RBT ada beberapa kondisi mengenai warna, yaitu:

   - misalkan:

M = target delete

C = pengganti

jika M = merah, C = merah langsung ganti

jika M = merah, C = hitam langsung ganti

jika M = hitam, C = merah langsung ganti dan recolor C = hitam

jika M = hitam, C = hitam akan menciptakan token double black di posisi C

C = N

S = sibling

Sl = sibling left

Sr = sibling right

P = parent

kondisi jika ada token double black:

- kondisi 1 jika S = merah, SL & SR = hitam

maka reverse color P dan S dan rotate di P , token black tetap ada di N. cek kondisi lagi

- kondisi 2 jika s = hitam, SL & SR = hitam

maka recolor S = red , token black pindah ke P

jika warna P = merah recolor jadi hitam, jika P = hitam maka terjadi double black lagi

- kondisi 3 jika S = hitam , SL / SR = merah

maka rotate di parent (single/double), parent baru mengikuti warna parent lama dan kedua anaknya jadi hitam , lalu token black hilang

nb : jika token double black berada pada node merah, maka node tsb menjadi hitam dan

token double black hilang.

contoh delete:

www.binus.ac.id

www.skyconnectiva.com