Red Black Tree (RBT)

RBT adalah sebuah binary search tree yang dimana setiap node nya memiliki warna merah atau hitam. Warna dari root selalu hitam dan warna dari edge yang menghubungkan ayah dengan anaknya selalu berwarna sama dengan warna node anak tersebut. Selain atribut yang dimiliki oleh BST, kita memerlukan persyaratan berikut untuk memnentukan.

Aturan pada Red Black Tree 

1. Setiap simpul/node adalah berwarna merah atau hitam

2. Akar selalu berwarna hitam

3. Nilai sebuah node adalah lebih besar anak kirinya dan lebih kecil dari anak kanannya.

4. Jika node berwarna merah, anaknya harus berwarna hitam

5. Node berwarna merah secara berturut-turut tidak diperkenankan.

6. Setiap path dari node yang menuju ke nil harus mengandung nilai yang sama dengan node yang berwarna hitam.

7. Tree dikatakan setimbang jika selisih level dari anak kiri dan anak kanan maksimal dua.

8. Node dibawah root yang berada pada level yang sama disebut sibling.


Insertion

Penyisipan dimulai dengan menambahkan node seperti penyisipan pohon pencarian biner dilakukan dan dengan mewarnai merah. Sedangkan dalam pohon pencarian biner, kita selalu menambahkan daun, merah-hitam daun pohon tidak mengandung informasi, jadi kita tambahkan node interior merah, dengan dua daun hitam, di tempat yang ada daun hitam.

Apa yang terjadi berikutnya tergantung pada warna terdekat lain node. Paman (saudara parent) dalam istilah node akan digunakan untuk merujuk pada saudara kandung dari node orangtua, seperti dalam pohon keluarga manusia.
catatan :

Baik anak-anak dari setiap node merah hitam terancam hanya dengan menambahkan simpul merah, mengecat node hitam merah, atau rotasi.

Semua path dari setiap node ke node daun berisi jumlah yang sama node hitam terancam hanya dengan menambahkan node hitam, mengecat simpul merah hitam, atau rotasi.


Delete

Menghapus sebuah node di RBT, hamper sama dengan menghapus node di BST ( Binary Search Tree) , jika sebuah node yang dihapus memiliki 2 anak, maka node yang dari anak kiri terbesar, atau anak kanan terkecil yang akan menggantikan si parent tersebut. Jika si parent berwarna merah dan anaknya merah, langsung digantikan dan tidak masalah, jika parent hitam dan anaknya merah, gantikan si parent dengan anaknya, lalu diwarna menjadi hitam, bagaimana jika kedua-duanya hitam? Jika keduanya hitam, gantikan si parent dengan anaknya, lalu rotasikan dan sesuaikan dengan treenya, sehingga tidak merusak aturan dalam RBT

Nama : Setiawan Faisal.K

NIM  :1701307501

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