Red Black Tree

Hampir sama dengan blog yang terakhir, sesi kali ini tetep panasssss tapi materi kali ini ga terlalu susah buat dingertiin dan cukup lah…

Jadi,

Red Black Tree

Cara buat menginsert datanya sama dengan BST yaitu yang lebih kecil ke sebelah kiri dan yang lebih besar di sebelah kanan.

Disebut Red Black Tree karena setiap Node PASTI punya warna sendiri. Antara Merah atau Hitam.

-    Aturannya :

1.   SETIAP Node harus punya warna yaitu Merah atau Hitam.

2.   Root HARUS berwarna Hitam.

3.   Semua Node-External (Node yang ga keliatan) warnanya Hitam.

4.   Node yang warnanya Merah, 2 Children-nya harus Hitam.

-    Contoh   :

Disini, 13 adalah Root makanya warnanya Hitam.

8 dan 17 berwarna Merah, oleh karena itu Children-nya harus berwarna Hitam.

Untuk kasus yang lain punya cara penyelesaiannya masing-masing.

Pada kasus ini, A (Merah) punya Child X yang warnanya Merah juga. Dan ini melanggar aturanya.

Nah disini, cek Sibling dari A terlebih dahulu (C) kalo Sibling tersebut warnanya merah juga. Maka langsung ubah A dan Siblingnya (C) menjari Hitam dan Parentnya menjadi Merah. Tapi karena Parentnya (B) adalah root, maka tetap berwarna Hitam.

Kalau Sibling dari A tersebut berwarna Hitam atau Kosong (External Node), maka harus dilakukan Rotasi sesuai tempatnya.

Contoh Rotasi seperti di bawah ini :

-   Deletion :

Delete data disini juga sama dengan BST, yaitu diganti dengan Left Child – Right Most Child. Nah setelah diganti, barulah ada aturan yaitu Parent yang berwarna Hitam tidak boleh bertemu Child berwarna Hitam juga.

Cara menyelesaikannya sama dengan Insertion yaitu dengan Rotasi atau ubah warna saja.