Baru pertama belajar data structures, langsung berhadapan dengan yang namanya red-black tree. Linux adalah alasan saya mempelajari struktur data yang satu ini. Dalam sistem internal linux, red-black tree banyak digunakan untuk menyimpan data sistemnya, misalnya data free page memory.
Saat ini saya sedang mengembangkan sistem operasi dari scratch di Programmer OS Indonesia. dengan bercermin pada Windows dan Linux, sayapun membuat inovasi yang menggabungkan kelebihan antara keduanya. Memory management adalah sektor yang sedang saya fokuskan kali ini.
Saya lihat, banyak source code linux mengimplementasikan red-black tree. Saat pertama mendengar istilah ini, saya tidak tahu apa-apa. Akhirnya, dengan berbekal google, saya mendalami red-black tree ini. Bukan Cuma teori tapi praktek juga. So, langsung saja kita bahas red-black tree nya.
Red-black tree adalah salah satu bentuk struktur data BST(Binary Search Tree) yang menerapkan balancing dalam kerjanya. Untuk melakukannya, sebuah node red-black tree disertai dengan atribut yang menyatakan properti bernilai merah atau hitam. Secara umum, bentuknya sama dengan struktur binary tree pada umumnya; ada parent, left child dan right child. Karena ini red-black tree, ada 1 lagi, field colour yang menunjukkan field ini merah atau hitam.
typedef
struct
_RBTreeNode {
int
data;
int
colour;
//0
for black
struct
_RBTreeNode *parent;
struct
_RBTreeNode *left;
struct
_RBTreeNode *right;
}
RBTreeNode;
typedef
struct
RBTree {
RBTreeNode
*root;
}
RBTree;
Menurut referensi, algoritma red-black tree tidak jauh berbeda dengan AVL tree. Red-black tree tidak banyak melakukan balancing seperti AVL tree, jadi proses insertion lebih cepat. Sebagai imbasnya, tentu pencarian data dalam red-black tree lebih lambat jika dikomparasi dengan AVL tree. Akan tetapi, dengan kesederhanaan proses balancing yang dilakukan, red-black tree cenderung lebih cepat melakukan insertion dan deletion. Itu juga mengapa red-black tree digunakan dlam memory management di linux, karena dalam pekerjaan ini banyak dilakukan insertion dan deletion.
Cara kerja red-black tree ditentukan oleh field colour yang terdapat pada setiap node. Setiap node tidak boleh melanggar aturan pewarnaan berikut.
1. Setiap node memiliki warna merah atau hitam.
2. Root node (node paling awal) SELALU hitam.
3. Setiap leaf(daun) adalah hitam. Leaf adalah istilah untuk node NULL. Maksudnya? Misalnya node tidak memiliki left child dan right child. Artinya field node->left dan node->right nya kan 0, tuh. Nah node NULL itulah yang dimaksud leaf.
4. Jika node berwarna merah, kedua child node (left child & right child) HARUS hitam.
5. Untuk setiap node, yang setingkat harus memiliki jumlah node hitam yang sama jika diturut dari node tersebut hingga ke leaf. Ingat, leaf adalah hitam.
Prinsip kerjanya, nanti ketika dilakukan insertion, node baru akan diberi warna awal merah. Jika terjadi violation (melanggar catatan-catatan di atas), maka proses balancing akan dilakukan. Misalnya, ketika parent berwarna merah; nah, kan jika node merah, kedua child-nya harus hitam..
OK, sampai itu dulu pembahasan awal red black tree. Yang ini buat pengantar saja. Kalau banyak-banyak entar takut pusing. Untuk implementasinya, tunggu part 2 ya..
0 comments