ARY ESWARA SAnnisya Aprilia P

Arie KrisnoantoSharif Hidayatullah

TIF-UB

Red-Black Trees (RBT) adalah Binary Search Tree (BST) dengan menyimpan data tambahan yaitu warna (Merah atau Hitam), yang 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.

RED BLAC

KTREE

ATURAN PADA RED BLACK TREE :

1. Setiap simpul/node adalah berwarna merah atau hitam2. Akar selalu berwarna hitam3. Nilai sebuah node adalah lebih besar anak kirinya dan lebih kecil dari anak kanannya.4. Jika node berwarna merah, anaknya harus berwarna hitam5. 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.

1. Setiap node baru yang disisipkan kedalam tree akan diberi warna merah, kecuali untuk root, warna merah tersebut langsung diganti dengan hitam.2. 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 merah4. 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.

ATURAN INSERT PADA RED BLACK TREE :

Data : 10 , 85 , 15 , 70 , 20 , 60 , 30 , 50 , 65 , 80 , 90 , 40 , 5 , 55

Data masuk

ATURAN DELETE PADA RED BLACK TREE :

- Jika sebuah node yang dihapus memiliki 2 anak, maka node yang dari anak kiri terbesar, atau anak kanan terkecil yang akan menggantikan si parent tersebut.- Jika parent berwarna merah dan anaknya merah, langsung digantikan saja (tidak ada masalah)- Jika parent hitam dan anakya merah, gantikan parent tersebut dengan anaknya, lalu warna anaknya yang merah tersebut gantikan warnanya menjadi hitam.- Jika parent dan anaknya hitam, maka gantikan parent tersebut dengan anaknya, lalu rotasikan dan sesuaikan dengan treenya.

30

20

40

15

25

10

18

28

38

50

28

28

18

TERIMAKASIH