Nama : Emilio Joshua Adiputra
NIM : 1901460171
Red Black Tree
Adalah sebuah binary search tree dimana tiap node diberi warna hitam dan merah
dan juga red black tree adalah salah satu cara self balance tree
Aturan Red black tree adalah :
-Setiap node adalah berwarna merah atau hitam
-Akar/Root selalu berwarna hitam- Node yang baru dimasukan itu harus berwarna merah
- Jika node berwarna merah, anaknya harus berwarna hitam
-Node berwarna merah secara berturut-turut tidak diperbolehkan.
Salah Satu Contoh Red Black Tree :
NIL di gambar adalah external node dimana itu tidak ada di tree yang sebenarnya hanya untuk membantu jika ada node baru yang masuk maka NIL yang akan di ganti
1. Insertion
yang di input adalah X : tidak terjadi masalah maka tree masih dalam kondisi "Balance"
Uncle dan parent yang di input adalah X itu berwarnah merah kita dapat mengubah parent dan uncle yang di input menjadi hitam untuk membalancekan kembali
Seperti syarat red black tree dimana tidak boleh merah bertemu merah maka ini tidak berkondisi balance sehingga kita perlu rotasikan
gambar di atas adalah cara untuk membalancekan dengan cara single rotation
Left - Left rotation : Y yaitu parent dari X menjadi parent X dan Z lalu X dan Z menjadi merah dan Y sendiri dari awal nya merah menjadi Hitam lalu C menjadi anak nya Z
Right- Right rotation : Y yaitu parent dari Z menjadi parent X dan Z lalu X dan Z menjadi merah dan Y sendiri dari awal nya merah menjadi Hitam lalu B menjadi anak nya X
Ini adalah cara dengan Double Rotation
Left Right Rotation : Y menjadi parent dari X dan Z lalu B di berikan ke X dan C diberikan ke Z
setelah itu ubah parent yaitu Y menjadi Hitam dan anak nya menjadi merah
Right left Rotation : Y menjadi parent dari X dan Z lalu B di berikan ke X dan C diberikan ke Z
setelah itu ubah parent yaitu Y menjadi Hitam dan anak nya menjadi merah
2. Deletion
Syarat-syarat
-Bila yang mau dihapus punya 2 anak carilah successor dari elemen paling besar di kiri atau elemen paling kecil di kanan tergantung dari cara anda
-Bila node yang mau dihapus berwarna merah, langsung dapat diganti dengan anaknya yang berwarna hitam.
-Bila node yang mau dihapus berwarna hitam & anaknya merah, gantilah dengan anaknya lalu ubah warna anaknya menjadi hitam.
-Bila yang mau di hapus dan anak nya berwarna hitam diperlukan perlakuan khusus:
- Ganti node yang mau dihapus dengan anaknya.
- Bila sibling berwarna merah, tukar warna sibling dan parent, lalu lakukan rotasi seperti berikut
- Bila sibling berwarna hitam dan keduanya anaknya juga hitam, maka cukup mengubah warna sibling tersebut menjadi warna merah
- Bila sibling merah dan ada anaknya yang berwarna merah (salah satu saja), maka lakukan rotasi seperti berikut
2-3 tree BUKAN sebuah Binary Tree
salah satu struktur data dimana node mempunyai anak
jika anak nya 2 maka setiap anak mempunyai 1 data
sedangkan jika anak nya 3 setiap anak mempunyai maksimal 2 data
Aturan 2-3 Tree :
- Setiap non-leaf terdapat 2-node atau 3-node. Sebuah 2-node berisi satu item data dan memiliki dua anak/children (anak kiri dan anak tengah). Sebuah 3-node berisi dua item data dan memiliki 3 anak/children (anak kiri, tengah, dan kanan).
- Semua leaf harus berada dilevel yang sama
- Semua data yang disimpan akan diurutkan kekiri adalah lebih kecil dari root dan kekanan lebih besar dari root
memasukan 45 cukup memasukan saja karena masih memiliki tempat untuk 45 tersebut sehingga tidak ada masalah
jika yang di masukan seperti 75 maka nilai dari 80 90 diperbandingkan dengan 75 lalu nilai tengah nya apa.. di sini adalah 80
lalu 80 naik ke atas dan 75 dan 90 berpisah menjadi node sendiri - sendiri
24 langsung ke atas dan 23 berpisah dengan 25 menjadi node- node sendiri
di atas pun 24 tetap nilai tengah sehingga 24 berpindah ke atas di sebelah 50
lalu kita perlu memisahkan 20 dan 30 menjadi node node sendiri dan tadikan ada 4 node yang berlokasi sebagai anak 20 | 30 maka yang di bagian kiri menjadi milik 20 lalu yang di bagian kanan menajdi milik 30
Deletion 2-3 Tree
-Jika leaf-nya sudah 3-node, maka kita tinggal menghapus saja data tersebut dan menjadikannya
2-node.
-Jika leaf-nya adalah 2-node :
- Jika parent-nya 3-node, maka ambil 1 nilai dari 3-node tersebut. Jika Sibling/Saudaranya adalah 3-node, maka push nilai tersebut dari sibling ke parent untuk membuat parent menjadi 3-node lagi. Jika sibling adalah 2-node, buat parent menjadi 2-node dan gabungkan node dengan sibling-nya.
- Jika parent-nya 2-node, Jika sibling-nya adalah 3-node, maka ambil satu nilai dari parent dan push satu nilai dari sibling ke parent-nya sendiri. Hal lainnya yaitu mengabungkan parent dengan sibling.
23 ingin di hapus lalu karena itu adalah 3 node maka menghapus 23 tidak terjadi masalah
50 ingin di hapus maka kita mencari element terkanan dari node kiri 50 dihapus lalu 40 berpindah ke 40 lalu lokasi 40 sebelum nya di 3 node menjadi kosong
di sini kita perlu menurunkan 30 ke anak nya di bagian paling besar supaya yang tadi nya bertotal 3 node anak menjadi 2 node anak saja sehingga menjadi seperti ini
Tidak ada komentar:
Posting Komentar