Pertemuan 7 - (Red Black Tree dan 2-3 Tree)

RED BLACK TREE

Red Black Tree adalah BST dimana terdapat node berwarna merah atau hitam.

ATURAN RED BLACK TREE :

1. root selalu berwarna hitam
2. external node selalu berwarna hitam
3. node yang baru di insert selalu berwarna merah
4. node merah tidak boleh bertemu merah (child merah)
5. jumlah node hitam sama dari root ke external node

INSERTION

terdapat dua kondisi jika terjadi masalah
1. jika node yang baru di insert memiliki paman hitam (Black Uncle) maka penyelesaiannya:

• Rotasi dan tukar warna parent dengan siblingnya untuk single rotation

2. jika node yang baru di insert memiliki paman merah (Red Uncle) maka penyelesaiannya:

• Tukar warna paman dan parent menjadi hitam dan grand parent menjadi merah 

DELETION

terdapat 6 case dalam deletion RBT :

1. Jika node yang ingin di hapus merah, maka langsung hapus saja 

2. Jika node yang ingin di hapus hitam, maka tukar dengan child lalu recoloring menajdi hitam

3. Jika terdapat double black memiliki keponakan merah, maka lakukan single rotation atau double rotation

4. Jika terdapat double black memiliki saudara merah (red sibling), maka lakukan rotasi tarik lalu recoloring (double black blm hilang)

5. Jika terdapat double black memiliki parent merah (red parent), maka dengan melakukan recoloring antara parent dengan sibling double black hilang

6. Jika terdapat double black memiliki saudara hitam (black sibling), maka dengan melakukan recoloring pada siblingnya, double black pindah ke parent

2-3 TREE

2-3 Tree berbeda dengan binary tree. setiap node yang memiliki satu data elemen memiliki setidaknya 2 children atau dua data elemen memiliki setidaknya 3 children.

Syarat-syarat 2-3 Tree antara lain:1. Semua data disimpan secara berurut.
2. Semua leaf ada pada level yang sama (level terbawah).
3. Setiap non leaf adalah sebuah 2 node atau 3 node
4. Sebuah 3 node terdiri dari 2 data elemen dan 3 child.
5. Sebuah 2 node terdiri atas 1 data elemen dan 2 child.

INSERTION

insert (45). ketika ingin melakukan insert 45 yang menuju dua node maka 45 bisa langsung disisipkan

insert (75). ketika ingin melakukan insert 75 yang menuju dua node tetapi sudah penuh maka kita akan membandingkan ketiga nila tsb. nilai yang berada di tengah akan menjadi parent.

DELETION

Kondisi 1 

Kondisi 2