RED-BLACK TREE DALAM JAVA

Red-Black Tree adalah binary tree yang memliki atribut warna hitam dan merah.

Dalam penyusunan Red-Black Tree terdapat aturan-aturan sebagai berikut:
1. Setiap simpul (node) selalu berwarna merah (red) atau hitam (black).
2. Simpul akar (root) selalu berwarna hitam (black).
3. Jika simpul (node) berwarna merah (red), maka simpul anaknya (child) harus berwarna hitam (black).
4. Setiap lintasan dari simpul akar ke daun (leaf), simpul anak yang paling bawah atau ke simpul anak yang bernilai null, harus memuat bilangan simpul hitam (black) yang sama.
Karena simpul-simpul dalam Red-Black Tree selalu berwarna merah (red) dan hitam (black), maka terdapat aturan-aturan yaitu sebagai berikut:
• Setiap simpul yang berwarna merah selalu memiliki 2 simpul anak yang berwarna hitam.
• Setiap “daun” yang memiliki 2 anak yang berwarna hitam (simpul kosong [empty] dan dianggap berwarna hitam).
• Setiap lintasan dari suatu simpul ke “daun” turunan memuat jumlah simpul anak yang berwarna hitam yang sama atau disebut black height.
Langkah-langkah yang dilakukan jika aturan warna dilanggar:
1. Melakukan perubahan warna simpul.
Perubahan warna simpul dilakukan dengan cara mengubah warna simpul-simpul anak (color flip).
2. Melakukan rotasi.
Rotasi merupakan pengaturan ulang simpul-simpul sedemikian hingga sehingga pohon biner menjadi lebih seimbang.
Aturan selanjutnya yaitu, jika memiliki pohon biner yang tidak seimbang yang memiliki 2 atau lebih pangkat (sudah mengikuti aturan dengan benar dan konsisten “main“ untuk sebuah Red-Black Tree). Dalam aturan Red-Black Tree pohon biner akan tetap seimbang. Jika suatu lintasan memiliki panjang lebih dari satu simpul dibanding lintasan yang lain, dapat dipastikan pohon biner tersebut memiliki lebih banyak simpul berwarna hitam, atau pohon biner banyak memiliki simpul berwarna merah.
Dari aturan 4 di atas, menspesifikasikan bahwa semua lintasan yang berawal dari simpul akar ke simpul daun manapun atau ke semua simpul anak yang bernilai NULL harus memiliki jumlah simpul hitam yang sama. Anak NULL adalah anak yang mungkin memiliki simpul non daun atau juga tidak memilikinya. Seperti gambar berikut ini:


Dari gambar di atas, dapat dijelaskan bahwa lintasan dari 5 ke 25 ke simpul anak sebelah kanan nilai 25 (merupakan anak NULL) hanya memiliki satu simpul warna hitam, yang tidak sama dengan jumlah simpul hitamnya dengan lintasan dari 6 ke 75 dimana yang terakhir memiliki dua simpul hitam. Hal ini melanggar aturan ke-4, meski kedua lintasan ke simpul daun memiliki jumlah simpul hitam yang sama. Black height digunakan untuk mendeskripsikan jumlah simpul hitam dari suatu simpul ke simpul akarnya. Dengan demikian black height untuk simpul 5 adalah 1, black height untuk simpul 25 juga 1, black height untuk simpul 12 adalah 2, dan seterusnya.
Dari gambar di atas, juga terlihat melanggar aturan Red-Black Tree ke-4 sehingga perlu dilakukan pengaturan ulang susunan simpul-simpul. Jika semua simpul yang ada di sebelah kiri simpul akar dipindahkan ke sebelah kanan, disebut dengan rotasi. Aturan-aturan rotasi dalam Red-Black Tree yaitu:
• Melakukan pengaturan simpul-simpul ke atas atau ke bawah untuk menyeimbangkan pohon biner.
• Memastikan bahwa aturan dan karakteristik pohon pencarian biner tidak dilanggar.
Dalam pohon pencarian biner (pohon biner yang dioptimalisasi [seraching] elemen-elemen tertentu) simpul anak sebelah kiri selalu memiliki nilai kunci (key) yang lebih kecil dari pada nilai yang ada di simpul induknya, sebaliknya simpul anak sebelah kanan selalu memiliki nilai kunci (key) yang lebih besar dari simpul induknya. Pengaturan warna dan perubahan warna simpul (color flip) digunakan untuk membantu menentukkan kapan perlu dilakukannya rotasi. Seperti gambar berikut ini:


