Red Black Tree dan 2-3 Tree

Pada kesempatan kali ini, saya mau sedikit membahas mengenai Red Black Tree dan 2-3 Tree.
Sebenarnya apakah RBT dan 2-3Tree itu? kedua hal tersebut adalah 2 jenis tree yang memiliki syarat-syaratnya sendiri dan memiliki dasar dari sifat Binary Search Tree (BST).

Sebelum masuk ke Topik Red Black Tree itu sendiri, kita perlu mengenal dahulu apakah itu BST.
BST merupakan salah satu jenis tree yang mempunyai syarat sebagai berikut:
1. Setiap node mempunyai maksimal 2 tangan/link (umumnya left dan right)
2.  Pada saat penginputan, maka harus sesuai dengan aturan:
     a. Bila urutan angka yang diinput lebih kecil, maka masuk ke left. Kemudian seterusnya sampai inputan
         masuk menjadi leaf
     b. Bila urutan angka yang diinput lebih besar, maka masuk ke right. Kemudian seterusnya sampai inputan
         masuk menjadi leaf

 Red Black Tree

Setelah mengel sifat BST, maka Red Black Tree adalah pengembangannya. Pada RBT, maka akan ada tambahan sifat, yaitu:

• Setiap node mempunyai warna masing-masing (Red / Black)
• Setiap root akan mempunyai warna default hitam 
• Setiap node yang menunjuk ke arah NULL. Maka akan digantikan dengan dengan eksternal node (warna default hitam)
• Tidak boleh memiliki parent (merah) yang punya child (merah). Jadi tidak boleh ada warna merah yang saling terhubung.

Insert / input nilai pada RBT
Pada saat melakukan insert akan memakai aturan BST dengan tambahan beberapa aturan:

• Setiap node yang baru input akan mempunyai default merah.
• Bila ditemukan Parent (merah) dan Child (merah) maka akan ada 2 kemungkinan:
  1. Sibling dari parent berwarna merah juga. Maka parent dan sibling parent akan berubah warna menjadi hitam, child akan tetap merah, grandparent akan menjadi merah.
  2. Sibling dari parent berwarna hitam juga (Bila sibling merupakan eksternal node, maka juga akan berlaku aturan ini, karena default eksternal node adalah hitam). Maka akan dilakukan Single Rotate / Double Rotate. Parent akan menjadi hitam dan kedua anak menjadi merah.
  
  
    
  Sumber: Power Point MatKul Struct Data Bina Nusantara
  Gambar di atas merupakan simulasi dari insert kata "LABCOM".
  1. Pada saat L masukkan, warna node L adalah merah. namun karena L menjadi root, maka akan mengikuti default root menjadi hitam, sehingga node L menjadi hitam.
  2. Kedua yang akan di insert adalah A. huruf A mempunyai urutan lebih kecil dari A, maka akan diletakkan di sebelah kiri L. warna node A akan menjadi merah.
  3. Insert B, huruf B akan berada di sebelah kiri L lalu di sebelah kanan A. maka akan terjadi link antara node merah. Maka aturan akan berlaku, warna dari sibling-parent B (yaitu A) adalah hitam. Maka akan dilakukan Double Rotate dan hasil seperti digambar.
  4. Langkah ke 4, adalah input huruf C. Maka huruf C akan berada di sebelah kanan B, dan sebelah kiri L. Maka akan kembali ditemukan 2 node merah yang saling terhubung. Karena warna dari sibling-parent C (yaitu L) adalah merah. Maka aturannya, parent dan sibling-parent akan berubah menjadi hitam, dan child (menjadi hitam), grandparent menjadi merah. Tapi karena default root adalah hitam, maka root kembali menjadi hitam.
  5. Inputan selanjutnya adalah O. huruf O akan berada di kanan B dan L. Karena tidak ada warna node yang bermasalah, maka tidak dilakukan operasi apapun
  6. Huruf terakhir yang diinput adalah M. Huruf M itu sendiri akan berada di kanan B, L, dan di kiri O. Karena O dan M sama-sama merah dan C (sibling-parent) adalah merah. Maka ubah warna O dan C menjadi hitam, dan M menjadi merah.
  
  
  

  2-3 Tree

  Tree jenis ini juga merupakan salah satu jenis tree yang memiliki pengembangan. Ciri-ciri dari tree jenis ini adalah :
  
  • Setiap kedalaman leaf harus sama. Sehingga tidak berbeda kedalamannya.
  • Setiap node dapat mempunyai 2node / menyimpan 2 nilai yang berbeda.
  • Bila node tersebut ada 2 / menyimpan 2 nilai. Maka link turunannya harus lah 3.
    Namun bila hanya menyimpan 1 nilai. Maka link turunannya harus 2.