Red Black Tree

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.

 

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. Perhatikan bahwa:

Properti 3 (Semua daun yang hitam) selalu berlaku.

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

Properti 5 (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.

Catatan: Label N akan digunakan untuk menunjukkan simpul sedang dimasukkan (berwarna merah); P akan menunjukkan N 's simpul ayah, G akan menyatakan N' s kakek-nenek, dan U akan menunjukkan N 's paman. Perhatikan bahwa di antara beberapa kasus, peran dan label simpul komunikasi, tetapi dalam setiap kasus, setiap label terus untuk mewakili simpul yang sama ini diwakili pada awal kasus. Setiap warna ditampilkan dalam diagram diasumsikan baik dalam kasus maupun tersirat oleh asumsi-asumsi ini.

Deleting (Penghapusan)

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 dari, yang pasti kurang dari dua non-daun anak-anak. Karena hanya menyalin nilai tidak melanggar sifat merah-hitam, ini untuk mengurangi masalah menghapus sebuah node dengan paling banyak satu anak non-daun. Tidak peduli apakah simpul ini adalah simpul kami awalnya ingin menghapus atau simpul kita menyalin nilai dari.

Untuk masalah ini kita dapat mengasumsikan kita menghapus sebuah node dengan paling banyak satu daun non-anak, yang akan kita sebut dengan anak (jika ia hanya mempunyai anak-anak daun, membiarkan salah satu dari mereka menjadi para anak). Jika kita menghapus simpul merah, kita dapat dengan mudah menggantinya dengan anak, yang harus hitam. Semua jalan melalui node dihapus hanya akan melewati kurang satu simpul merah, dan kedua dihapus node orangtua dan anak harus hitam, jadi sifat 3 (Semua daun, termasuk null s, yang hitam) dan 4 (Kedua anak-anak dari setiap node merah hitam) masih terus. Lain kasus sederhana adalah ketika dihapus node anak hitam dan merah. Cukup menghapus simpul hitam bisa memecahkan Properti 4 (Baik anak-anak dari setiap node merah hitam) dan 5 (Semua path dari setiap node ke node daun berisi jumlah yang sama node hitam), tetapi jika kita mengecat kembali dengan anak hitam, baik properti ini dipertahankan.

Kasus yang rumit adalah ketika kedua simpul untuk dihapus dan anak yang hitam. Kita mulai dengan mengganti node untuk dihapus dengan anak. Kami akan panggilan (atau label) anak ini (dalam posisi baru) N, dan saudara (orangtua baru anak lain) S. Dalam diagram di bawah ini, kita juga akan menggunakan P untuk N 's orangtua baru, S L untuk S' s anak kiri, dan S R untuk S 's anak kanan (dapat ditunjukkan bahwa S tidak bisa menjadi daun).

Catatan: Di antara beberapa kasus, saling bertukar peran dan label dari node, tapi dalam setiap kasus, setiap label terus untuk mewakili simpul yang sama ini diwakili pada awal kasus. Setiap warna ditampilkan dalam diagram diasumsikan baik dalam kasus maupun tersirat oleh asumsi-asumsi ini. Putih merupakan warna yang tidak diketahui (baik merah atau hitam).