Binus Preview

Data Structure (Conclusion)

Red Black Tree (RBT)

RBT memiliki ‘External Node‘ di setiap leafnya yang disebut ‘Dummy Children‘.
Jika sebuah node di masukkan, maka node tersebut akan di masukkan ke salah satu external node RBT.

External node tidak memiliki value tertentu, hanya menjadi bagian dalam penghitungan algoritma didalam program saja.

Ciri – ciri Red Black Tree :

1. Setiap node mempunyai warna, yaitu merah dan hitam
2. Root selalu berwarna hitam
3. Semua external node berwarna hitam
4. Jika ada node yang berwarna merah, maka kedua anaknya berwarna hitam

Ciri ke-4 juga berarti :

• Tidak ada node merah yang mempunyai parent merah
• Setiap jalan dari root sampai external node, mempunyai jumlah warna hitam yang sama rata

RBT Opertaion : Insertion

• Node baru selalu berwarna merah
• Jika parentnya warna hitam, tidak ada pelanggaran
• Jika parentnya warna merah, maka ada pelanggaran

  Hanya perlu melakukan re-coloring.

 Dilakukan Single Rotation

 Dilakukan Double Rotation

RBT Operation : Deletion

 Karena sibling dari double black node adalah merah, maka perlu dilakukan single rotation

Karena sibling dari double black node adalah hitam, maka perlu dilakukan re-coloring

 Karena sibling dari double black node adalah hitam dan keponakannya merah, maka perlu dilakukan double rotation

2 – 3 Tree (Bukan Binary Tree)

2 – 3 Tree adalah sebuah data struktur dimana setiap node dengan anaknya mempunyai antara 2 anak sampai 3 anak.
Jika node mempunyai 1 data, maka node memiliki 2 anak
Jika node mempunyai 2 data, maka node memiliki 3 anak
Setiap leaf mempunyai level yang sama rata

2 – 3 Tree Operation : Insertion

Insert 45 (Tidak mengubah)

*GAMBAR ATAS DENGAN BAWAH TIDAK BERHUBUNGAN

Insert 75 (Berada di antara node 70 dan node 80, 90)

Karena 80 berada di tengah, maka 80 naik

80 naik, 75 dan 90 membuat node masing-masing

2 – 3 Tree Operation : Deletion

Delete 23 (Tidak ada yang berubah)

Delete 50. 40 menggantikan 50 (terbesar paling dekat dengan 50)

30 turun mengisi data kosong disebelah 25

Hasil akhir setelah Delete 50