Tag Archives: 3

RED BLACK TREE

Red Black Tree merupakan salah satu Balanced Binary Search Tree. Konsepnya hampir sama dengan AVL, namun Red Black Tree menggunakan pewarnaan merah atau hitam pada node dan violation ditentukan dari pewarnaan node tersebut.

Syarat dalam Red Black Tree:

1. Root selalu berwarna hitam.
2. Node berwarna merah tidak bisa memiliki parent atau child berwarna merah.
3. Jumlah node hitam ke node eksternal sama.
4. Apabila insert node baru, node tersebut diberi warna merah.

Operasi dalam Red Black Tree:

1. Searching
   Proses searching pada Red Black Tree sama dengan proses searching Binary Search Tree.
2. Insertion
   • Proses insertion sama dengan BST
   • Node yang di-insert diberi warna merah
   • Pastikan tidak ada violation
   • Bila ada violation gunakan langkah berikut:
     • Color Swap
       
     • Single Rotation
       
     • Double Rotation
       
3. Deletion
   • Proses deletion pada RBT sama dengan deletion pada BST.
   • Anggap node yang ingin dihapus adalah M dan anaknya adalah C.
   • Jika M berwarna merah, maka gantikan M dengan C dan C harus hitam.
   • Jika M berwarna hitam dan C berwarna merah, ganti M dengan C dan ganti warna C menjadi hitam.
   • Jika M dan C berwarna hitam:
     • Ganti M dengan C.
     • Jika sibling berwarna merah, tukar warna sibling dan parent. Lalu lakukan single rotation pada parent.
       
     • Jika sibling berwarna hitam dan kedua anaknya juga berwarna hitam, maka ubah warna sibling menjadi merah.
       
     • Jika sibling berwarna merah dan salah satu anaknya berwarna merah, maka lakukan single rotation atau double rotation.
       

_______________________________________________________________________

2-3 TREE

2-3 Tree bukan merupakan binary tree. 2-3 Tree merupakan struktur data dimana:

1. Setiap node yang memiliki 2 anak akan memiliki 1 data pada node.
2. Setiap node yang memiliki 3 anak akan memiliki 2 data pada node.

Syarat pada 2-3 Tree:

1. Setiap node internal (non leaf) adalah 2-node (1 data dan 2 anak) atau 3-node (2 data dan 3 anak).
2. Data disimpan secara urut:
   • Pada 2-node, anak kiri lebih kecil dari anak kanan.
   • Pada 3-node, anak kiri lebih kecil dari anak kanan dan anak yang di tengah memiliki nilai yang masuk dalam range parents-nya (nilainya di antara parents-nya).
3. Semua leaf berada di level yang sama.

Contoh 2-3 Tree:

Operasi pada 2-3 Tree:

1. Searching
   Konsep searching pada 2-3 Tree sama dengan konsep searching pada BST. Perbedaan hanya pada maksimal jumlah data per node dan maksimal jumlah anak per node.
2. Insertion
   • Konsep pada 2-3 Tree hampir sama dengan BST. Anak kiri lebih kecil dari anak kanan. Data kiri lebih kecil dari data kanan pada suatu node. Maka, apabila data yang di-insert lebih kecil dari node, penelusuran bergerak ke anak kiri menuju ke leaf. Sedangkan apabila data yang di-insert lebih besar dari node, penelusuran bergerak ke anak kanan menuju ke leaf.
   • Jika leaf merupakan 2-node, maka lakukan insert menjadi 3-node.
     
   • Jika leaf merupakan 3-node, push data tengah ke parent dan data dari node tersebut dipisahkan menjadi 2-node. Perbaiki parent secara rekursif.
     
3. Deletion
   • Sama seperti BST, cari sebuah data pada leaf yang akan menggantikan data yang mau dihapus. Deletion akan selalu terjadi pada leaf.
   • Jika leaf berupa 3-node, maka delete node sehingga menjadi 2-node.
   • Jika leaf berupa 2-node:
     • Jika parent berupa 3-node, ambil 1 value dari parent. Jika sibling berupa 3-node, push 1 value dari sibling-nya ke parent (untuk membuat parent kembali menjadi 3-node). Jika sibling berupa 2-node, ubah parent menjadi 2-node dan gabungkan dengan sibling.
     • Jika parent berupa 2-node dan sibling-nya berupa 3-node, maka ambil 1 value dari parent dan push 1 value dari sibling ke parent. Jika sibling berupa 2-node, maka gabungkan parent dengan sibling.
     • Perbaiki parent secara rekursif.
   • Contoh deletion: