Red black tree sebenarnya memiliki beberapa rule yang masih sama dengan AVL tree , seperti jika lebih kecil cek ke sub-tree sebelah kiri jika lebih besar cek ke sub-tree sebelah kanan , tapi bedanya di RBT ini menggunakan warna hitam dan merah

Rule :

  • Root harus selalu hitam
  • New Node adalah merah
  • External node atau null node adalah hitam
  • Jika  node merah tanpa sibling , memiliki anak merah maka lakukan rotate (single/double)  #case1
  • Jika node merah dengan sibling , memiliki anak merah maka turunkan warna dari grand parent  #case2
  • Jika RBT tidak seimbang maka rotate (single/double) , single = ( kanan-kanan atau kiri-kiri ) , double = ( kanan-kiri atau kiri-kanan) #case3

In Example : 

Insert “LABCOMPUTING” to Red Black Tree

insert L

insert dengan warna merah , karena L adalah root maka ganti ke hitam

insertL

Insert A

karena A < L maka cek ke sub-tree sebelah kiri , kalau kosong langsung input node

insertL

 

Insert B

  • karena B < L maka cek ke sub-tree sebelah kiri ,
  • karena B > A maka cek sub-tree sebelah kanan , kalau kosong langsun input node
  • kita mendapatkan #case1 , parent dengan warna merah memiliki anak merah maka lakukan rotate , disini double rotate

 

 

doublerotate

Animasi Double Rotation

insertL

 

Insert C

  • karena C > B maka , cek sub-tree kanan ,
  • karena C < L maka cek sub-tree kiri , kalau kosong lagsung masukan node
  • tapi kita menemukan #case2 parent merah yang memiliki sibling merah dan anak merah , jadi kita harus turunkan warna dari root ke (A,L) jadi hitam
  • kemudian warna root kembali jadi hitam (B)

insertL

Insert O

  • O > B , cek sub-tree kanan
  • O > L , cek sub-tree kanan , jika kosong input node

insertL

 

Insert M 

  • M > B , cek sub-tree kanan
  • M > L , cek sub-tree kanan
  • M < O , cek sub-tree kiri , kosong input node
  • Kita menemukan #case2 lagi jadi kita ambil warna dari grand parent(L) , turun ke (C,O)

insertL

 

Insert P

  • R > B , cek sub-tree kanan
  • R > L , cek sub-tree kanan
  • R > O , cek sub-tree kanan, kosong input node
insertL

R di gambar seharusnya P

Insert U

  • U > L , cek sub-tree kanan
  • U > O , cek sub-tree kanan
  • U > P , cek sub-tree kanan , kosong input node
  • kita menemukan #case2 kembali ganti warna (M,P) menjadi hitam , ambil dari grand parent (O) ,turunkan lagi warna dari (B) ke (A,L)
  • karena RBT tidak seimbang , dalam case ini (single rotation) , kanan-kanan , maka lakukan single rotation dari root

insertL

Insert T

  • T > L , cek sub-tree kanan
  • T > O , cek sub-tree kanan
  • T > P , cek sub-tree kanan
  • T < U , input node
  • kita bertemu dengan #case1 ( double rotation )

insertL

Insert I

  • I < L , cek sub-tree kiri
  • I > B , cek sub-tree kanan
  • I > C , cek sub-tree kanan , input node

insertL

Insert N

  • N > L , cek sub-tree kanan
  • N < O , cek sub-tree kiri
  • N > M , input node

insertL

Insert G

  • G < L , cek sub-tree kiri
  • G > B , cek sub-tree kanan
  • G > I , cek sub-tree kanan

insertL