♣ AVL TREE
AVL Tree adalah suatu jenis modifikasi BST. Tree ini dinamai sesuai dengan penemunya yaitu Adelson, Velsky, dan Landis. AVL Tree juga dikenal sebagai self-balancing tree karena jenis tree ini dapat mengoptimasi dirinya sendiri dengan melakukan operasi tertentu.
Tujuan dari self -balancing tree ini adalah mempercepat operasi yang ada di BST pada umumnya yaitu insert, search, dan delete. Dengan AVL maka average case dan worst case dari BST dapat diperbaiki menjadi O (log n).
• Hal penting yang perlu dipelajari di dalam konsep AVL Tree adalah :
1. Height
2. Balance Factor
3. Rotation Pattern
1. Height
Konsep height pada dasarnya sama didalam semua konsep tree. Height root biasa dimulai dengan 0. Height adalah jarak suatu Node dengan Leaf Node terjauh dari Node tersebut.
2. Balance Factor
Pada konsep AVL kita mengenal konsep baru yaitu balance factor. Balance factor adalah selisih tinggi antara subtree kiri dan kanan. Balance factor ini kita gunakan untuk menentukan apakah tree kita sudah seimbang atau belum. Utk memperoleh tree yang stabil balance factor dari semua Node yang ada didalam tree kita hanya boleh berkisar -1, 0, atau 1.
Balance factor yang bernilai -1 = Left subtree lebih tinggi dari right subtree
Balance factor yang bernilai 0 = Tinggi left subtree sama dengan tinggi right sub tree
Balance factor yang bernilai 1 = Right subtree lebih tinggi dari left subtree
Balance Factor = Height Left Subtree - Height Right Subtree
3. Rotation Pattern
Masih berkaitan dengan balance factor. Lalu apa jadinya jika di dalam tree kita terdapat suatu Node yang nilai balance factornya tidak sesuai dengan ketentuan. Jika kondisi seperti itu ditemui maka kita harus melakukan rotation pada tree kita. Konsep rotation adalah kunci dari AVL Tree.
Jenis rotation pada AVL ada 4 macam yaitu :
1. LL Rotation
2. RR Rotation
3. LR Rotation
4. RL Rotation
LL dan RR Rotation adalah rotation dasar sedangkan LR dan RL Rotation adalah rotation yang merupakan rotation gabungan.
Operation pada AVL Tree
Operasi pada AVL Tree pada dasarnya sama seperti BST, kita memiliki operasi Searching, Insert, dan Delete.
1. Searching : Utk proses searching cara yang kita gunakan sama persis seperti operasi searching pada BST.
2. Insert : Pada proses searching kita akan melakukan hal yang sama seperti insert pada BST. Kita tetap akan meletakkan Node baru pada posis Leaf. Setelah diletakkan pada posisi leaf kita akan meninjau kembali balance factor dari tree kita karena pada sebagaian besar kasus adanya proses insert akan membuat tree menjadi tidak balance.
3. Delete : Serupa dengan Insert, pada proses Delete kita akan menerapkan delete seperti BST terlebih dahulu. Sesudah hal ini dilakukan maka kita akan melanjutkan prses dengan meninjau kembali balance factor dari tree kita karena adanya proses delete dapat menyebabkan tree kita menjadi tidak balance.
Code utk AVL Tree :
♣ B-Tree
B-Tree adalah bentuk spesial dari M-way Tree. Pada B-Tree kita memiliki keunikan dimana 1 Node dapat menampung paling banyak m-1 key (m = berapa way tree yang kita punya, contoh 4 way tree maka m = 4). Dengan penerapan B-Tree kita dapat meminimalisir tinggi dari tree kita sehingga operasi dapat berjalan lebih cepat.
B-Tree memiliki beberapa aturan yaitu :
1. Setiap Node di B-Tree memiliki maksimum m anak
2. Setiap Node di B-Tree kecuali root dan leaf Node harus mempunyai minimal m/2 anak (ceiling)
3. Root Node memiliki minimal 2 anak
4. Semua leaf Node berada di level yang sama
Operasi pada B-Tree
1. Searching
Proses searching dilakukan sama seperti BST hanya saja pada B-Tree karena setiap Node dapat memiliki lebih dari 1 key kita harus mengecek isi Node tersebut.
2. Insert
Insert dilakukan sama seperti BST, yaitu pada leaf node. Jika leaf Node yang belum terpenuhi maka kita harus mengisi leaf Node tersebut terlebih dahulu. Namun, jika leaf Node sudah penuh maka yang harus kita lakukan adalah menempatkan Node baru pada posisinya, lalu membagi keseluruhan Node menjadi 2 bagian dan mendorong elemen ke parent Node.
3. Delete
Pada proses delete kita mempunyai 2 kasus yaitu kasus leaf Node dan internal Node. Proses yang akan kita lakukan adalah :
1. Mencari elemen sesuai dengan key value
2. Jika Node berisi > m/2 kita akan delete
3. Jika tidak maka kita akan mengambil elemen sibling, jika sibling kiri mempunyai elemen lebih dari m/2 maka kita push elemen terbesar ke parent Node. Jika tidak maka kita lihat sibling kiri, jika sibling kiri mempunyai jumlah yang sesuai ketentuan maka ambil elemen terkecil.
4. Jika sibling tidak mempunyai elemen yang mencukupi maka kita akan membuat leaf Node baru dengan kombinasi elemen dari parent Node.
♠ Red-Black Tree
Red-Black Tree atau yang disingkat RBT pada dasarnya juga menerapkan prinsip BST. Tujuan RBT sama dengan AVL yaitu mengoptimasi operasi pada BST. RBT juga dikenal sebagai Roughly Balance Tree.
• Perbedaan antara RBT dan AVL antara lain :
1. RBT hanya memerlukan 2 rotasi agar tree menjadi balance sedangkan pada AVL rotasi dapat terjadi beberapa kali.
2. RBT memanfaatkan pewarnaan pada Node sedangkan AVL menggunakan balance factor.
3. Insertion dan Deletion lebih cepat di RBT sedangkan searching lebih cepat di AVL. Hal ini dapat terjadi karena pada AVL tinggi dari tree tidaklah terlalu tinggi.
• Aturan di RBT antara lain :
1. Root Node mempunyai warna hitam
2. Semua leaf node yang merupakan null berwarna hitam
3. Jika parent berwarna merah maka child harus hitam. Menghindari red-red violation
• Aturan pada operasi Insertion di RBT :
1. Jika tree kosong maka buat new node dan beri warna hitam.
2. Jika tree tidak kosong maka buat new node dan jadikan warnanya menjadi merah. New node ini diletakkan di ujung atau leaf.
3. Jika parent dari new node berwarna hitam maka tidak diperlukan operasi lanjutan.
4. Jika parent dari new node berwarna merah maka kita perlu melakukan operasi tambahan :
- Jika uncle dari new node adalah hitam / null maka kita perlu melakukan rotasi dan recolor
- Jika uncle dari new node adalah merah maka kita hanya perlu melakukan recolor
• Aturan pada operasi Deletion di RBT :
1. Jika node yang ingin di hapus adalah leaf node dan berwarna merah maka langsung hapus node tersebut.
2. Jika root merupakan Double Black (DB), maka hapus DB.
3. Jika sibling dari DB berwarna hitam dan anaknya berwarna hitam semua maka kita hanya perlu memberikan black ke parent dan merubah warna sibling menjadi merah.
- Jika parent berwarna merah maka black kita terima dan ubah warna parent menjadi hitam
- Jika parent berwarna hitam maka black tetap kita terima dan ubah parent menjadi DB + lakukan operasi dengan mengevaluasi kondisi.
4. Jika sibling dari DB berwarna merah maka kita tukar warna antara parent dan sibling, rotasi parent kearah DB. Jika masih ada masalah kita evaluasi lagi.
5. Jika sibling dari DB berwarna hitam dan anak paling jauh dari sibling DB adalah merah maka kita tukar warna sibling dengan anak dari sibling lalu kita lakukan rotasi kearah yang berlawanan dengan DB.
6. Jika sibling dari DB berwarna hitam dan anak paling jauh dari sibling berwarna DB adalah hitam sedangkan anak sibling yang dekat adalah merah maka kita tukar warna antara parent dan sibling. Lalu lakukan rotasi kearah DB dan rubah warna anak sibling yang sebelumnya berwarna merah menjadi hitam.
Contoh kasus :
AVL Tree adalah suatu jenis modifikasi BST. Tree ini dinamai sesuai dengan penemunya yaitu Adelson, Velsky, dan Landis. AVL Tree juga dikenal sebagai self-balancing tree karena jenis tree ini dapat mengoptimasi dirinya sendiri dengan melakukan operasi tertentu.
Tujuan dari self -balancing tree ini adalah mempercepat operasi yang ada di BST pada umumnya yaitu insert, search, dan delete. Dengan AVL maka average case dan worst case dari BST dapat diperbaiki menjadi O (log n).
• Hal penting yang perlu dipelajari di dalam konsep AVL Tree adalah :
1. Height
2. Balance Factor
3. Rotation Pattern
1. Height
Konsep height pada dasarnya sama didalam semua konsep tree. Height root biasa dimulai dengan 0. Height adalah jarak suatu Node dengan Leaf Node terjauh dari Node tersebut.
2. Balance Factor
Pada konsep AVL kita mengenal konsep baru yaitu balance factor. Balance factor adalah selisih tinggi antara subtree kiri dan kanan. Balance factor ini kita gunakan untuk menentukan apakah tree kita sudah seimbang atau belum. Utk memperoleh tree yang stabil balance factor dari semua Node yang ada didalam tree kita hanya boleh berkisar -1, 0, atau 1.
Balance factor yang bernilai -1 = Left subtree lebih tinggi dari right subtree
Balance factor yang bernilai 0 = Tinggi left subtree sama dengan tinggi right sub tree
Balance factor yang bernilai 1 = Right subtree lebih tinggi dari left subtree
Balance Factor = Height Left Subtree - Height Right Subtree
Masih berkaitan dengan balance factor. Lalu apa jadinya jika di dalam tree kita terdapat suatu Node yang nilai balance factornya tidak sesuai dengan ketentuan. Jika kondisi seperti itu ditemui maka kita harus melakukan rotation pada tree kita. Konsep rotation adalah kunci dari AVL Tree.
Jenis rotation pada AVL ada 4 macam yaitu :
1. LL Rotation
3. LR Rotation
4. RL Rotation
LL dan RR Rotation adalah rotation dasar sedangkan LR dan RL Rotation adalah rotation yang merupakan rotation gabungan.
Operation pada AVL Tree
Operasi pada AVL Tree pada dasarnya sama seperti BST, kita memiliki operasi Searching, Insert, dan Delete.
1. Searching : Utk proses searching cara yang kita gunakan sama persis seperti operasi searching pada BST.
2. Insert : Pada proses searching kita akan melakukan hal yang sama seperti insert pada BST. Kita tetap akan meletakkan Node baru pada posis Leaf. Setelah diletakkan pada posisi leaf kita akan meninjau kembali balance factor dari tree kita karena pada sebagaian besar kasus adanya proses insert akan membuat tree menjadi tidak balance.
3. Delete : Serupa dengan Insert, pada proses Delete kita akan menerapkan delete seperti BST terlebih dahulu. Sesudah hal ini dilakukan maka kita akan melanjutkan prses dengan meninjau kembali balance factor dari tree kita karena adanya proses delete dapat menyebabkan tree kita menjadi tidak balance.
Code utk AVL Tree :
♣ B-Tree
B-Tree adalah bentuk spesial dari M-way Tree. Pada B-Tree kita memiliki keunikan dimana 1 Node dapat menampung paling banyak m-1 key (m = berapa way tree yang kita punya, contoh 4 way tree maka m = 4). Dengan penerapan B-Tree kita dapat meminimalisir tinggi dari tree kita sehingga operasi dapat berjalan lebih cepat.
B-Tree memiliki beberapa aturan yaitu :
1. Setiap Node di B-Tree memiliki maksimum m anak
2. Setiap Node di B-Tree kecuali root dan leaf Node harus mempunyai minimal m/2 anak (ceiling)
3. Root Node memiliki minimal 2 anak
4. Semua leaf Node berada di level yang sama
Operasi pada B-Tree
1. Searching
Proses searching dilakukan sama seperti BST hanya saja pada B-Tree karena setiap Node dapat memiliki lebih dari 1 key kita harus mengecek isi Node tersebut.
2. Insert
Insert dilakukan sama seperti BST, yaitu pada leaf node. Jika leaf Node yang belum terpenuhi maka kita harus mengisi leaf Node tersebut terlebih dahulu. Namun, jika leaf Node sudah penuh maka yang harus kita lakukan adalah menempatkan Node baru pada posisinya, lalu membagi keseluruhan Node menjadi 2 bagian dan mendorong elemen ke parent Node.
3. Delete
Pada proses delete kita mempunyai 2 kasus yaitu kasus leaf Node dan internal Node. Proses yang akan kita lakukan adalah :
1. Mencari elemen sesuai dengan key value
2. Jika Node berisi > m/2 kita akan delete
3. Jika tidak maka kita akan mengambil elemen sibling, jika sibling kiri mempunyai elemen lebih dari m/2 maka kita push elemen terbesar ke parent Node. Jika tidak maka kita lihat sibling kiri, jika sibling kiri mempunyai jumlah yang sesuai ketentuan maka ambil elemen terkecil.
4. Jika sibling tidak mempunyai elemen yang mencukupi maka kita akan membuat leaf Node baru dengan kombinasi elemen dari parent Node.
♠ Red-Black Tree
Red-Black Tree atau yang disingkat RBT pada dasarnya juga menerapkan prinsip BST. Tujuan RBT sama dengan AVL yaitu mengoptimasi operasi pada BST. RBT juga dikenal sebagai Roughly Balance Tree.
• Perbedaan antara RBT dan AVL antara lain :
1. RBT hanya memerlukan 2 rotasi agar tree menjadi balance sedangkan pada AVL rotasi dapat terjadi beberapa kali.
2. RBT memanfaatkan pewarnaan pada Node sedangkan AVL menggunakan balance factor.
3. Insertion dan Deletion lebih cepat di RBT sedangkan searching lebih cepat di AVL. Hal ini dapat terjadi karena pada AVL tinggi dari tree tidaklah terlalu tinggi.
• Aturan di RBT antara lain :
1. Root Node mempunyai warna hitam
2. Semua leaf node yang merupakan null berwarna hitam
3. Jika parent berwarna merah maka child harus hitam. Menghindari red-red violation
• Aturan pada operasi Insertion di RBT :
1. Jika tree kosong maka buat new node dan beri warna hitam.
2. Jika tree tidak kosong maka buat new node dan jadikan warnanya menjadi merah. New node ini diletakkan di ujung atau leaf.
3. Jika parent dari new node berwarna hitam maka tidak diperlukan operasi lanjutan.
4. Jika parent dari new node berwarna merah maka kita perlu melakukan operasi tambahan :
- Jika uncle dari new node adalah hitam / null maka kita perlu melakukan rotasi dan recolor
- Jika uncle dari new node adalah merah maka kita hanya perlu melakukan recolor
• Aturan pada operasi Deletion di RBT :
1. Jika node yang ingin di hapus adalah leaf node dan berwarna merah maka langsung hapus node tersebut.
2. Jika root merupakan Double Black (DB), maka hapus DB.
3. Jika sibling dari DB berwarna hitam dan anaknya berwarna hitam semua maka kita hanya perlu memberikan black ke parent dan merubah warna sibling menjadi merah.
- Jika parent berwarna merah maka black kita terima dan ubah warna parent menjadi hitam
- Jika parent berwarna hitam maka black tetap kita terima dan ubah parent menjadi DB + lakukan operasi dengan mengevaluasi kondisi.
4. Jika sibling dari DB berwarna merah maka kita tukar warna antara parent dan sibling, rotasi parent kearah DB. Jika masih ada masalah kita evaluasi lagi.
5. Jika sibling dari DB berwarna hitam dan anak paling jauh dari sibling DB adalah merah maka kita tukar warna sibling dengan anak dari sibling lalu kita lakukan rotasi kearah yang berlawanan dengan DB.
6. Jika sibling dari DB berwarna hitam dan anak paling jauh dari sibling berwarna DB adalah hitam sedangkan anak sibling yang dekat adalah merah maka kita tukar warna antara parent dan sibling. Lalu lakukan rotasi kearah DB dan rubah warna anak sibling yang sebelumnya berwarna merah menjadi hitam.
Contoh kasus :
Contoh kasus 2 :
Comments
Post a Comment