Heaps and tries

Video conference 12-5-2020

Heaps and Tries

Heaps adalah sebuah binary tree yang isinya (nodenya) dapat direpresentasikan dalam sebuah array.

cara memasukkan datanya adalah masukkan data dari array secara berurutan dari index 1-10
data pertamanya sebagai root, data ke 2 dan 3 sebagai left child dan right child, dan seterusnya.

cara menghitung index

x sebagai index
menghitung index parent : x/2
menghitung index left child : 2*x
menghitung index right child : (2*x)+1

misal kita mengambil node 18 yang memiliki index 4 (dari gambar di atas)

untuk menghitung index parent (node 15) : 4/2=2
untuk menghitung index left child : 4*2=8
untuk menghitung index right child : (4*2)+1=9

Min heap dan max heap

Min heap : setiap node pasti lebih kecil dari pada child node.

angka terkecil yang ada di min heap pasti ada di rootnya.

Insertion di Min heap
ada 2 cara untuk insert di min heap
cara 1 : Upheap

Masukkan node seperti biasa, lalu bandingkan dengan node di atasnya (parent) bila parent nilai nya lebih besar, tukar. Setelah ditukar lakukan hal yang sama dengan node diatasnya. Berhenti ketika node yang diatas nya sudah lebih kecil.

contoh :

cara 2 : Downheap

Masukkan node seperti biasa, mulai dari node root, bandingkan dengan left dan right child, bila lebih kecil, tukar node nya dengan node yang lebih kecil. lanjutkan terus dan berhenti bila node dibawahnya.

Deletion di Min heap :

deletion menggunakan konsep down heap.

Max heap : setiap node pasti lebih besar dari pada child node.

Max-Min heap

dalam max-min heap, max dan min bergantian pada setiap level
level ganjil memakai max heap
level genap memakai min heap

insertion di max-min heap

masukkan node seperti biasa,

bila node ada di min heap:

-jika node parent lebih kecil, tukar node sekarang dengan node parent, lalu cek grand parent dari nodenya, bila lebih kecil, tukar.

bila node ada di max heap:

-jika node parent lebih besar, tukar node sekarang dengan node parent, lalu cek grand parent dari nodenya, bila lebih besar, tukar.

Tries

Tries adalah tree yang node nya berisikan sebuah char (single character) dan root nya berisikan NULL.

contoh tries

tries di atas mengandung kata :

ALGO, API, BOM, BOS, BOSAN, dan BOR

struct trie {

  char chr;

  int  word;

  struct trie* edge[128];

} *root = 0;

root = (struct trie*)malloc(sizeof(struct trie));

root->chr  = ‘’;

root->word = 0;

ini adalah structure dari tries

insert word dalam tries

#include<stdio.h>

#include<stdlib.h>

void insert(struct trie *curr, char *p) {

  if ( curr->edge[*p] == 0 )

  curr->edge[*p] = newnode(*p);

  if ( *p == 0 ) curr->word = 1;
  else insert(curr->edge[*p],p+1);

}

struct trie* newnode(char x) {

  struct trie* node =

  (struct trie*)malloc(sizeof(struct trie));

  node->chr  = x;

  node->word = 0;

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

  node->edge[i] = 0;

  return node;

}

int main()

{

  char s[100];

  insert (root,s);

  return 0;

}

cari kata dalam tries

char s[100] = {“...”}; // global

void find(struct trie *curr, int x)

{

  if ( curr->word == 1 )

  {

    s[x] = 0;

    puts( s );

  }

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

  if ( curr->edge[i] != 0 )

  {

    s[x] = i;

    find(curr->edge[i],x+1);

  }

}

int main()

{

  int  i, n, okay;

  struct trie *curr;

  n = strlen(s);

  okay = 1;

  curr = root;

  for(int i = 0; i < n; && okay == 1; i++)

  {

    if(curr->edge[s[i]] == 0) okay=50;

    else curr=curr->edge[s[i]];

  }

 if(okay) find(curr,n);

}

maaf bila ada salah, karena saya juga masih belajar :)