Red Black Tree / Gnarley Tree

Red-Black Tree / Gnarley Tree adalah salah satu jenis "balanced tree" selain AVL tree, yaitu tree yang memiliki keseimbangan antara sisi left child dan right child. Sesuai namanya, Red-black tree adalah tree dengan node / vertex dengan warna merah atau hitam. Setiap node memiliki child kosong berwarna hitam apabila tidak ada "real child".

Rules:
Saat membuat red-black tree, root adalah berwarna hitam
Saat menambah child, vertex berwarna merah
Vertex merah tidak dapat memiliki child/parent yang berwarna merah juga
Vertex hitam boleh memiliki child/parent yang berwarna hitam atau merah.

Pada saat melakukan penambahan node, apabila parent dan "uncle" dari node baru berwarna merah, parent dan "uncle" berubah menjadi hitam, lalu "kakek" dari node tersebut menjadi warna merah apabila bukan root

Pada kasus yang sama apabila parent dari node baru berwarna merah dan "uncle" dari node baru berwarna hitam, maka dilakukan rotasi ke arah "uncle" lalu grand-parent yang sebelum dirotasi berubah warna menjadi merah

Contoh:
60, 30, 90, 15, 48, 106, 74, 13, 1, 16, 216, 99

Insert 60

Root berwarna merah, maka warna diubah menjadi hitam.

Insert 30, 90 , tidak membuat root maka warna tetap merah

Insert 15

Vertex 15 dengan parent (30) berwarna merah menyalahi aturan dimana tidak boleh ada vertex merah yang memiliki anak dan atau parent yang berwarna merah. Dalam kasus ini, "uncle" (90) berwarna merah juga, maka hanya dilakukan pengubahan warna pada parent (30) dan "uncle" (90), lalu mengubah warna pada grand-parent (60).

 Grand-parent (60) adalah root, maka warna berubah lagi menjadi hitam kembali.

Insert 48, 106, 74.

Insert 13

Vertex 13 dengan parent (15) berwarna merah menyalahi aturan dimana tidak boleh ada vertex merah yang memiliki anak dan atau parent yang berwarna merah. Dalam kasus ini, "uncle" (48) berwarna merah juga, maka hanya dilakukan pengubahan warna pada parent (15) dan "uncle" (48), lalu mengubah warna pada grand-parent (30). Tidak seperti langkah tadi, grand-parent (30) tetap berwarna merah karena bukan merupakan root.

Insert 1

 Vertex 1 dan parent (13) menyalahi aturan karena berwarna merah. "uncle" dari vertex 1 adalah kosong yang berarti berwarna hitam. Dalam kasus ini, vertex harus diputar ke arah warna hitam, warna grand-parent lama (15) menjadi merah, dan parent (13) menjadi hitam.

Insert 16, "uncle" (1) dan parent (15) menjadi merah, dan grand-parent (13) menjadi merah.

Grand-parent (13) dan great-grand-parent (30) sama sama berwarna merah, menyalahi aturan dan "uncle" dari vertex 13 (90) berwarna hitam, maka dilakukan rotasi ke arah 90, grand-parent dari 13 (60) menjadi merah, dan parent dari 13 (30) menjadi hitam.

Insert 216, "uncle" (74) dan parent (106) berubah menjadi hitam, grand-parent (90) menjadi merah dan menyalahi aturan dengan vertex 60...

"Uncle" dari vertex 90 (13) dan parent dari vertex 90 (60) sama sama berwarna merah, maka hanya dilakukan perubahan warna menjadi merah. Grand-parent dari 90 (30) berubah warna menjadi merah namun karena vertex 30 adalah root, warna tetap hitam.

Insert 99

---

Images : credits to skyconnectiva.com

skyconnectiva.com

binus.ac.id

Balanced tree ( AVL Tree )

Balanced tree adalah tree dengan berat / selisih level child kiri dan kanan tidak lebih dari 1.

Dalam binary search tree, pencarian dimulai dari root sampai ke leaf
apabila tree yang dibuat adalah skewed tree, pencarian akan sangat panjang dan tidak efisien sehingga perlu diseimbangkan supaya dapat mencapai jarak dari root hingga ke leaf paling jauh dapat diminimalkan ( height dari tree )

contoh:
Memasukkan data : 50, 25, 48, 28, 38, 32, 35

cr : skyconnectiva.com

tinggi tree : 7

untuk meminimalkan tinggi dari tree, dibutuhkan sebuah metode. Salah satunya metode AVL.

Jika kita memasukkan data yang sama ( 50, 25, 48, 28, 38, 32, 35 )
Untuk step 50 dan 25 masih sama, namun saat memasukkan angka 48, child kiri lebih banyak dari child kanan sehingga ada yang harus dipindahkan

Hasil akhir:

tinggi tree = 4
dalam metode AVL, ada 4 macam pemindahan node/verteks dari tree.
1 & 2 : Single rotation apabila orientasi child sama sama ke kiri / kanan.

[input = 42.16.3] tree berat ke kiri, rotation ke kanan

[input = 3,24,106] tree berat ke kanan, rotation ke kiri

3 & 4 : Double rotation apabila orientasi child berbeda dengan orientasi child ke-2 dari child pertama.

[input = 85,34,51] tree akan merotasi 51 dengan 34 terlebih dahulu

[input = 256,512,384] tree akan merotasi 384 dan 512 terlebih dahulu

perpindahan node/verteks tidak selalu pada angka yang baru dimasukkan, tergantung saat selisih level kedua child dari sebuah verteks adalah lebih dari 1. Cara menghitungnya adalah level 1 untuk leaf, level leaf untuk parent adalah +1 dan apabila verteks mempunyai 2 child dengan level 3 dan 4, verteks tersebut adalah level 4+1 ( = 5)

Contoh : memasukkan angka 1 hingga 12

analisis:
verteks input : 12
level verteks 11 = 2 | child : 0 dan 1 ( 12 ) , Δ = 1
level verteks 10 = 3 | child : 2 ( 11 ) dan 1 ( 9 ) , Δ = 1
level verteks 8 = 4 | child : 2 ( 6 ) dan 3 ( 10 ) , Δ = 1
level verteks 4 = 5 | child : 2 ( 2 ) dan 4 ( 8 ) , Δ = 2
*Δ = selisih

permasalahan terjadi pada verteks 4 jadi, penyelesaian adalah single rotation ke kiri dari verteks 4 ke kanan ( 4, 8, 10)

karena 8 tidak bisa mempunyai lebih dari 2 child ( binary tree ), maka child kiri dari 8 adalah 4, tree 6(5,7) menjadi child 4

Kesimpulan : AVL Tree dapat membuat tinggi tree menjadi lebih rendah dan kondisi tree lebih seimbang sehingga pencarian verteks/node lebih efisien.

P.S. : Baru bisa dikerjain karena laptop abis diservice
credits : images generated by apps from skyconnectiva.com

---

skyconnectiva.com
binus.ac.id