Blog untuk Tugas

Nama: Wilson Nursalim
NIM: 1901516495

Rangkuman Pertemuan 7

www.binus.ac.id
www.skyconnectiva.com

Red Black Tree

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

Syarat Red Black Tree:

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)

External nodes adalah anak dari leaf. Sebenarnya external node itu cuma hayalan. Bila suatu node baru di-insert maka akan ditaruh di salah satu external node.

Insertion pada Red Black Tree

1. Masukkan node baru seperti pada BST
2. Warna node baru itu merah
3. Jika parent dari node baru itu merah, berarti terjadi violation. Kita harus memperbaiki Tree.

Contoh:  (X adalah node baru yang di-insert)

1. Bila parent dari x berwarna hitam, berarti tidak terjadi violation.
   (Tree tidak perlu diperbaiki)
2. Bila parent dan uncle dari x berwarna merah,
   Ubah warna parent dan uncle x menjadi hitam, lalu ubah warna grandparent x menjadi merah.                                                  (Click to Enlarge)
3. Bila parent dari x berwarna merah & uncle dari x berwarna hitam, (external nodes berwarna hitam)
   Maka lakukan Rotasi. Ubah pivot rotasi menjadi hitam dan anak-anaknya menjadi merah.

Single Rotation

Double Rotation

 

Deletion pada Red Black Tree

1. Lakukan deletion seperti pada BST. (Bila yang mau dihapus punya 2 anak carilah successor dari elemen paling besar di kiri atau elemen paling kecil di kanan)
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:

• Ganti node yang mau dihapus dengan anaknya.
• Bila sibling berwarna merah, tukar warna sibling dan parent, lalu lakukan rotasi pada parent

 

 

• Bila sibling berwarna hitam dan keduanya anaknya juga hitam, maka ubah warna sibling menjadi merah

 

• Bila sibling berwarna hitam dan ada anaknya yang berwarna merah, maka lakukan rotasi

 

2-3 Tree

2-3 tree adalah struktur data dimana setiap node yang bukan leaf mempunyai:

• 2 anak dan 1 data,  atau
• 3 anak dan 2 data

Syarat 2-3 Tree:

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

Contoh 2-3 Tree:

Insertion pada 2-3 Tree

1. Data akan dimasukkan ke dalam salah satu leaf (diatur menurut nilainya)
2. Jika leaf tersebut merupakan 2-node, maka masukkan data kesana sehingga menjadi 3-node

   

3. Jika leaf tersebut merupakan 3-node, urutkan ketiga data, push data yang di tengah ke node parent lalu pisahkan 2 data yang tertinggal menjadi 2 buah node baru. (Perbaiki juga parent-nya secara rekursif)

Deletion pada 2-3 Tree

1. Carilah sebuah data pada leaf yang akan menggantikan data yang mau dihapus. Deletion akan selalu terjadi pada leaf.
2. Jika leaf tersebut adalah 3-node, maka hapuslah data tersebut sehingga menjadi 2-node
3. 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
   
   
   
4. Jika leaf tersebut adalah 2-node & parent adalah 2-node,
   – Bila sibling adalah 3-node, ambil satu nilai dari parent lalu push satu nilai dari sibling ke parent
   – Bila sibling adalah 2-node, gabungkan parent dengan sibling.
5. Perbaiki parent secara rekursif bila perlu