Implementasi Red-Black Tree Dalam C – Part 3

Yak, jumpa lagi kita dengan tema red-black tree. Dan kali ini, akan membahas part tentang red-black tree insertion. Setelah sebelumnya sudah dibuat pusing dengan rotation, maka tulisan ini akan lebih membuat anda pusing dari sebelumnya, tapi untungnya tidak sampai bisa membuat anda muntah, apalagi sampai muntah darah. :v

Yuk, kita langsung lanjut saja ke topik pembahasan kita.

Proses insertion pada red-black tree bisa diawali dengan metode insertion ke struktur data tree biasa. Tapi selanjutnya, kita harus segera memberikan properti warna merah pada node yang baru ditambahkan tersebut. Dalam tullisan ini saya menggunakan nilai colour = 1, yang artinya berwarna merah/red; dan colour = 0 untuk merepresentasikan warna hitam.

Berikut pseudo-code untuk insertion awal.
RB-INSERT(T,z)
    y ← null
    x ← T->root
    WHILE x ≠ null DO
        y ← x
        IF z->data < x->data THEN
            x ← x->left
        ELSE
            x ← x->right
   
    z->parent ← y
    IF y = null THEN
        T->root ← z
    ELSE IF z->data < y->data THEN
            y->left ← z
        ELSE
            y->right ← z
   
    z->left ← null
    z->right ← null
    z->color ← RED
    RB-INSERT-FIXUP(T, z)

Tidak usah bingung, intinya, kita harus mencari posisi penempatan yang tepat, sesuai algoritma tree; yakni node yang nilainya lebih besar atau sama dengan nilai parent selalu berada di kanan. Jika tidak, taruh sebelah kiri. Dan, jangan lupa, kita sedang berhadapan dengan red black tree. Berikan node yang ditambahkan tersebut warna awal merah. Terakhir, kita akan memanggil fungsi Fix Up untuk memeriksa adanya tidaknya violation.

void RBTreeInsert(RBTree *tree, RBTreeNode *z){
 RBTreeNode *y = 0;
 RBTreeNode *x = tree->root;
 
 z->left = 0;
 z->right = 0;
 
 while (x != 0){
  y = x;
  if(z->data < x->data)
   x = x->left;
  else
   x = x->right;
 }
 z->parent = y;
 if(y == 0){
  tree->root = z;
 }
 else{
  if(z->data < y->data)
   y->left = z;
  else {
   y->right = z;
  }
 }
 z->colour = 1; //RED
 insert_fixup(tree,z);
}

Pemberian warna merah ini mungkin akan membuat node ini mengalami violation terhadap node lain terdekatnya. Maka dari itu, algoritma diperlukan untuk mengeliminasi kondisi violation ini

Selalu ingat bahwa node yang baru saja ditambahkan pasti berwarna merah.
Tahap berikutnya mungkin sedikit rumit, karena kita akan bertemu dengan banyak proses checking, comparison dan loop untuk memeriksa node terdekat yang mampu menimbulkan violation. Violation ini tidak cukup diatasi dengan mengganti warna node yang bersangkutan, tapi terkadang kita harus memutar-mutar posisi node, juga. Itulah mengapa pada artikel yang sebelumnya dibahas tentang rotation.

Tahapan pemeriksaan violation dalam proses insertion dilakukan dalam 3 tahap cek (case).

Case 1: node memiliki parent dan saudara parent (bisa disebut paman/uncle) yang warnanya sama-sama merah.
Violation ini diatasi dengan mengubah parent dan uncle menjadi hitam dan grand parent menjadi merah. Grandparent = node→parent→parent.

Case 2: node (lihat node z berikut) adalah child di sisi kanan dari parent. Lalu, disaat yang sama uncle (lihat y) dari node tersebut adalah hitam. Ingat, leaf node juga dianggap hitam, jadi bisa saja uncle merupakan leaf.

Case 3: Mirip case 2, disini node (lihat z) adalah child di sisi kiri dari parent. Di saat yang sama, uncle dari node tersebut (lihat y) berwarna hitam.

Kedua case ini bekerja secara bersama sama. Pertama saya jelaskan case 2. Misalnya, lihat gambar paling kiri di atas. Pada ilustrasi tersebut terjadi violation pada parent A terhadap child B, karena parent A berwarna merah, namun memiliki child merah (yaitu B).

Jika dilihat asal muasal violationnya, tidak beda jauh dengan case 1. Hanya saja, uncle di case 2 dan case 3 ini berwarna hitam. Coba perhatikan dan bandingkan lebih dekat. Lalu, untuk violation dalam case 2 ini, dapat diatasi dengan melakukan rotasi. Berdasarkan ilustrasi tersebut, lakukan rotasi kiri(left rotation), sehingga jadilah bentuk seperti ilustrasi yang tengah. Dengan kata lain, jika terjadi violation case 2, PASTI akan terjadi violation case 3.