Rotasi perlu dilakukan untuk penyisipan atau penghapusan simpul-simpul. Dalam algoritma rotasi yang akan dilakukan oleh komputer, rotasi dilakukan dengan kendali program. Tetapi sebelumnya harus dilakukan secara manual.
Seperti pada gambar 2, dapat dilihat bahwa semua simpul bergerak. Simpul 12 mengikuti simpul 25 ke atas, kemudian simpul 50 mengikuti simpul 75 ke sebelah kanan bawah. Kemudian simpul 37 lepas dari simpul 25 yang merupakan induknya dan menjadi simpul anak sebelah kiri dari simpul 50. Namun hal ini melanggar aturan reed black tree sehingga perlu dilakukan color flip dibagian selanjutnya. Simpul 37 dinamakan sebagai cucu sebelah dalam (inside grandchild) dari simpul root yaitu simpul 50, sedangkan simpul 12 merupakan cucu sebelah luar (out grandchild). Cucu sebelah dalam, jika merupakan anak dari simpul yang bergerak ke atas (yang merupakan simpul anak sebelah kiri dari simpul root pada rotasi kanan) selalu terputus dari induknya dan terhubung kembali ke kakek (grand parent) sebelumnya.
Untuk melakukan penyisipan data tertentu pada pohon biner, pertama kali yang dilakukan adalah penyisipan adalah inisialisasi penggunaan simpul dengan nama X, P, dan G untuk merancang pola bagi simpul yang terlibat dalam metode penyisipan. Dalam hal ini X akan merujuk pada simpul baru yang akan disisipkan dan kadang dirujuk pada simpul anak saat simpul induk mengalami konflik merah-merah (red-red conflict). X akan dirujuk sebagai simpul yang akan disisipkan, P sebagai simpul induk dari X sedangkan G merupakan kakek (grand child) dari X (induk dari P).
Langkah-langkah turun pohon biner untuk menemukan posisi penyisipan (insertion point), yang dilakukan pertama kali adalah perubahan warna (color flip) seperti gambar (berapa) diperolah bahwa simpul hitam (black node) yang memiliki 2 simpul anak berwarna merah (red child node). Dalam hal ini kadang color flip menyebabkan konflik merah-merah. Konflik ini sering ditunjukan sebagai simpul anak merah X dan induk merah P. Konflik merah-merah dapat diselesaikan dengan rotasi tunggal atau ganda (bergantung pada simpul yang berotasi merupakan outside grandchild atau inside grandchild dari G). Sesuai dengan aturan colour flip dan rotasi maka akan ditemukan titik penyisipan dan kemudian akan menyispkan simpul yang baru. Setelah menyisipkan simpul yang baru, jika mula-mula P berwarna hitam maka dengan mudah dapat menempelkan simpul merah yang baru, sebaliknya jika P berwarna merah ada 2 kemungkinan langkah yang akan dilakukan yaitu outside grandchild atau inside grandchild dari G. selain itu juga perlu dilakukan perubahan warna (color flip).
Jika X merupakan outside grandchild maka perlu dilakukan satu rotasi (rotasi tunggal) sedangkan inside grandchild maka perlu dilakukan dua kali rotasi (rotasi ganda) sehingga keseimbangan pohon biner tetap terjaga.
 Color flip bergerak ke bawah
 Melakukan rotasi tunggal saat simpul disisipkan
 Melakukan rotasi lebih lanjut
