Heap and Tries

Heap and Tries

Heap

         Heap adalah struktur data berbasis pohon khusus di mana pohon itu adalah pohon biner lengkap. Secara umum, tumpukan dapat terdiri dari dua jenis:

Max-Heap: Dalam Max-Heap kunci yang ada di simpul akar harus paling besar di antara kunci yang                         ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua                         sub-pohon di Pohon Biner itu.


Min-Heap: Dalam Min-Heap kunci yang ada di simpul akar harus minimum di antara kunci yang ada di                    semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-                            pohon di Pohon Biner itu.

Insertion

Suppose the Heap is a Max-Heap as: 10 / \ 5 3 / \ 2 4 The new element to be inserted is 15. Process: Step 1: Insert the new element at the end. 10 / \ 5 3 / \ / 2 4 15 Step 2: Heapify the new element following bottom-up approach. -> 15 is more than its parent 3, swap them. 10 / \ 5 15 / \ / 2 4 3 -> 15 is again more than its parent 10, swap them. 15 / \ 5 10 / \ / 2 4 3 Therefore, the final heap after insertion is: 15 / \ 5 10 / \ / 2 4 3

Deletion

Suppose the Heap is a Max-Heap as:
      10
    /    \
   5      3
  / \
 2   4

The element to be deleted is root, i.e. 10.

Process:
The last element is 4.

Step 1: Replace the last element with root, and delete it.
      4
    /    \
   5      3
  / 
 2   

Step 2: Heapify root.
Final Heap:
      5
    /    \
   4      3
  / 
 2

Trie

          Tries adalah struktur data yang sangat spesial dan berguna yang didasarkan pada awalan string. Mereka digunakan untuk mewakili "Pengambilan" data dan dengan demikian nama Trie.
          Prefix: prefix adalah awalan string tidak lain adalah huruf apa saja yang dapat dianggap dimulai dari awal string. Misalnya, kata "abacaba" memiliki awalan berikut:

ab
aba
abac
abaca
abacab

          Trie adalah struktur data khusus yang digunakan untuk menyimpan string yang dapat divisualisasikan seperti grafik. Terdiri dari node dan edge. Setiap simpul terdiri dari maksimal 26 anak dan ujung-ujungnya menghubungkan setiap simpul induk ke anak-anaknya. 26 pointer ini tidak lain adalah pointer untuk masing-masing 26 huruf alfabet Inggris. Tepi terpisah dipertahankan untuk setiap tepi.
         String disimpan dengan cara top to bottom berdasarkan awalan mereka dalam sebuah trie. Semua awalan panjang 1 disimpan sampai level 1, semua awalan panjang 2 diurutkan sampai level 2 dan seterusnya.

Misalnya, perhatikan diagram berikut:



Nama : Raymond Andilsim
NIM   : 2301906533