RED BLACK TREE

Red Black Tree adalah salah satu contoh dari self-balancing binary search tree.

Suatu Binary Search Tree di anggap Red Black Tree jika :

1. Setiap node mempunyai warna, hitam atau merah.
2. Warna default Root adalah hitam
3. Semua external nodes warnanya hitam
4. Node berwarna merah anaknya harus berwarna hitam
   (Tidak boleh ada node merah beranak merah)

Insertion

1. Operasi Insert pada Red Black Tree sama seperti Binary Search Tree.
2. New Node selalu berwarna merah.
3. Jika parent dari node itu bewarna merah, maka terjadi violation.

Contoh :

1.

–> Parent berwarna hitam, tidak terjadi violation.

2. 

–> jika Parent dan Paman dari X berwarna merah, ubah Parent dan Paman menjadi hitam, lalu kakek nya menjadi merah.

3. –> Bila Parent dari X berwarna merah dan Paman dari X berwarna hitam, Maka lakukan Rotasi. Ubah pivot rotasi menjadi hitam dan anak-anaknya menjadi merah.

Singel Rotation

Double Rotation

Deletion

1. Deletion pada Red Black Tree sama seperti deletion pada Binary Search Tree
2. Bila node yang mau dihapus berwarna merah, gantilah dengan anaknya yang pasti berwarna hitam.
3. Bila node yang mau dihapus berwarna hitam & anaknya merah, gantilah dengan anaknya lalu ubah warna anaknya menjadi hitam.
4. Bila node yang mau dihapus dan anaknya berwarna hitam :

Contoh :

1.   –> Bila Sibling berwarna merah, tukar warna Sibling dan Parent, lalu lakukan rotasi pada Parent.
2. –> Bila Sibling berwarna hitam dan keduanya anaknya juga hitam, maka ubah warna Sibling menjadi merah.
3. 

–> Bila Sibling berwarna merah dan ada anaknya yang berwarna merah, maka lakukan rotasi.

2-3 TREE CONCEPT

2-3 tree concept adalah sebuah struktur data dimana setiap node mempunyai 2 anak dan 1 data atau 3 anak dan 2 data.

Syarat-syarat dari 2-3 Tree Concept :

1. Setiap node yang bukan leaf adalah 2-node (1 data dan 2 anak) atau 3-node (2 data dan 3 anak).
2. Semua data disimpan secara berurutan.
3. Semua leaf ada pada level yang sama.

• letakkan data yang ingin di insert ke posisi yang benar (urut).
•  jika leafnya 2 node, maka langsung di insert menjadi 3 node.

• 3. jika leafnya 3 node, maka yang tengah harus naik menjadi parent yang childnya 2 / 3 data.

 

 

Deletion

• Carilah data pada leaf untuk menggantikan data yang ingin di hapus.
• Jika leaf itu 3 node, maka hapus saja data itu sehinggal menjadi 2 node.

Delete (23), node berada di leaf dan leafnya 3 node, jadi langsung hapus.

• Jika leaf tersebut adalah 2-node & parent adalah 3-node, ambil satu nilai dari parent.
  – Bila sibling adalah 3-node, push satu nilai sibling ke parent sehingga parent tetap 3-node
  – Bila sibling adalah 2-node, ubah parent menjadi 2-node lalu gabungkan leaf dengan sibling

Delete (50), 40 akan menggantikan 50.

40 naik menggantikan 50, tetapi 30 akan turun bersebelahan dengan 25.

Hasil akhirnya.

www.binus.ac.id

www.skyconnectiva.com