Atau disingkat sebagai RBT, adalah jenis tree yang di seimbangkan dengan pengelompokan warna yang di bedakan menjadi 2 warna yaitu hitam dan merah.
Syarat-Syarat yang berlaku dalam RBT:
- Setiap Node memiliki warna, antara hitam atau pun Merah.
- Root yang ada dalam Tree tersebut harus berwarna Hitam.
- Setiap External Node yang ada berwarna Hitam.
- Jika sebuah Node berwarna Merah, maka kedua anaknya pasti berwarna Hitam.
Insertion:
Dalam Insertion, proses yang dilakukan sama dengan Binary Search Tree. Namun memiliki syarat setiap Node yang dimasukan memiliki warna Merah.
Apabila saat Node dimasukkan, memiliki Parent yang berwarna Merah, maka ada pelanggaran yang terjadi dari aturan yang telah ditetapkan.
Untuk memperbaikinya, kita bisa melakukan LL, LR, RR, RL rotation. agar Tree tersebut kembali seimbang dan memenuhi syarat pewarnaan yang ada.
Berikut adalah contoh dari double rotation
Perhatikan bahwa setiap Node leave terakhir memiliki external node dengan default color black.
Deletion
Berikut adalah catatan yang diberikan dari dosen saya.
Delete
M = target delete
C = pengganti
jika M = red , C = Black langsung ganti
jika M = black ,
C = red langsung ganti dan recolor C = black
jika M = black ,
C = black akan menciptakan token double black di posisi C
C = N
S = sibling
Sl = sibling left
Sr = sibling
right
P = parent
kondisi 1 jika S
= red , SL & SR = black
maka reverse
color P dan S dan rotate di P , token black tetap ada di N
kondisi 2 jika s
= black , SL & SR = black
maka recolor S =
red , token black pindah ke P
jika warna P =
red recolor jadi black jika P = black maka terjadi double black lg
kondisi 3 jika S
= black , SL / SR = RED
maka rotate di
parent (single/double), parent baru mengikuti warna parent lama dan kedua
anaknya jadi hitam , lalu token black hilang
nb : jika token
double black berada pada node merah, maka node tsb menjadi hitam dan
token
double black hilang.
No comments:
Post a Comment