Red Black Tree

Red-Balck Tree (RBT) adalah sebuah BST (binary search tree) dimana tiap simpul memiliki atribut warna yang bernilai merah atau hitam.

            RBT juga berguna dalam pemrograman fungsional karena RBT merupakan salah satu struktur data yang paling “persistent”, digunakan untuk membuat associative array dan himpunan yang bhisa mengambil kembali versi sebelumnya setelah perubahan. Versi “persistent” dari RBT memerlukan tambahan ruang O(log n) untuk setiap insersi atau delesi, selain waktu.

RBT isometri dari pohon 2-3-4. Artinya, untuk setiap 2-3-4 pohon, terdapat paling sedikit satu satu RBT dengan elemen data yang berurutan sama. Operasi insersi dan delesi pada pohon 2-3-4 equivalen dengan color-flipping (pertukaran warna) dan rotasi pada RBT. Ini membuat pohon 2-3-4 alat yang penting untuk memahami logika dibalik RBT, hal ini pula yang membuat berbagai text algoritma memperkenalkan pohon 2-3-4 sebelum RBT walaupun pohon 2-3-4 lebih jarang digunakan.

Red Black Tree adalah suatu BST( Binary Search Tree) dimana node-node dan edge-edge memiliki warna merah atau hitam. Warna dari root selalu hitam. 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

validitas RBT :

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.

Aturan Insert pada Red Black Tree :

1.      Setiap node baru yang disisipkan  kedalam tree akan diberi warna merah.

2.      Jika kita memberi warna hitam  pada node baru yang  masuk, maka jumlah node dari root akan berbeda.

3.      Jika kita memasukkan node baru yang berwarna merah kedalam parent yang berwarna hitam tidak akan menjadi masalah, yang menjadi masalah adalah jika kita menyisipkan node baru ke dalam parent yang berwarna merah

4.      Jika parent berwarna merah kita akan membuat dua node merah yang berurutan, jadi kita harus melakukan rotasi atau pewarnaan ulang.

5.      Hal penting yang harus diingat adalah node yang tidak mempunyai daun harus berwarna hitam.

Delete

Setelah belajar cara untuk push, maka kita akan belajar cara untuk menghapus nya, cara nya hampir mirip dengan di BST.

Misal nya seperti ini :

1. Misalkan node yang mau di hapus adalah M lalu anak nya adalah C.

2. Kalau M adalah merah, lalu maka tinggal mengganti M dengan C yang berarti warna C seharus nya adalah hitam.

3. Kalau M adalah hitam dan C adalah merah, ganti M dengan C dan ubah warna C menjadi hitam.

Lalu bagaimana kalau M dan C adalah hitam ?

Maka, langkah yang akan kita lakukan adalah :

1. Ganti M dengan C, lalu kita ganti nama C menjadi N (ini disebut double black), dan parent nya menjadi P, sibling nya menjadi S, lalu SL adalah anak kiri dan SR adalah anak kanan.

2. Kalau S berwarna merah tukar warna N dan P, lalu putar di P

3. Kalau S, SL dan SR berwarna hitam maka ganti warna S ke merah

4. Kalau S adalah hitam dan SL atau SR adalah merah, maka lakukan single atau double rotat

Berikut adalah kasus - kasus dalam delete RBT :

1. 

Dalam kasus ini dapat kita lihat bahwa a adalah double black node, sibling nya berwarna merah jadi kita putar di X dan ganti warna X dan Y.

2.

Dalam kasus ini a adalah double black node, sibling nya adalah black dan anak dari sibling tersebut adalah node berwarna hitam, jadi ganti warna sibling menjadi merah.

3.

Dalam kasus ini a adalah double black node, sibling nya berwarna hitam dan anak dari sibling tersebut berwarna merah, jadi lakukan single atau double rotation.

Nama: Ardi Yuriansyah

Nim: 1701290816

www.binus.ac.id