RANGKUMAN MATERI DS

Nama : Zhofar Putra W.
NIM : 2301908141

 Tries

Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string. Kata tries diambil dari kata RETRIEVAL, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja. Tries sudah diterapkan ke banyak hal dalam kehidupan sehari-hari, contohnya pada web browser. suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja.(autocomplete)
kemudian selain itu juga pada spell checker, spell checker dapat mengetahui spelling kata yang tepat saat kita melakukan kesalahan dalam pengetikan. (autocorrect)
Heap 
Heap adalah complete binary tree yang berbasis struktur data dan memenuhi aturan heap. Tree pada heap and deap tidak memenuhi aturan BST yang harus terurut secara inorder, yang penting tree tersebut mengikuti aturan heap.
Ada 3 jenis heap :

  1. Min Heap : node paling kecil adalah root dan semakin kebawah levelnya semakin besar
  1. Max Heap : node paling besar adalah root dan semakin kebawah levelnya semakin kecil
  1. Min-Max Heap : min-heap dan max-heap levelnya saling bergantian pada tree
  • Insert node baru (key) pada index selanjutnya (setelah index terakhir)
  • lakukan upheap, yaitu compare key dengan parentya, jika node parent > key, maka swap. Jika tidak maka biarkan saja
  • lakukan point ke-2 berulang kali jika setelah diswap masih parent > key. namun stop jika key sudah berada pada posisi root.
  • operasi delete hanya terjadi pada rootnya saja. 
  • gantikan elemen yang didelete dengan node yang berada pada index terakhir
  • lakukan downheap, yaitu compare dengan salah satu childnya yang terkecil. jika node tersebut > child terkecil, maka swap
  • lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut < child terkecilnya
  • Insert node baru (key) pada index selanjutnya (setelah index terakhir)
  • lakukan uphead, yaitu compare key dengan parentnya, jika node parent < key maka swap. Jika tidak maka biarkan saja
  • lakukan point ke-2 berulang kali jika setelah diswap masih parent < key. namun stop jika key sudah berada pada posisi root.
  • operasi delete hanya terjadi pada rootnya saja. 
  • gantikan elemen yang didelete dengan node yang berada pada index terakhir
  • lakukan downheap, yaitu compare dengan salah satu childnya yang terbesar. jika node tersebut < child terbesar, maka swap
  • lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut > child terbesarnya
  • Insert node baru (key) pada index selanjutnya (setelah index terakhir)
  • jika key terletak pada level min : bandingkan dengan parentnya
  • Jika parent < maka swap dan upheapmax dari parentnya (dibandingkan dengan grandparentnya dari posisi key setelah swap)
  • Jika parent > key, upheapmin dari posisi key (dibandingkan dengan grandparentnya dari posisi key).
  • jika key terletak pada level max :
  • Jika parent > key maka swap dan upheapmin dari parentnya (dibandingkan dengan grandparentnya dari posisi keysetelah swap)
  • jika parent < key, upheapmax dari posisi key(dibandingkan dengan grandparentnya dari posisi key).
  • Delete Min, menghapus node terkecil, yaitu root
  • Delete Max, menghapus node terbesar, yaitu salah satu dari anak root
  • node yang dihapus digantikan oleh node index terakhir
  • lakukan downheapmin jika delete min, atau downheapmax jika delete max

Agar data benar-benar tersusun dalam struktur data BST, dua aturan yang harus dipenuhi pada saat data diatur dalam BST adalah sebagai berikut:
  • Semua data dibagian kanan sub-tree dari node t selalu lebih besar atausama dengan data dalam node t.    
  • Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node      t itu sendiri.
  • Memulai Pencarian Dari Root
  • Jika Root adalah value yang kita cari , maka berhenti
  • Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
  • Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan
  • Dimulai dari root
  • jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
  • jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
  • Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )
  • Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
  • Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
  • jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan)



x

Min Heap
Operasi : Find Min
Pada min-heap, untuk menemukan node terkecil sangatlah mudah, karena root dari min heap adalah node dengan nilai terkecil.
Operasi : Insertion


Operasi : Deletion
aturan delete :


Max Heap
Max heap adalah kebalikan dari min heap.
Operasi : Find Max
Pada max-heap, untuk menemukan node terbesar sangatlah mudah, karena root dari max heap adalah node dengan nilai terbesar.
Operasi : Insertion


Operasi : Deletion
aturan delete :


Min-Max Heap
Min-Max Heap adalah penggabungan dari min-heap dan max-heap. dimana pada tree ini kita dapat mendapatkan 1 angka terkecil dan 2 angka terbesar. Namun sayangnya, angka terbesar tersebut salah satunya memang terbesar tetapi satunya lagi belum pasti nilai terbesar keduanya.
Operasi : Insertion



