Red Black Tree

==============================================================

Red Black Tree (RBT)

• RBT adalah tree yang mempunyai sifat yang sama seperti Binary search tree namun memiliki sifat - sifat khusus seperti berikut : 

1. Semua node berwana merah atau hitam.
2. Root selalu berwarna hitam.
3. Semua node eksternal berwarna hitam.
4. Apabila node berwarna merah , maka kedua anaknya berwarna hitam.

Operasi Insertion pada RBT

• Pada RBT setiap anak baru node selalu berwarna merah

• Jika root berwarna hitam dan sesuai dengan syarat, maka tree tidak perlu diubah

• Saat nodes merah mempunyai anak merah, maka nodes di rotate menjadi seperti gambar di tengah. Apabila lebih banyak di kanan maka akan diputar ke kiri namun sebaliknya apabila lebih banyak di kiri akan diputar ke kanan.

• Akan dilakukan double rotate apabila kondisi seperti di gambar berikut

• Apabila sibling berwarna merah maka akan diubah warnanya menjadi hitam dan root diubah menjadi warna merah, seperti gambar berikut :

Operasi Deletion pada RBT

==============================================================

Nama : Johanes Arnold
NIM   : 1701302242

www.binus.ac.id | www.skyconnectiva.com