Data Structures 07 :

• 2-3 Tree
• Red Black Tree

2-3 Tree :

2-3 Tree ada 2 jenis node

• node 2 : tidak punya anak atau punya 2 anak.  contoh node 2. p dan q bisa null bisa ber angka :  
• node 3: tidak punya anak atau punya 3 anak. contoh node 3. p, q dan r bisa null bisa ber angka : 

2-3 Tree harus simetris, alias perbedaan level kiri dan kanan harus sama.

Insert :

• Selalu insert mengisi yang kosong dari paling atas. kalau dari bawah kosong, cek dahulu ke parentnya, apakah kosong atau penuh, jika kosong, naik lagi sampai terisi bagian atas semua.

Delete:

• Jika yang di delete adalah leaf node, bisa langsung dilakukan penghapusan.
• Jika bukan, harus dilakukan reposisi.

Red Black Tree

Kriteria:

• Root selalu berwarna hitam
• Paling bawah selalu terdapat null node (hitam)
• Tree balance tidak balance dihitung dari jumlah lompatan node hitam dari setiap null node. Jumlahnya harus sama.

Insert :

Node yang baru diinsert selalu berwarna merah.

Jika node yang baru masuk, parent dari node tersebut berwarna merah, dan tetangga dari parent tsb juga berwarma merah, maka harus dilakukan color flip : 

Jika node yang baru masuk, parent dari node tersebut berwarna merah, dan tetangga dari parent tsb berwarma hitam, maka harus dilakukan single/double rotation seperti AVL :

Jika setelah melakukan color flip dan mengubah root node menjadi merah, maka harus dilakukan Re-coloring. atau mengubah warna menjadi hitam. re-coloring ini biasa hanya berlaku untuk root node.