Berikutnya kita bahas case 3. Case ini dapat terjadi ketika struktur node terlihat seperti ilustrasi yang tengah. Cara mengatasi violation ini adalah dengan melakukan rotasi sehingga menjadi seperti ilustrasi paling kanan. Sesuai ilustrasi tersebut, maka lakukan right rotation.

Case 2 dan case 3 yang telah saya jelaskan hanya berlaku ketika node A dan node B berperan sebagai child sebelah kiri dari C. Jika di arah kanan, ya, tinggal balik saja arah rotasinya. Setelah melakukan pemeriksaan dengan melihat ketiga case tersebut, kita juga perlu melihat kondisi parent. Pastikan tidak ada violation. Lanjutkan juga untuk memeriksa parent lebih atas lagi, dan seterusnya. Biar mudah, kita pakai while loop (lihat pseudo-code).

RB-INSERT-FIXUP(T, z)
    WHILE z->parent->color = RED DO
        IF z->parent = z->parent->parent->left THEN
            y ← z->parent->parent->right
            IF y->color = RED THEN
                //case 1
                z->parent->color ← BLACK
                y->color ← BLACK
                z->parent->parent->color ← RED
                z ← z->parent->parent
            ELSE
                IF z = z->parent->right THEN
                    //case 2
                    z ← z->parent
                    LEFT-ROTATE(T, z)
                //case 3
                z->parent->color ← BLACK
                z->parent->parent->color ← RED
                RIGHT-ROTATE(T, z->parent->parent)
        ELSE
            y ← z->parent->parent->left
            IF y->color = RED THEN
                z->parent->color ← BLACK
                y->color ← BLACK
                z->parent->parent->color ← RED
                z ← z->parent->parent
            ELSE
                IF z = z->parent->left THEN
                    z ← z->parent
                    RIGHT-ROTATE(T, z)
                z->parent->color ← BLACK
                z->parent->parent->color ← RED
                LEFT-ROTATE(T, z->parent->parent)
   
    T->root->color ← BLACK

Wow, sebegitu kah? jangan kawatir. Jika masih bingung, baca dan pahami penjelasan tentang ketiga case di atas. Kode yang akan ditunjukkan disini sama persis kok dengan yang telah dijelaskan.

Saat awal mempelajari red-black tree, saya sempat kesulitan. Masalahnya terletak pada pengecekan leaf node. Leaf node sama artinya dengan null pointer. Jadi ketika leaf node hendak diakses untuk dicek, node->colour; program akan mengalami fault. So, saya menulis macro sederhana untuk mengecek node dengan aman. Fungsi ini juga akan memeriksa apakah node yang dicek adalah null(leaf node). Jika iya, maka langsung dikatakan bahwa node tersebut adalah hitam.

#define IS_RED(x) ((x) ? ((x->colour) ? 1:0):0)

Macro di atas mengembalikan 1 jika merah, atau 0 jika hitam.
Terakhir, berikut saya sertakan kode untuk fix up node red-black tree yang baru dimasukkan.

void insert_fixup(RBTree *tree, RBTreeNode *z){
 RBTreeNode *y;
 while(IS_RED(z->parent)){
  if(z->parent == z->parent->parent->left){
   y = z->parent->parent->right;
   if(IS_RED(y)){
    z->parent->colour = 0;
    y->colour = 0;
    z->parent->parent->colour = 1;
    z = z->parent->parent;
   }
   else{
    if(z == z->parent->right){
     z = z->parent;
     rotate_left(tree,z);
    }
    z->parent->colour = 0;
    z->parent->parent->colour = 1;
    rotate_right(tree,z->parent->parent);
   }
  }
  else { //parent at right
   y = z->parent->parent->left;
   if(IS_RED(y)){
    z->parent->colour = 0;
    y->colour = 0;
    z->parent->parent->colour = 1;
    z = z->parent->parent;
   }
   else {
    if(z == z->parent->left){
     z = z->parent;
     rotate_right(tree,z);
    }
    z->parent->colour = 0;
    z->parent->parent->colour = 1;
    rotate_left(tree,z->parent->parent);
   }
  }
 }
 tree->root->colour = 0;
}

Masih sulit untuk mencobanya atau malas untuk melakukan debugging?
Tunggu chapter berikutnya, untuk melihat versi putting it all together.

Saat mempelajari red-back tree, saya sangat menganjurkan untuk mengikuti bacaan berikut. Chapter berikut ini akan sangat membantu.
software.ucv.ro/~mburicea/lab8ASD.pdf

Sekian dari saya, semoga tulisan ini bermanfaat.
See you on the next article.