AVL Tree

AVL Tree adalah subtype dari BST yang dapat menyeimbangkan dirinya sendiri di mana perbedaan antara ketinggian subtree kiri dan kanan tidak boleh lebih dari satu untuk semua node.

AVL Insertion Process
Hampir sama dengan BST, setelah itu memnyeimbangkan AVL Tree dengan left atau right rotation.

  • Jika ada ketidakseimbangan pada anak kiri subtree kanan, maka lakukan left-right rotation.
  • Jika ada ketidakseimbangan pada anak kiri subtree kiri, maka lakukan right rotation.
  • Jika ada ketidakseimbangan pada anak kanan subtree kanan, maka lakukan left rotation.
  • Jika ada ketidakseimbangan pada anak kanan subtree kiri, maka lakukan right-left rotation.
AVL Tree memeriksa ketinggian subtree kiri dan kanan dan memastikan bahwa perbedaannya tidak lebih dari 1. Perbedaan ini disebut Balance Factor.

AVL Deletion Process
Ada 2 kasus yang biasanya terjadi saat operasi delete, yaitu :
  1. Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
  2. Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan BST dengan perbedaan tinggal maksimal 1.
anggap T adalah node yang harus diseimbangkan kembali
  • Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
  • Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
  • Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
  • Kasus 4 : node terdalam terletak pada subtree kiri da
    ri anak kanan T (left-right)


AVL Tree Rotations
di AVL Tree, setelah melakukan setiap operasi seperti insertion dan deletion, kita perlu memeriksa keseimbangan setiap simpul di Tree. Jika setiap node memenuhi kondisi faktor keseimbangan maka kita menyimpulkan operasi jika tidak kita harus membuatnya seimbang. Kami menggunakan operasi rotasi untuk membuat pohon seimbang setiap kali pohon menjadi tidak seimbang karena operasi apa pun.


Operasi rotasi digunakan untuk membuat pohon seimbang. Ada empat rotasi dan diklasifikasikan menjadi dua jenis:

Rotasi Kiri Tunggal (Rotasi LL)
Dalam Rotasi LL setiap node bergerak satu posisi ke kiri dari posisi saat ini.







Rotasi Kanan Tunggal (Rotasi RR)
Dalam RR Rotation setiap node bergerak satu posisi ke kanan dari posisi saat ini.







Rotasi Kanan Kiri (Rotasi LR)
Rotasi LR adalah kombinasi dari rotasi kiri tunggal diikuti oleh rotasi kanan tunggal. Dalam LR Rotation, pertama setiap node bergerak satu posisi ke kiri lalu satu posisi ke kanan dari posisi saat ini.

Rotasi Kiri Kanan (Rotasi RL)
Rotasi RL adalah kombinasi dari rotasi kanan tunggal diikuti oleh rotasi kiri tunggal. Dalam Rotasi RL, pertama setiap node bergerak satu posisi ke kanan lalu satu posisi ke kiri dari posisi saat ini.

Sumber :

Comments

Post a Comment

Popular posts from this blog

Hashing Table & Binary Tree

Image
Kemarin kita sudah membahas mengenai Stack & Queue. Hari ini saya akan membahas mengenai hashing table dan binary tree. Binary Tree adalah data struktur berpohon di mana setiap simpul memiliki paling banyak 2 anak, yang disebut kiri dan kanan. Binary tree diimplementasikan terutama menggunakan link. Sebuah Tree diwakili oleh pointer ke simpul paling atas di Tree. Jika Tree tersebut kosong, maka nilai sebuah Root kosong. Binary Tree terdapat beberapa node seperti : Data Pointer ke anak kiri Pointer ke anak kanan Binary Tree dapat dilalui dengan 2 cara. Yang pertama adalah Depth First Traversal dan yang kedua adalah Breadth First Traversal. Depth First Traversal terdiri dari : Inorder (Kiri-Root-Kanan) Preorder (Root-Kiri-Kanan)  Postorder (Kiri-Kanan-Root). Breadth First Traversal terdiri dari : Level order Traversal. Properti dari Binary Tree : Angka maksimum node ada di level '1' = 2 1-1 . Angka maksimum node adalah = 2 h + 1 - 1. h adalah ...
Read more

Linked List

Image
Linked list II Halo, pada hari ini, saya aka meringkas materi mengenai Linked List II yang terdiri dari : Single Linked List Circular Double Linked List Double Linked List Circular Linked List adalah koleksi data item yang tersusun dalam sebuah barisan secara linear, dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat Linked List tersebut. Single Linked List adalah sebuah Linked List yang menggunakan sebuah variable pointer saja untuk menyimpan banyak data dengan metode Linked List, suatu daftar isi yang saling berhubungan. Contoh : Pada gambar diatas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpang data disebut node, setiap node memiliki pointer yang menunjuk ke node berikutnya sehingga membentuk suatu untaian yang disebut single Linked List. Bila dalam single Linked List pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saj...
Read more

Binary Search Tree

Image
Binary Search Tree Kemarin kita sudah membahas mengenai Hash Table, Hashing dan Binary Tree. Pada hari ini, saya akan menjelaskan tentang Binary Search Tree. Binary Search Tree adalahadalah Binary Tree dengan : Subtree kiri dari sebuah node hanya berisi node dengan kunci kurang dari kunci node. Subtree kanan dari sebuah node hanya berisi node dengan kunci lebih besar dari kunci node. Subtree kiri dan kanan masing-masing juga harus berupa pohon pencarian biner. Properti di atas dariBST menyediakan pemesanan antar tombol sehingga operasi seperti pencarian, minimum dan maksimum dapat dilakukan dengan cepat. Jika tidak ada pemesanan, maka BST mungkin harus membandingkan setiap kunci untuk mencari kunci yang diberikan. BST mempunya Basic Operations yang terdiri dari : Search - untuk mencari elemen dalam tree Insert - untuk memasukkan data ke dalam tree Pre-order Traversal - melintasi tree dengan cara pre-order In-order Traversal - melintasi tree dengan cara in...
Read more