Senin, 18 Mei 2020
Pengenalan
Red-Black Tree diciptakan pada tahun 1972, oleh Rudolf Bayer. Saat pertama kali diciptakan, tree ini disebut "Symmetric Binary B-Tree". Meskipun Red-Black Tree terbilang kompleks, tree ini memiliki running time yang cepat untuk setiap operasinya serta sangat efisien.
Sebuah Binary Tree bisa disebut Red-Black Tree jika memenuhi kondisi berikut:
- Setiap node memiliki warna, antara hitam atau merah
- Root dari tree selalu berwarna hitam
- Semua external node berwarna hitam
- Jika suatu node berwarna merah, maka kedua anaknya pasti hitam
Operasi
Insertion
Red-Black tree merupakan binary tree, karena itu peraturan-peraturan pada binary tree berlaku juga pada red-black tree. Bedanya, saat melakukan insertion pada red-black tree, kita harus memperhatikan kondisi berikut:
- Jika tree masih kosong. Buat node baru sebagai root dengan warna hitam
- Jika node tidak kosong. Buat node baru sebagai leaf node dengan warna merah
- Jika parent dari node baru berwarna hitam, kita tidak perlu lakukan penyesuaian tambahan
- Jika parent dari node baru berwarna merah, cek warna sibling dari parent. Lalu perhatikan kondisi berikut:
- Jika sibling berwarna hitam, lakukan rotation sesuai dengan kondisi tree. Kemudian lakukan recolor
- Jika sibling berwarna merah, lakukan recolor. Kemudian cek apakah parent dari parent node baru adalah root atau bukan. Jika bukan, lakukan recolor kemudian recek dan sesuaikan dengan kondisi yang ada
Contoh insertion:
Deletion
Sama seperti insertion, deletion pada red-black tree juga harus memperhatikan peraturan yang ada pada binary tree. Namun pada red-black tree, deletion memiliki tambahan kondisi yang membuatnya menjadi lebih kompleks.
Penghapusan / deletion hanya bisa dilakukan pada leaf. Node lain selain leaf node hanya mengosongkan value dari node, tanpa menghapus node tersebut.
Ketika suatu node dihapus, dia akan digantikan oleh child nodenya. Warna dari child node akan menimpa warna dari parent. Sehingga saat kita menghapus suatu black node (dan dia mempunyai 2 black child), dia akan menjadi double black (DB). Hal itu juga berlaku pada leaf node, karena setiap leaf node sebenarnya memiliki 2 anak black node yang NULL (secara default).
Berikut kondisi yang perlu diperhatikan:
- Jika node yang ingin dihapus (harus leaf) adalah red node, maka node boleh langsung dihapus tanpa perlu melakukan cek kondisi atau penyesuaian tertentu
- Jika sibling dari DB adalah hitam dan kedua childnya (child dari sibling) adalah black node, ikuti step berikut:
- Hilangkan DB
- Pindahkan hitam ke parent (warna parent berubah jadi hitam jika warna awalnya merah, dan DB jika warna awalnya hitam)
- Buat sibling menjadi merah
- Jika DB masih ada, cek dan sesuaikan dengan kondisi lain
- Jika sibling DB adalah merah, tukar warna antara parent dengan sibling. Lalu rotate parent ke arah DB
- Jika sibling DB adalah hitam, dan childnya (dengan posisi paling jauh dari node DB) adalah hitam dan child lainnya (dengan posisi paling dekat dengan DB) adalah merah:
- Tukarkan warna sibling dari DB dengan warna anaknya (yang paling dekat dengan DB)
- rotate sibling ke arah menjauhi DB
- Lakukan kondisi 5
- Jika sibling DB adalah hitam, dan child dari sibling (yang jauh) adalah merah:
- Tukarkan warna parent dengan sibling
- rotate parent ke arah DB
- Hilangkan DB
- Ganti warna anak sibling yg merah, menjadi hitam
Contoh deletion:
