Rangkuman Sebelum UAS

Nama : Vanessa Ratana Yoe
NIM : 2301869424
Kelas : CB01-CL
Dosen : Henry Chong (4460) & Ferdinand Ariandy Luwinda (4522)

AVL TREE

AVL Tree adalah salah satu jenis Binary Search Tree dimana antara subtree kiri dengan subtree kanan memiliki perbedaan tinggi / level maksimalnya 1. AVL Tree digunakan untuk menyeimbangkan Binary Search Tree sehingga memungkinkan untuk mempersingkat waktu pencarian.A

INSERTION

Pada dasarnya insert di AVL sama dengan insert di BST, setelah node dimasukkan apabila tree belum seimbang maka akan diseimbangkan. Terdapat 4 kasus, yaitu :
  • node terdalam ada di subtree kiri dari anak kiri n (left-left)
  • node terdalam ada di subtree kanan dari anak kanan n (right-right)
  • node terdalam ada di subtree kanan dari anak kiri n (right-left)
  • node terdalam ada di subtree kiri dari anak kanan n (left-right)

* n adalah node yang harus diseimbangkan

Proses penyeimbangan dapat dilakukan dengan Single Rotation dan Double Rotation.

SINGLE ROTATION

>> untuk kasus 1 dan 2

vio - 2

DOUBLE ROTATION

>> untuk kasus 3 dan 4

vio - 3

DELETION

Delete pada AVL sama seperti BST, node yang dihapus akan digantikan dengan node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Setelah itu tree akan dicek kembali, apabila tidak seimbang maka akan diseimbangkan.


node yang ingin didelete adalah 60, sehingga 60 akan digantikan dengan 55. Namun setelah diganti terdapat ketidakseimbangan pada tree.


tree akan diseimbangkan dengan menggunakan single rotation, namun tree masih belum seimbang.


sehingga tree akan diseimbangkan kembali dengan menggunakan double rotation.

HEAP

1. Min Heap

  • Node parent lebih kecil dibandingkan node anak-anaknya
  • Root adalah node yang paling kecil di tree
Max Heap Example

INSERT



DELETE



2. Max Heap

  • Node parent lebih besar dibandingkan node anak-anaknya
  • Root adalah node yang paling besar di tree

Max Heap Example

INSERT

NoImage


DELETE



3. Min Max Heap


Delete-max operation in a min-max heap - Stack Overflow

INSERT

  • node baru masuk ke inde terakhir
  • jika node min,
    • parent < node, swap dan upheapmax dari parentnya
    • parent > node, upheapmin dari posisi node
  • jika node max, 
    • parent > node, swap dan upheapmin dari parentnya
    • parent < node, upheapmax dari posisi node

DELETE

  • delete min : menghapus node terkecil (root)
  • delete ma : menghapus node terbesar
  • node yang dihapus digantikan oleh inde terakhir
  • downheapmin jika delete min dan downheapmax jika delete max

TRIES

  • setiap node isinya 1 huruf
  • root melambangkan karakter kosong

Radix tree - Wikipedia

Comments

Post a Comment

Popular posts from this blog

BINARY SEARCH TREE

Image
BINARY SEARCH TREE SEARCHING Always starts from the root,  compare the data stored with the key we are searching for. I f the data is less than the key value, search in the left subtree otherwise search in the right subtree. a binary search tree can reduce the search time to O(n). Algorithm If root . data is equal to search . data return root else while data not found If data is greater than node . data goto right subtree else goto left subtree If data found return node endwhile return data not found end if INSERTION Start from the root and go down searching for a proper location. If the data is less than the key search for empty location in the left subtree, otherwise searh for empty location in the right subtree. Insert the data if the data that want to be insert is not in the tree (NULL), won't insert duplicates. Algorithm If root is NULL the...
Read more

Hash Table and Binary Tree

HASH TABLE Hash Table is a data structure that stores data. It is  consist of 2 parts:  An array format (generally array of Linked List) where we keep the data with special index value.   A hash function that help us to decide wherein the inputted data could be saved. Access of data will be very fast if we know the index of the wanted data.  The efficiency of mapping itself relies upon on how fast the hash function is. Hashing is implemented in 2 steps:  An element is converted into an integer by the usage of a hash function. This element may be used as an index to keep the original, which falls into the hash table. The element is stored in the hash table where it may be fast retrieved by the use of hashed key. Cryptographic Hash Functions A cryptographic hash function is a unique class of hash functions that has numerous properties making it ideal for cryptography. There are certain properties that a cryptographic hash func...
Read more

RANGKUMAN

RANGKUMAN Link ed List Linked List adalah struktur data linear, pada Linked List terdapat nodes / sekumpulan data yang bersambungan dimana setiap node menunjuk node yang lain dengan pointer. Single Linked List Single Linked List adalah Linked List yang hanya menggunakan satu pointer untuk menghubungkan satu node dengan node lainnya sehingga pada Single Linked List pointer hanya bisa bergerak satu arah saja. Single Linked List diawali dengan head untuk menyimpan alamat awal dan diakhiri dengan node yang pointernya mengarah ke NULL. Double Linked List Double Linked List adalah Linked List yang memiliki dua pointer yaitu head dan tail. Pointer head adalah pointer yang menunjuk ke node pertama dan pointer tail adalah pointer yang menunjuk ke node paling terakhir. Pada Double Linked List juga terdapat next untuk menunjuk ke node selanjutnya dan prev untuk menunjuk ke node sebelumnya sehingga  pointer pada Double Linked List bisa bergerak dua arah. Hash Table Ha...
Read more