Red Black Tree (RBT)

Suatu tree dikatakan RBT apabila :
- setiap node memiliki warna (hitam atau merah)
- root berwarna hitam
- eksternal node berwarna hitam
- node merah tidak memiliki anak merah
- setiap subtree memiliki jumlah node hitam yang sama dengan subtree lainnya

Insertion
Aturan  insertion :
- node baru berwarna merah
- node merah tidak boleh memiliki anak merah

Apa yang dilakukan jika node merah memiliki node child merah?
Cek paman dari node child merah
Jika pamannya berwarna merah, maka ubah warna orangtuanya dan pamannya menjadi hitam, dan kakekny menjadi merah.
Jika pamannya berwarna hitam, lakukan rotasi single/double, kemudian setelah rotasi, orangtuanya berwarna hitam, anak berwarna merah
Jika tidak memiliki paman, sama artinya dengan pamannya berwarna hitam(eksternal node)

Deletion
Deletion RBT sama seperti deletion pada AVL
Aturannya :
anggap O =  node yang di delete dan N = node yang menggantikan

jika O merah, diganti dengan N yang berwarna hitam
jika O hitam dan N merah, maka O diganti N dan N berubah warna menjadi hitam
jika O hitam dan N hitam, kita lakukan pemisalan kembali :

 
  P = parent N,
  S = sibling N,
  Sl = anak kiri S,
  Sr = anak kanan S
 Kita perhatikan siblingnya :
  a.  jika S merah, ubah warna N dan P (tukar warna), kemudian rotate di P
  b.  jika S hitam dan Sl, Sr hitam, maka ubah S menjadi merah
  c.  jika S hitam dan Sl atau Sr ada yang merah maka lakukan rotasi single/double