AVL Tree

AVL tree adalah sebuah Binary Search Tree yang bisa menyeimbangkan antara tinggibagian kiri dengan tinggi bagian kanan.

Contoh sebuah AVL Tree

Perbedaan tinggi subtree bagian kanan dan kiri adalah kurang dari sama dengan 1.

Contoh yang bukan AVL Tree


Perbedaan tinggi subtree 8 dan 18 lebih dari 1.

AVL Tree sangat berguna karena BST biasa yang bukan AVL Tree, membutuhkan waktu yang cukup lama untuk beroperasi.

Insertion
Proses insertion AVL Tree dan BST cukup mirip, hanya saja setelah diinsert, AVL Tree langsung menyeimbangkan subtree kiri dan kanan.
Contoh X adalah node yang akan diinsert,
  • Case 1 : node terdalam terletak pada subtree kiri dari anak kiri X (left-left)
  • Case 2 : node terdalam terletak pada subtree kanan dari anak kanan X (right-right)
  • Case 3 : node terdalam terletak pada subtree kanan dari anak kiri X (right-left)
  • Case 4 : node terdalam terletak pada subtree kiri dari anak kanan X (left-right
Case tersebut akan selesai menggunakan single rotation untuk case 1 dan 2, gunakan double rotation untuk case 3 dan 4.

Contoh left rotation
AVL Tree Left Rotation

Source:
https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

Comments

Post a Comment

Popular posts from this blog

Hashing table & Binary Tree

Image
Hashing Table Hashing adalah sebuah cara untuk mengetahui objek secara spesifik dari kumpulan objek yg mirip. Sedangkan Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Operasi pada hash table: insert: diberikan sebuah key dan nilai, insert nilai dalam tabel find: diberikan sebuah key, temukan nilai yang berhubungan dengan key remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu Contoh deklarasi hash table dalam coding: HASHTBL *hashtbl_create(hash_size size, hash_size (*hashfunc)(const char *)) { HASHTBL *hashtbl; if(!(hashtbl=malloc(sizeof(HASHTBL)))) return NULL; free(hashtbl); return NULL; } hashtbl->size=size; if(hashfunc) hashtbl->hashfunc=hash
Read more

Laporan Akhir Mata Kuliah Human and Computer Interaction Aplikasi Predical

Image
LAPORAN AKHIR MATA KULIAH HUMAN AND COMPUTER INTERACTION APLIKASI PREDICAL   Disusun oleh Elbert Adiwijanto 2301881171 Georgius Andrian Halim 2301854315 Stanley Jonathan 2301893820 1. Pendahuluan 1.1. Latar Belakang Permasalahan utama yang mendorong kami untuk mendesain aplikasi ini berawal dari jumlah kasus misdiagnosis penyakit jantung dan angka kejadian penyakit jantung yang semakin meningkat. Berdasarkan hasil observasi kami, Organisasi Kesehatan Dunia (WHO) menyatakan bahwa terdapat lebih dari 17.9 juta orang di seluruh dunia yang meninggal setiap tahunnya, dimana 32% kematian di dunia diakibatkan oleh penyakit jantung dan pembuluh darah. Lebih lanjut, berdasarkan salah satu contoh kasus misdiagnosis di Indonesia, di mana terdapat seorang gadis yang mengalami misdiagnosis antara penyakit flu dengan penyakit jantung, kasus ini menguatkan fakta bahwa penyakit jantung ini bisa diterima dari yang muda hingga yang tua dan juga ternyata dokter ma
Read more

FINAL SUMMARY

Image
LINKED LIST 1. Circular Single Linked List Di circular single linked list, node terakhir (tail) berisikan sebuah pointer yang terhubung ke node pertama (head), sehingga membentuk sebuah sirkuit, yang berarti tidak ada awal maupun akhir dan tidak ada NULL setelah node manapun, karena seperti contoh gambar dibawah, setelah node 3 adalah node 1. Gambar berikut adalah contoh dari circular single linked list: 2. Doubly Linked List Berbeda dengan circular single linked list, doubly linked list ini tidak membentuk sebuah sirkuit. Di setiap node ada sebuah pointer yang menunjuk ke node sebelum dan setelahnya. Dalam doubly linked list ini, setiap node berisikan 3 bagian: node data, pointer ke node berikutnya, dan pointer ke node sebelumnya. Gambar berikut adalah contoh dari doubly linked list: 3. Circular Doubly Linked List Sesuai dengan namanya, circular doubly linked list merupakan gabungan dari circular single linked list dan
Read more