Red Black Tree

Nama  : Mochamad Rizki
NIM   : 1401081034
Kelas  : 02PVT


Karakterisitik Red Black Tree :

External node boleh tidak ditulis

1. Memiliki karakteristik BST.
2. Node memiliki warna Red atau Black.
- Root selalu Black
- Node external selalu Black
3. Anak dari node Red harus Black (tidak ada 2 node red yang berurutan)
4. Black-height yang sama pada kedua simple path dari suatu node ke leaf
- black-height (bh) : Jumlah node black pada suatu simple path
bh(node 2) = 1
bh(node 11) = 2


Operasi pada Red Black Tree :
a. Insert
• Node baru diberi warna Red
• Hasil insert harus tetap memenuhi karakteristik Red Black tree
• Pemeriksaan node setelah insert dilakukan secara berurutan dari node baru ke node-node yang lain (ancestor) ke arah root
Contoh :
1.

Jika parent node baru BLACK, tree masih memenuhi persyaratan tree R-B


2.

• Node baru (X atau Z) dan parent berurutan berwarna RED
• Supaya memenuhi persayaratan tree R-B, dilakukan rotasi tunggal dan pergantian warna


3.

• Node baru (Y) dan parent berurutan berwarna RED
• Supaya memenuhi persayaratan tree R-B, dilakukan rotasi ganda dan pergantian warna


4.

• Node baru dan parent, berurutan RED
• Perubahan RED-BLACK pada parent dan uncle
• Perubahan BLACK-RED pada grandparent


b. Delete
• Delete pada tree R-B menyerupai BST
• Pada BST :
Jika node 56 dihapus, isi child 3 di copy ke posisi 56 yang di hapus dan node child dihapus.
• Pada tree R-B :
     o Hapus node black akan menyebabkan keseimbangan black height terganggu.
     o Token double-black menggantikan posisi black yang dihapus.
     o Proses terhadap token mengikuti kasus A,B,C.
• Token double-black pada node Red : mengubah warna node menjadi black, dan token akan dihapus.
• Token double-black pada root (black) : dapat dihapus, tidak ada pengaruh.
• Delete leaf RED, langsung dihapus karena tidak mempengaruhi keseimbangan black-height
Contoh :
i.

• Sibling dari node double-black : BLACK
• Satu nephew dari node double-black : RED
• Rotasi tunggal atau ganda dan token dihapus

ii.

• Sibling dari node double-black : BLACK
• Dua nephew dari node double-black : BLACK
• Token dipindahkan ke atas dengan perubahan warna tanpa rotasi