Heap and Tries
Heap
Heap adalah complete binary tree berdasarkan struktur data yang memenuhi properti heap.
Find-Min
Deletion-Min pada Min-Heap
Max Heap
Min-Max Heap
Left-child(x): 2*x
Right-Child(x): 2*x+1
Tries
1. ALGO
2. API
3. BOM
4. BOS
5. BOSAN
6. BOR
Sumber :
http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html
Heap adalah complete binary tree berdasarkan struktur data yang memenuhi properti heap.
- Tujuan dari heap ini adalah untuk menemukan nilai terkecil pada min heap dan nilai terbesar pada max heap.
- mempunyai properties sebagai berikut:
Min Heap
- Minimum node terletak pada root
- Insert node selalu berurutan dari level paling rendah dengan urutan left ke right
- New node selalu menjadi leaf node
- Sesuikan sesuai heap properties secara rekursif
Deletion-Min pada Min-Heap
- Node yang dihapus selalu root karena merupakan node paling kecil, lalu diganti dengan node yang paling terakhir di insert
- Sesuaikan dengan heap properties secara rekursif
Max Heap
- Setiap node lebih besar dari masing-masing childnya
- Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node
- Heap dengan Min heap pada level ganjil dan Max heap pada level genap
- Aplikasi heap adalah sebagai berikut:
- Selection algorithm
- Priority Queue
- Dijkstra's Algorithm
- Prim Algorithm
- Implementasi heap menggunakan array
- Array dimulai dengan indeks ke 1
- Rumus umum aplikasi heap dengan array (x adalah current node):
Left-child(x): 2*x
Right-Child(x): 2*x+1
Tries
Tries atau Prefix Tree adalah ordered tree pada struktur data yang
digunakan untuk menyimpan array asosiatif (biasanya string). Tries merupakan sebuah tree di mana setiap vertex mewakili satu
kata atau awalan. Root mewakili karakter kosong (").
Properties pada tries:
Contoh tries tersebut mengandung kata-kata:Properties pada tries:
- Setiap vertex/node merepresentasikan satu huruf
- Root merepresentasikan karakter kosong
1. ALGO
2. API
3. BOM
4. BOS
5. BOSAN
6. BOR
Sumber :
http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html
Komentar
Posting Komentar