RED BLACK TREE

Red Black 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 bisa mengambil kembali versi sebelumnya setelah perubahan.

Red Black Tree adalah suatu BST (Binary Search Tree) dimana node-node dan edge-edge memiliiki 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.

• Aturan pada RBT

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 annak kanan maksimal dua
8. Node dibawah root yang berada pada level yang sama disebut sibling.

• Aturan Insert pada RBT

1. Setiap node baru yang disiapkan 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 berwarnna 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.

• 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 innformasi, jadi kita tambahkan node interior merah, dengan dua daun hitam, ditempat yang ada daun hitam.

• Deleting

Dalam sebuah pohon pencarian biner yang normal, saat menghapus sebuah node dengan dua anak-anak non-daun, kita menemukan salah satu elemen maksimum dalam subtree kiri atau elemen minimum dalam subtree kanan, dan memindahkan nilainya ke dalam node yang dihapus. Kami kemudian menghapus simpul kita menyalin nilai tidak melanggar sifat merah-hitam, ini untuk mengurangi masalah menghapus sebuah node dengan paling banyak satu anak non-daun. Tidak peduli apkah simpul ini adalah simpul kami awalnya ingin mengapus atau simpul kita menyalin nilai dari.

• Contoh Red Black Tree