Jumat, 28 Oktober 2016

Implementasi Red-Black Tree Dalam C – Part 2

Jika belum baca part 1, silahkan baca dulu sebelum membaca yang ini. OK ?
Pada tulisan ini, pembahasannya akan ditujukan pada pemahaman awal sebelum insertion. Juga, tulisan ini akan sedikit menyinggung tentang sedikit prinsip kerja binary tree. Jadi, bagi yang belum tahu apa-apa, bisa memperoleh sedikit gambaran, kan.

Red-black tree memiliki prinsip dasar seperti binary tree biasa. Dalam binary tree setiap node punya field pointer ke parent, pointer ke left child node, dan pointer ke right child node. Setiap right node pasti memiliki nilai yang lebih besar; dan left node memiliki nilai yang lebih kecil.
Misalnya, kita masukkan nilai 10, 13, 4, 11 dan 15..


Tidak ada yang aneh ?
Hmm, bagaimana jika ditambah beberapa nilai lagi ? +16, 17, 18 dan 19 ?

WTF. Panjang sekali! Jangan kawatir, hal ini tidak akan pernah terjadi pada red-black tree. Saat terjadi violation, red-black tree akan melakukan sejumlah operasi untuk menyeimbangkan tree. Operasi yang saya maksud adalah operasi rotasi lalu diikuti dengan merubah warna node. Hal ini terus dilakukan hingga tidak ada node yang mengalami violation.

Sebelum tahu benar-benar bagaimana proses insertion dilakukan, pertama kita ketahui bagaimana cara merotasi node.

Node bisa dirotasi ke arah kiri, ataupun ke kanan; tergantung kondisi violation. Proses rotasi bisa dilihat di gambar berikut. Jika merasa bingung, coba gambarkan dalam secarik kertas dan imajinasikan bagaimana node bergerak dan berganti kaki dalam pikiran anda.


Biar lebih mudah, berikut pseudo-code nya.

LEFT-ROTATE(T, x)
    y ← x->right
    x->right ← y->left
    y->left->parent ← x
    y->parent ← x->parent
    IF x->parent = null THEN
        T->root ← y
    ELSE
        IF x = x->parent->left THEN
            x->parent->left ← y
        ELSE
            x->parent->right ← y
    y->left ← x
    x->parent ← y

RIGHT-ROTATE(T, x)
    y ← x->left
    x->left ← y->right
    y->right->parent ← x
    y->parent ← x->parent
    IF x->parent = null THEN
        T->root ← y
    ELSE
        IF x = x->parent->right THEN
            x->parent->right ← y
        ELSE
            x->parent->left ← y
    y->right ← x
    x->parent ← y


Dan, jika anda sudah paham bagaimana melakukan rotasi, coba pahami kode hasil implementasi yang sudah saya buat berikut. Jika sulit, pandangi kembali proses rotasi serta pseudo-code nya.

void rotate_left(RBTree *tree, RBTreeNode *x){
 RBTreeNode *y = x->right;
 x->right = y->left;
 
 if(y->left) y->left->parent = x;
  y->parent = x->parent;
 if(x->parent == 0)
  tree->root = y;
 else if(x == x->parent->left)
   x->parent->left = y;
  else
   x->parent->right = y;
 x->parent = y;
 y->left = x;
}

void rotate_right(RBTree *tree, RBTreeNode *x){
 RBTreeNode *y = x->left;
 x->left = y->right;
 
 if(y->right) y->right->parent = x;
  y->parent = x->parent;
 if(x->parent == 0)
  tree->root = y;
 else if(x == x->parent->left)
   x->parent->left = y;
  else
   x->parent->right = y;
 x->parent = y;
 y->right = x;
}
 
Aduh, rumit sekali, ya. Padahal masih part 2!
Hahaha, Don't worry, saya masih punya banyak part untuk dijejalkan pada anda. Tapi, untuk insertion, kita cuma butuh 1 part lagi. Just wait it..
Sembari menunggu part selanjutnya, anda bisa mendalami proses rotasi, sembari meminum secangkir kopi. :D
Load disqus comments

0 comments