AVL

AVL

AVL(Adelson, Velskii, Landis) ditemukan oleh G.M. Adelson-Veleskii dan E.M. Landis, dan nama AVl sendiri digunakan untuk menghargai penemu-penemunya.
AVL merupakan tree balancing pertama yang pernah ada dan merupakan salah satu yang lainnya adalah RBT.
AVL tentunya akan lebih baik untuk digunakan dibandingkan dengan RBT yang akan sangat lama untuk melakukan insert, search maupun delete nya.
AVL sangatlah mirip dengan BST tetapi bedanya AVL bisa dikatakan sebagai BST yang seimbang.


Berikut ini merupakan beberapa konsep AVL:

• Tinggi subtree : Level node terbawah dari subtree  dikurang level root subtree tsb
• Balance Factor : Tinggi subtree kanan dikurang tinggi dari subtree kiri dari suatu node
• Pada AVL, balance factor nya hanya boleh -1,0,1.
• Selebihnya dari itu, maka terjadi violation lalu harus dilakukan rotasi.
•  Tinggi sebuah sub tree kosong itu 0
•  Tinggi sebuah leaf itu 1.
• Tinggi pada tree dapat dihitung dengan cara tinggi terbesar dari children nya+1, jadi missal ada 2 anak yang satu tinggi nya 1, sedangkan yang satu lagi 2. Maka node tersebut memiliki tinggi 2+1=3.

Angka yang merah merupakan balance factor, sedangkan yang hitam merupakan tiiggi subtree.

Dan, pada node yang isi angka 17 terjadi violation karena balance factor nya 2.

Berikut ini merupakan contoh AVL:

Cara-cara rebalance AVL ada 2:

1.       Single rotation: dilakukan bila terjadi violation dimana berbentuk node kiri dengan deepest kiri(left-left) / node kanan dengan deepest node nya kanan (right-right) .

       

2.       Double rotation : dilakukan bila terjadi  violation dimana berbentuk node kiri dengan deepest node nya dikanan (left, right) / node kanan dengan deepest node nya dikiri (right-left).

Operasi-operasi pada AVL:

a.       Insert

a.       Cara insert nya sama dengan insert pada BST.

b.      Setelah data diinsert maka dilakukan trace dari data yang diinsert sampai ke root, dimana balance factor nya harus maksimal 1, jika tidak maka lakukan single rotation / double rotation tergantung situasi, jika sudah lakukan terus menerus sampai root.

b.      Delete

a.       Cara delete sama seperti delete pada BST.

b.      Lakukan trace dari node yang didelete tadi sampai root, jika terjadi violation, maka lakukan single rotation/double rotation , lalu trace lagi sampai root.

2-3 Tree

2-3 Tree

Meruppakan suatu tree dimana internal nodenya merupakan node-2 atau node-3 dan semua leafnya berada pada level yang sama .

Yang kiri merupakan contoh node 2 dimana pada node 2 akan ada 1 data dan mempunyai 2 anak, sedangkan yang kanan merupakan node 3 dimana pada node 3 akan ada 2 data dan mempunyai 3 anak.

Gambar dibawah ini merupakan contoh dari 2-3 Tree:

Satu hal yang paling penting pada 2-3 Tree adalah tree ini harus lah seimbang dalam arti jika ada node 3, maka ia harus punya 3 anak(kecuali root).

Operasi pada 2-3 tree:

1.       Insert

a.       Kalau insert pasti data kita taruh terlebih dahulu di leaf

b.      Kalau data baru tersebut akan diinsert di 2-node maka langsung taruh saja.

c.       Kalau data baru tersebut diinsert di 3-node(2 data dlm 1 kotak) maka push nilai tengah diantara 3 data tersebut ke atas(parentnya) dan nilai kiri dan nilai kanan di split/pisah, begitu seterusnya.

Contoh:

a

   b

Pada gambar a dapat terlihat bahwa node nya sudah ppenuh, oleh karena itu diantara ketiga data tersebut kita push nilai tengah(2) ke parent, karena parent kosong maka ia menjadi root dan 1 serta 3 memisah jadi anak kiri dan anak kanan dari 2.

*Note biasanya digambarkan dengan kotak bukan dengan oval seperti gambar diatas.

2.       Delete

a.       Jika leafnya node-2 :

                                                               i.      Jika parent node-3 : ambil salah satu datanya.

1.       Jika kedua siblingnya node-3 : masukan salah satu data sibling ke parent.

2.       Jika ada sibling node-3 diapit oleh node-2&yg dhps node 2 nya,maka berlaku seperti poin 1.

