Red Black Tree

Red Black Tree

Red Black Tree adalah pohon pencarian biner seimbang yang ditemukan pada tahun 1972 oleh Rudolf Bayer yang menyebutnya "pohon-biner simetris B-tree". Running time untuk operasinya  untuk digunakan sebagai pencarian, penyisipan, dan penghapusan semua dapat dilakukan dalam waktu O (log n), di mana n adalah jumlah node di pohon.

RBT Properties:
1. Setiap node berwarna hitam atau merah.
2. Warna root adalah hitam.
3. Semua node eksternal berwarna hitam.

4. Jika simpul berwarna merah, maka kedua anaknya berwarna hitam.
5. Setiap jalur dari leaf ke root memiliki jumlah node hitam yang sama.

RBT Operations: Insertion
Node yang baru diinsert bewarna merah. Namun, perlu diperhatikan:
-Jika induknya berwarna hitam, maka tidak ada pelanggaran yang terjadi.
-Jika induknya merah, maka pelanggaran terjadi.

Fixing the violation
-Misalkan simpul baru adalah q, induknya adalah p, dan siblingnya adalah s (uncle dari q). Jika -parent tidak memiliki sibling, maka s berwarna hitam (simpul eksternal berwarna hitam).
-Jika s berwarna merah, maka ubah p dan s menjadi hitam dan parent dari p menjadi merah.

-Jika s berwarna hitam, lakukan rotasi (tunggal atau ganda), ubah pivot rotasi terakhir menjadi hitam dan childnya menjadi merah.

RBT Operations: Deletion
Misalkan simpul yang akan dihapus adalah M, dan childnya adalah C.
-Jika M berwarna merah, maka cukup ganti dengan C

-Jika M berwarna hitam dan C berwarna merah, gantilah dengan C dan warnai kembali C dengan hitam.

Jika M dan C bewarna Hitam;
-Jika M dan C berwarna hitam, ganti M dengan C.
-Nyatakan C dalam posisi barunya menjadi N (dapat disebut double black), parentya menjadi P, siblingnya adalah S, SL menjadi left child S dan SR menjadi right child S.
-Jika S berwarna merah, balikkan warna N dan P, dan putar pada P.
-Jika S, SL dan SR berwarna hitam, maka warnai ulang S sebagai merah.

-Jika S berwarna hitam dan SL atau SR berwarna merah, maka rotate tunggal atau rotate ganda.