RED BLACK TREE

Red Black Tree bisa disebut sebagai Binary Search Tree yang mempunyai fungsi yang sama.

Ciri-ciri dari Red Black Tree adalah:

1. Setiap node mempunyai warna yang antara lain adalah merah atau hitam

2. Root (external node) selalu berwarna hitam

3. Leaf atau akar dari root berwarna hitam

4. Jika suatu node berwarna merah, maka anak-anaknya berwarna hitam

5. Node yang baru dimasukkan selalu berwarna merah

Insertion

Ada beberap violation yang dapat terjadi dalam insertion:

 

  1. Jika parent dan uncle dari new node adalah merah, maka violation dapat dihindari dengan cara merubah wanr dari parent dan uncle menjadi hitam

rbbt2

  • Jika parent dari new node adalah merah dan unclenya adalah hitam (external node termasuk warna hitam), lalu new node lebih kecil daripada nilai dari parentnya, maka yang harus dilakukan adalah melakukan single rotate seperti pada gambar

rbt3

  • Jika parent dari new node adalah merah dan unclenya adalah hitam (external node termasuk warna hitam), lalu new node lebih besar daripada nilai dari parentnya, maka yang harus dilakukan adalah melakukan double rotate seperti pada gambar

rbt4

Deletion

Deletion pada Red Black Tree umumnya sama seperti pada BST

Dalam Deletion pada Red Black Tree, ada dua hal yang dapat terjadi pada umumnya

  • Jika node yang ingin di-delete adalah node merah, maka dapat langsung dihapus
  • Jika node yang ingin di-delete adalah node hitam, maka dapat terjadi double black

 

Pada gambar dibawah, terjadi double black pada node a. Jika saudara dari a adalah merah, maka terjadi single rotatation dan X menjadi warna merah.

1464017084182

 

Pada gambar di bawah, jika a adalah double black dan Y beserta anak-anaknya adalah hitam juga, maka Y akan menjadi warna merah dan double black berpindah kepada parent dari a dan Y.

1464017100780

 

Pada gambar di bawah, a adalah double black, saudara dari a (Z) adalah hitam dan mempunyai anak yang berwarna merah. Pada kondisi tersebut, harus dilakukan double rotation.

1464017109944

 

2-3 Tree

2-3 Tree:

  • Setiap internal node merupakan 2 node yang punya 1 data dan 2 anak, atau 3 node yang punya 2 data dan 3 anak
  • Semua leaf harus berada dalam level yang sama
  • Semua node ter organisir seperti halnya dengan BST

Insertion

  • Jika tree kosong, insert new node pada letaknya
  • Jika tree sudah terisi satu value, maka buat node barunya di sebelah value dalam node tersebut
  • Jika tree sudah terdapat 2 value, dan masih ingin diletakkan node baru, maka value tengah dari ketiga tersebut akan split twothree3