3.       Jika salah satu sibling node-2 : Satukan data tersebut dengan siblingnya yg node-2

                                                             ii.      Jika parent node-2 :

1.       Jika sibling node-3 : ambil satu data dari parent dan masukan salah satu data sibling ke parent.

2.       Selain sibling node-3 : gabungkan parent dengan sibling

b.      Jika leaf node 3 maka hapus saja datanya.

Contoh delete:

Delete 1

*Dari kiri ke kanan lalu kebawah

RBT(Red Black Tree)

RBT(Red Black Tree)

RBT merupakan salah satu balanced binary tree yang digunakan untuk membuat tree seimbang.
Akan tetapi, RBT merupakan tree yang memberikan kita worst time guarantee(waktu terburuk) untuk melakukan operasi-operasi nya yaitu insert, delete maupun searching, sehingga RBT cocok digunakan untuk mencari tau waktu terburuk dari suatu aplikasi.

Contoh RBT:

Ketentuan dasar RBT yaitu sebagai berikut :

1.       Setiap node memiliki warna baik hitam maupun merah.

2.       Root warnanya selalu hitam.

3.       Dibawah leaf ada external node yang berwarna hitam.

4.       Node merah tidak bisa punya anak node merah, tetapi node hitam bisa punya anak node itam dan node merah.

5.       Jumlah node berwarna hitam dari root ke external node melewati tiap cabang nya  jumlah nya harus sama.

Double black merupakan suatu kondisi dimana node hitam digantikan oleh node hitam.

Operasi pada RBT :

1.       Insert:

a.       Cara insert sama seperti pada BST dan AVL

b.      Node yang baru diinsert selalu berwarna merah.

c.       Jika node yang baru diinsert parentnya hitam maka, tidak apa-apa

d.      Jika node yang baru diinsert parentnya merah maka,terjadi violation:

                                                               i.      Jika uncle dari node baru berwarna hitam maka lakukan rotasi(single/double) ke arah uncle berwarna hitam tersebut dan lalu lakukan recolor menjadi parent dari hasi rotation tadi menjadi hitam dan kedua anaknya menjadi merah.
                                  
                                    dimana pada contoh dimasukkan angka 5, yang menyebabkan terjadi violation.

                                                             ii.      Jika uncle dari node baru berwarna merah, maka lakukan recolor, dimana parent dan uncle dari node baru tersebut ubah warnanya menjadi warna hitam dan grandparent dari node baru tersebut menjadi warna merah.

a

b

Seperti pada contoh dimasukkan angka 4, terjadi violation seperti pada pint 2 insert, dimana seharusnya angka 6 juga menjadi merah akan tetapi dikarenakan angka 6 merupakan root(lihat ketentuan RBT) sehingga root selalu hitam.

2.       Delete:

a.       Cara delete sama seperti pada BST.

b.      Jika sebuah node warna merah dihapus dan anaknya warna hitam, maka ganttin saja node yang dihapus tersebut dengan node hitam tersebut.

c.       Jika sebuah node warna hitam dihapus dan digantikan oleh node warna merah maka, gantiin node yang dihapus dengan node merah tersebut dan ubah warna nya jadi hitam

d.      Jika node hitam dihapus dan diganttin sama node hitam maka masuk kondisi double black.

                                                               i.      Jika sibling db nya warna hitam dan kedua anaknya hitam maka, ubah sibling jadi warna merah dan parentnya jadi warna hitam, klo sebelumnya parentnya warna hitam, maka parentnya masuk ke kondisi db.

                                       Jika x merupakan node merah, maka proses insertion selesai. Akan tetapi jika x merupakan nofe hitam, maka x akan menjadi double black.

                                                             ii.      Jika sibling db warna nya hitam dan anaknya ada yang berwarna merah, maka lihat parentnya:

1.       Jika parentnya warna merah maka lakukan rotasi(single/double) dan nanti ubah warna parent yang setelah di rotasi jadi merah dan kedua anak nya jadi hitam

2.       Jika parentnya warna hitam maka lakukan rotasi kemudian parent dan juga kedua anaknya menjadi warna hitam semuanya.

Jika x merupakan node merah maka setelah dirotasi node y akan menjadi merah 

tetapi jika x merupakan node hitam maka setelah dirotasi node y menjadi warna hitam.

                                                            iii.      Jika sibling db warna merah, maka lakukan rotasi ke arah db nya, lalu parentnya jadi warna hitam dan anak kanannya(yang sebelumnya jadi parent) jadi warna merah, tapi db nya belum hilang sehingga masih harus diselesaikan.

Gambar yang node nya ada kotak nya menandakan double black(db).