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

Insert A

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

 

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

 

 

 

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)

Insert O

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

 

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)

 

Insert P

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

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

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 )

Insert I

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

Insert N

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

Insert G

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