Operasi : Deletion
ada 2 jenis delete, yaitu delete min, dan delete max


konsep deletenya sama :


Stack dan Queue



Stack

Stacks adalah struktur data dapat kita bayangkan berupa tumpukan. Misalnya tumpukan piring, kita menumpuk beberapa piring yang akan dicuci. Piring yang akan terambil lebih dulu adalah piring yang paling atas. Jadi, piring yang di tumpuk terakhir(paling atas) akan terambil duluan, atau yang biasa disebut dengan LIFO(Last In, First Out).

Terdapat dua fungsi utama pada stacks, yaitu Push & Pop. Push menaruh sebuah elemen pada bagian paling atas stacks, sedangkan Pop mengambil sebuah elemen yang berada paling atas pada stacks.

Queue

Queue atau antrian sebenarnya juga merupakan suatu list. Salah satu sifat yang membedakan queue dengan stack adalah bahwa pada queue penambahan elemen dilakukan pada salah satu ujung (ujung depan) dan pengambilan dilakukan pada ujung yang lain (ujung belakang) . Dengan demikian queue menggunakan prinsip FIFO (First In First Out), yaitu elemen yang pertama masuk akan pertama kali pula dikeluarkan.
Seperti pada stack, operasi-operasi dasar pada queue adalah operasi penambahan elemen ( sebut "ADDQ") dan operasi pengambilan elemen (sebut DELQ). Di bawah ini diberikan contoh pemakaian operasi PUSH dan POP dan isi stack untuk setiap selesai eksekusi satu operasi.
(Untuk mempermudah penulisan, di bawah ini isi queue tidak dituliskan secara bertumpuk, tetapi dengan kesepakatan:



elemen paling kanan adalah elemen yang ada pada ujung belakang (yang terakhir kali masuk)
queue yang dipakai bernama Q
ADDQ(Q,B) berarti memasukkan elemen B ke dalam queue Q
DELQ(B,Q) berarti mengambil elemen dari queue Q dan menaruhnya ke dalam variabel B

IMPLEMENTASI QUEUE DALAM BAHASA PASCAL
konstanta maxelm menyatakan banyaknya elemen maksimum yang dapat ditampung oleh queue
typeelemen adalah tipe data yang akan disimpan di dalam queue(bisa integer, word, real, boolean, char , string atau lainya)
banyak adalah field yang menyatakan banyaknya elemen dalam queue saat itu
queue diimplementasikan sebagai array linier dengan memandang bahwa elemen terdepan selalu berada pada sel pertama (implementasi fisik), sehingga bila terjadi pengambilan satu elemen maka semua elemen di belakang elemen terambil (bila ada) harus digeser ke depan satu langkah

Implementasi dalam bahasa Pascal dapat dilakukan dengan memanfaatkan struktur data record dan array. Array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang ada di dalam array.


HASHING TABLE & BINARY TREE


Hash Table

hash table adalah struktur data dasar yang tersedia di hampir semua bahasa pemrograman, maka kerentanan ini bisa dieksploitasi di hampir semua bahasa pemrograman yang ada, termasuk PHP, ASP.NET, Java, Ruby dsb.

Hash table adalah salah satu (bukan satu-satunya) implementasi dari associative array, artinya hash table ini adalah concrete data type (sudah konkrit bukan lagi abstract/konseptual).

Hash table pada dasarnya adalah sebuah array (setiap elemen array ini disebut dengan bucket), jadi fungsi hash ini akan menghasilkan index array berupa integer, dimana lokasi data disimpan.

Binary Tree

Binary Tree adalah struktur data yang hampir mirip juga dengan Linked List untuk menyimpan koleksi dari data. Linked List dapat dianalogikan sebagai rantai linier sedangkan Binary Tree bisa digambarkan sebagai rantai tidak linier. Binary Tree dikelompokkan menjadi unordered Binary Tree (tree yang tidak berurut) dan ordered Binary Tree (tree yang terurut). 

Binary Search Tree (BST) Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Aturan yang harus dipenuhi untuk membangun sebuah BST adalah sebagai berikut: 
Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri. 

Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t. 

Binary Search Tree

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list.Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.



binary search tree






Oprasi: Search 


Operasi: Insertion 
dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.
Bayangkan kita akan mencari value X.
Memasukan value (data) baru kedalam BST dengan rekrusif
Operasi: Delete ( Remove )



AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).

Cara menentukan Height dan Balance Factor :
Height :
– Jika node (root) tidak memiliki subtree heightnya = 0

– Jika node adalah leaf, height =  1
– Jika internal node, maka height =  height tertinggi dari anak + 1
-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.
AVL Tree Operations : Insertion
Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.
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 dari anak kanan T (left-right)
– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation
AVL Tree Operations : Deletion
Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali.

x
Balance Factor :
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi




Comments

Post a Comment