Proses penyisipan pada Red-Black Tree pertama kali yang dilakukan adalah proses pencarian mengenai lokasi penyisipan yang tepat melintasi baik lintasan kiri (left path) maupun lintasan kanan bergantung pada nilai kunci (key) yang dimiliki oleh simpul yang akan disisipkan.
Aturan untuk melakukan uji color flip yaitu: setiap saat metode atau fungsi penyisipan menjupai simpul hitam yang memilki 2 simpul anak berwarna merah, metode atau fungsi ini harus mampu mengubah warna simpul anak menjadi hitam dan warna induknya menjadi merah (kecuali jika induknya adalah simpul akar [root] simpul akar harus tetap berwarna hitam).


Dari gambar di atas (sebelah kiri) terlihat bahwa P adalah parent, anak sebelah kiri P adalah X1, dan anak sebelah kanan P adalah X2. Sebelah kanan memperlihatkan keadaan simpul-simpul setelah proses color flip. Teknik color flip membiarkan jumlah simpul hitam (black height) pada lintasan dari simpul akar (root) melewati P hingga ke daun atau simpul yang bernilai NULL. Dalam hal ini semua lintasan akan melewati P, kemudian melewati baik X1 maupun X2. Sebelum terjadi color flip hanya simpul P yang berwarna hitam sehingga segitiga (yang terdiri dari P, X1, dan X2) perlu ditambah dengan satu simpul hitam pada masing-masing lintasan. Setelah proses color flip, P tidak lagi berwarna hitam tetapi anak-anaknya yang berwarna hitam sehingga segitiga P, X1, dan X2 berkontribusi pada tambahan satu simpul berwarna hitam pada setiap lintasan yang dilewati.
Sistem dala perubahan color flip yang mengubah simpul daun yang berwarna merah dapat disebut red leaf dan yang mengubah simpul daun berwarna hitam disebut black leaf.
Dari gambar 3 (sebelah kanan) memperlihatkan bahwa simpul-simpul setelah proses color flip yang melibatkan aturan Red-Black Tree dimana simpul anak dan induknya keduanya tidak boleh berwarna merah karena dapat melanggar aturan Red-Black Tree. Jika induk P berwarna hitam maka tidak akan menimbulkan masalah yang terjadi saat P berubah dari hitam ke merah. Meski demikian jika induk berwarna merah kemudian setelah perubahan warna maka dalam satu baris akan terdapat dua simpul berwarna merah. Dalam hal ini melanggar aturan Red-Black Tree sehingga perlu dilakukan rotasi. Untuk simpul akar dan dua simpul anaknya yang menyebabkan semuanya berwarna hitamnya maka dalam hal ini tidak terjadi konflik merah-merah sebab semua sudah berwarna hitam dan tidak simpul yang berwarna merah. Selain itu juga karena simpul akar dan satu atau lebih simpul anak dalam setiap lintasan, black height untuk setiap lintasan bertambah dengan nilai yang sama yaitu 1.


Setelah melakukan color flip dan rotasi untuk menentukkan tempat penyisipan, untuk selanjutnya dilakukan penyisipan simpul baru. Penyisipan dilakukan dengan menggunakan metode/fungsi insert () yang sama seperti pada pohon biner. Cara untuk melakukan rotasi tunggal terlihat pada gambar di bawah ini:


Dari gambar di atas, simpul baru yang akan disisipkan (disebut X) dan simpul X yang baru selalu berwarna merah. Terdapat 3 kemungkinan yang akan didapat setelah melakukan penyisipan simpul X, yaitu:
1) P berwarna hitam.
2) P berwarna merah dan X merupakan outside grandchild dari G.
3) P berwarna merah dan X merupakan inside grandchild dari G.
Jika P berwarna hitam, maka penyisipan dilakukan secara bebas karena simpul yang baru (X) selalu berwarna merah. Jika P berwarna merah dan X merupakan outside grandchild, maka harus dilakukan rotasi tunggal dan beberapa perubahan warna (color flip). Sebagai contoh gambar di bawah ini, di mana kita akan menyisipkan simpul yang memiliki nilai 6.


