Data Structure 011 - sky011 - Heap & Tries

Heap & Tries

halo guys dulur-dulur sekalian
kali ini ane bakalan ngasih beberapa materi tentang heap & tries, tapi sejujurnya sejauh ini kalau teorinya sendiri sih ane juga blom terlalu mateng jadi kita ambil dari web lain saja untuk beberapa materi yang kemudian dirangkum disini


jadi apa sih Heap itu?
trus kok mirip sama B-tree?
jadi Heap itu ada macemnya, contohnya Min Heap & Max Heap
perbedaan antara Heap sama B-tree yang paling utama itu adalah child / anak sebelah kiri sama child yang sebelah kanan itu gk ada hubungannya sama sekali

jadi gimana tuh?
pada Heap, hubungan child/anak yang kanan dan kiri hanyalah kepada induknya saja

Min Heap
apasih min heap?
min heap adalah heap yang dimulai dari angka paling kecil ke angka yang paling besar
cara penggambarannya kurang lebih ya seperti B-tree namun ini beda kok..

nah sekarang Max Heap
yap , kebalikan dari Min Heap dari angka terbesar sampai angka terkecil

yap berikut tadi beberapa contoh bentuk pengoperasian Heap , lebih mudah memang jika dipraktekan langsung dengan video / animasi. kalau saya sendiri jujur saja belum terlalu paham dan masih harus melihat youtube dan juga soal teorinya daripada missinformation lebih baik saya berikan langsung dari source web nya karena lebih terpercaya

https://www.youtube.com/watch?v=t0Cq6tVNRBA

source gambar dan teori  : https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm

Tries

nah sekarang kita ke materi tries

apa sih tries itu? tries itu adalah sebuah sebuah pohon yang dimulai dari node kosong dan juga node lain hanyalah berupa awalan katanya saja

contoh kodingan dari geeksforgeeks

// C implementation of search and insert operations

// on Trie

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdbool.h>

  

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

  

// Alphabet size (# of symbols)

#define ALPHABET_SIZE (26)

  

// Converts key current character into index

// use only 'a' through 'z' and lower case

#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

  

// trie node

struct TrieNode

{

    struct TrieNode *children[ALPHABET_SIZE];

  

    // isEndOfWord is true if the node represents

    // end of a word

    bool isEndOfWord;

};

  

// Returns new trie node (initialized to NULLs)

struct TrieNode *getNode(void)

{

    struct TrieNode *pNode = NULL;

  

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

  

    if (pNode)

    {

        int i;

  

        pNode->isEndOfWord = false;

  

        for (i = 0; i < ALPHABET_SIZE; i++)

            pNode->children[i] = NULL;

    }

  

    return pNode;

}

  

// If not present, inserts key into trie

// If the key is prefix of trie node, just marks leaf node

void insert(struct TrieNode *root, const char *key)

{

    int level;

    int length = strlen(key);

    int index;

  

    struct TrieNode *pCrawl = root;

  

    for (level = 0; level < length; level++)

    {

        index = CHAR_TO_INDEX(key[level]);

        if (!pCrawl->children[index])

            pCrawl->children[index] = getNode();

  

        pCrawl = pCrawl->children[index];

    }

  

    // mark last node as leaf

    pCrawl->isEndOfWord = true;

}

  

// Returns true if key presents in trie, else false

bool search(struct TrieNode *root, const char *key)

{

    int level;

    int length = strlen(key);

    int index;

    struct TrieNode *pCrawl = root;

  

    for (level = 0; level < length; level++)

    {

        index = CHAR_TO_INDEX(key[level]);

  

        if (!pCrawl->children[index])

            return false;

  

        pCrawl = pCrawl->children[index];

    }

  

    return (pCrawl != NULL && pCrawl->isEndOfWord);

}

  

// Driver

int main()

{

    // Input keys (use only 'a' through 'z' and lower case)

    char keys[][8] = {"the", "a", "there", "answer", "any",

                     "by", "bye", "their"};

  

    char output[][32] = {"Not present in trie", "Present in trie"};

  

  

    struct TrieNode *root = getNode();

  

    // Construct trie

    int i;

    for (i = 0; i < ARRAY_SIZE(keys); i++)

        insert(root, keys[i]);

  

    // Search for different keys

    printf("%s --- %s\n", "the", output[search(root, "the")] );

    printf("%s --- %s\n", "these", output[search(root, "these")] );

    printf("%s --- %s\n", "their", output[search(root, "their")] );

    printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );

  

    return 0;

}

source : https://www.geeksforgeeks.org/trie-insert-and-search/

https://www.youtube.com/watch?v=t0Cq6tVNRBA