Jika P berwarna merah dan X merupakan outside grandchild, maka ada beberapa langkah yang harus dilakukan untuk mengembalikan aturan Red-Black Tree, yaitu:
• Mengubah warna “kakek” X (simpul 25)
• Mengubah warna induk (simpul 12)
• Melakukan rotasi dengan “kakek” X (simpul 25) pada “top” dengan arah simpul X (simpul 6) yang merupakan simpul kanan.


Jika P berwarna merah dan X merupakan inside grandchild, maka harus dilakukan 2 kali rotasi dan beberapa perubahan warna simpul-simpul. Jika melalukan rotasi ke kanan dengan simpul G (simpul 25) sebagai “top”, inside grandchild akan bergerak melintas alih-alih ke atas sehingga pohon biner tidak lebih seimbang dari semula. Dalam hal ini teknik yang digunakan adalah dengan melakukan 2 kali rotasi (rotasi ganda). Dalam rotasi ganda juga harus melakukan beberapa perubahan warna yang dilakukan setiap kali melakukan rotasi baik left rotasion maupun right rotasion.
Langkah-langkah yang dilakukan jika P berwarna merah dan X merupakan inside grandchild adalah sebagai berikut:
• Mengubah warna “kakek” X (simpul 25)
• Mengubah warna X (bukan induknya)
• Melakukan rotasi dengan P (induk X) sebagai simpul “top” dengan arah X (melakukan rotasi ke arah kiri)
• Melakukan rotasi sekali lagi dengan “kakek” X (simpul 25) sebagai simpil “top” dengan arah X (melakukan rotasi ke arah kanan)
Dengan langkah-langkah di atas, maka pohon biner dapat kembali seimbang.
Proses penghapusan pada Red-Black Tree dilakukan dengan mengubah warna dan melakukan rotasi-rotasi untuk menghapus simpul-simpul tertentu. Sedangkan untuk proses pencarian dibutuhkan pembandingan-pembandingan sekitar log2N dan dapat dibuktikan tidak pernah terjadi pembandingan-pembandingan lebih dari 2*log2N.
Waktu yang diperlukan untuk melakukan penyisipan (insertion) dan penghapusan bertambah dengan nilai nilai yang tetap/konstan karena Red-Black Tree harus melakukan color flip dan melakukan rotasi-rotasi di sekitar titik penyisipan dan titik penghapusan (deletion point). Dengan demikian penyisipan pada Red-Black Tree membutuhkan waktu sekitar 0(log2n). Dari kondisi di atas, Red-Black Tree lebih sesuai digunakan pada aplikasi-aplikasi yang kegunaan utuamanya adalah pencarian-pencarian dan hanya sedikit melakukan penyisipan dan penghapusan, misalnya pada aplikasi-aplikasi basis data lanjut seperti Datawarehouse atau Data Mining. Dengan demikian salah satu keunggulan dari Red-Black Tree untuk data-data terurut adalah kecepatan pencariannya, jika dibandingkan dengan pohon biner yang biasa yang juga telah terurut.
Pada saat implementasi, pada umumnya penyisipan-penyisipan (data insertion) akan berjalan lebih cepat jika data-data yang masuk dalam keadaan sudah terurut, hal ini akan meningkatkan kinerja Red-Black Tree dalam melakukan penyeimbangan-penyeimbangan saat terjadi penyisipan dan penghapusan data-data berikutnya, yaitu dengan cara meminimalisai proses-proses color flip dan rotasi-rotasi yang harus dilakukan.