Heap & Tries

Sekarang kita akan membahas dua materi yakni, Heap dan Tries. Kita langsung masuk ke penjelasannya aja yuk.

1. Heap

Heap itu adalah struktur data berbasis pohon khusus dimana pohon itu adalah pohon biner lengkap. Heap itu juga merupakan pohon yang isi dari root hingga leaf berurut dari index pada array.

contoh : kita memiliki array[] : {4 3 2 6 5}, maka kita akan memiliki pohon heap seperti :         

 

                4

              /   \

            3     2

          /   \

        6     5

Dari contoh itu kita dapat melihat bahwa setiap node dari heap tree tersebut itu sesuai urutannya dengan value dari index pada array yang kita miliki.

Heap juga memiliki tiga macam, yaitu min heap, max heap, dan min-max heap.

Saya hanya akan membahas min heap dan max heap saja, karena min-max heap itu jarang digunakan.

A. Min Heap

1. Insertion Dalam Min Heap

Min heap adalah heap yang data di parent atau root memiliki value yang lebih kecil dari childnya.

contoh : kita memiliki value dalam array[] : {7 4 3 8 2 6 5}

langkah pertama yang kita lakukan adalah memasukan semua value dalam array itu seperti contoh diatas saat saya menjelaskan tentang heap, yaitu masukan value kedalam tree sesuai dengan urutan indexnya. 

               7

      /   \

    4     3

   / \    /  \

         8  2  6   5

Setelah kita memasukkan value tersebut menjadi bentuk tree, sekanjutnya kita akan membandingkan child dengan parentnya. Jika value dari child lebih kecil dari parentnya maka akan kita swap.

                7                                          2

      /   \                                       /   \

    4     3               =>               4      3

   / \    /  \                                /  \    /  \

         8  2  6   5                             8   7 6   5

Saya akan menjelaskan cara melakukan swapping heap untuk min heap dari tree tersebut.

1. Kita akan bandingkan value 2 dan 4, karena yang lebih kecil adalah 2 maka kita akan swapping 2 dengan 4.
2. Lalu, saat 2 sudah di posisi 4, kita akan bandingkan kembali 2 dengan 7, karena yang lebih kecil 2 maka kita akan melakukan swapping 2 dengan 7 sehingga kita mendapatkan value root baru yaitu 2.
3. Dan yang terakhir, kita akan menukar 7 dengan 4 karena 4 lebih kecil kita akan melakukan swapping sehingga tree akan terbentuk seperti urutan yang sebelah kanan. 

2. Deletion Dalam Min Heap

Untuk deletion kita memakai cara yang sama seperti Binary Search Tree. Saya akan langsung menjelaskan caranya. Anggap saja kita memiliki array yang sama seperti array saat insertion min heap yaitu, array[] : {7 4 3 8 2 6 5} tetapi saya akan mengambil tree yang sudah memenuhi syarat min heap.

                          2

                /   \

                      4      3

                     /  \    /  \

                   8   7  6   5

Dari tree tersebut, misalnya saya ingin mendelete value 2 yang terletak di root. Nah untuk menggantinya kita ambil dari value urutan terakhir di index array (lebih mudahnya lagi, value yang terakhir dimasukkan kedalam tree) yaitu 5. 

                          5

                /   \

                      4      3

                     /  \    /  

                   8   7  6   

Setelah digantikkan root pada tree akan menjadi 5. setelah itu kita akan melakukan teknik heapify untuk mengganti / swapping dengan child yang memiliki nilai terkecil yaitu 3. 

                          3

                /   \

                      4      5

                     /  \    /  

                   8   7  6 

Bentuk tree akan menjadi seperti ini.

B. Max Heap

1. Insertion Dalam Max Heap

Cara melakukan insertion dalam max heap sama seperti min heap, tetapi untuk swapping sedikit berbeda, pada min heap semua parent valuenya akan lebih kecil daripada child, pada max heap valuenya akan lebih besar dari pada childnya.

contoh : kita memiliki tree sebagai berikut

               5

     /   \

   10    3

   /  \   /  \

          7  4 6   8

Kita akan melakukan swapping yang sama seperti min heap, tetapi bedanya adalah parent harus lebih besar daripada childnya. 

1. Dari tree tersebut kita akan melakukan swapping 3 dengan 8 karena 8 merupakan anak terbesar dari 3.
2. Setelah itu kita akan melakukan swapping 10 dengan 5 karena 10 merupakan anak terbesar dari 5.
3. setelah ditukar, 5 akan kita tukar kembali dengan 7 karena valuenya lebih besar.

Setelah melakukan semua itu kita mendapatkan tree sebagai berikut.

              10

     /    \

   7      8

  /  \    /  \

         5  4  6   3

2. Deletion Dalam Max Heap

Untuk deletion dalam max heap pun sama seperti min heap. Untuk contoh treenya saya akan ambil dari tree max heap yang sudah sesuai dengan syarat tree max heap.

              10

     /    \

   7      8

  /  \    /  \

         5  4  6   3

Lalu saya ingin mendelete value 8. Kita hanya langsung mendelete 8 dan menggantikannya dengan 3 setelah itu kita akan melakukan heapify dengan 6 dan langsung mendapatkan tree sebagai berikut.

              10

     /    \

   7      6

  /  \    /  

         5  4  3

C. Min-Max Heap

Untuk mempelajari min-max heap, saya akan mencantumkan sumbernya disini agar kalian bisa pelajari sendiri.

Sumber : 

https://en.wikipedia.org/wiki/Min-max_heap

2. Tries

Trie adalah struktur data pencarian informasi yang efisien. Menggunakan Trie, kompleksitas pencarian dapat dibawa ke batas optimal (panjang kunci). Jika kita menyimpan kunci dalam pohon pencarian biner, BST yang seimbang akan membutuhkan waktu yang proporsional dengan M * log N, di mana M adalah panjang string maksimum dan N adalah jumlah key dalam pohon. Dengan menggunakan Trie, kita dapat mencari key dalam waktu O (M). Namun penalti ada pada persyaratan penyimpanan Trie (Silakan merujuk Aplikasi Trie untuk detail lebih lanjut).

  

Setiap simpul Trie terdiri dari banyak cabang. Setiap cabang mewakili karakter kunci yang memungkinkan. Kita perlu menandai simpul terakhir dari setiap key sebagai simpul kata akhir. Bidang simpul Trie isEndOfWord digunakan untuk membedakan simpul tersebut sebagai simpul akhir kata. Struktur sederhana untuk mewakili simpul dari alfabet bahasa Inggris dapat sebagai berikut,

// Trie node
struct TrieNode
{
     struct TrieNode *children[ALPHABET_SIZE];

     // isEndOfWord is true if the node
     // represents end of a word
     bool isEndOfWord;
};

Memasukkan key ke Trie adalah pendekatan sederhana. Setiap karakter key input dimasukkan sebagai simpul Trie individual. Perhatikan bahwa anak-anak adalah array pointer (atau referensi) ke node trie level berikutnya. Karakter key bertindak sebagai indeks ke dalam array anak-anak. Jika kunci input adalah baru atau ekstensi dari kunci yang ada, kita perlu membangun simpul kunci yang tidak ada, dan menandai akhir kata untuk simpul terakhir. Jika key input adalah awalan dari key yang ada di Trie, kami cukup menandai simpul terakhir kunci sebagai akhir kata. Panjang key menentukan kedalaman Trie.

Mencari key mirip dengan memasukkan operasi, namun, kami hanya membandingkan karakter dan bergerak ke bawah. Pencarian dapat diakhiri karena akhir string atau kurangnya key dalam trie. Dalam kasus sebelumnya, jika bidang isEndofWord dari simpul terakhir benar, maka key ada di trie. Dalam kasus kedua, pencarian berakhir tanpa memeriksa semua karakter kunci, karena key tidak ada dalam trie.

Gambar berikut menjelaskan konstruksi trie menggunakan kunci yang diberikan dalam contoh di bawah ini,

                       root
                    /   \    \
                    t   a     b
                    |   |     |
                    h   n     y
                    |   |  \  |
                    e   s  y  e
                 /  |   |
                 i  r   w
                 |  |   |
                 r  e   e
                        |
                        r

Dalam gambar, setiap karakter bertipe trie_node_t. Sebagai contoh, root adalah tipe trie_node_t, dan itu anak-anak a, b dan t diisi, semua node root lainnya adalah NULL. Demikian pula, "a" di tingkat berikutnya hanya memiliki satu anak ("n"), semua anak lainnya adalah NULL. Node daun yang berwarna biru.

Sekian dari penjelasan saya mengenai Heap dan Tries. Semoga bermanfaat untuk kalian semua.

Nama : Reinhart Perbowo Pujo Leksono

NIM : 2301857254

Source:

1. https://www.geeksforgeeks.org/heap-data-structure/
2. https://practice.geeksforgeeks.org/problems/max-heap-and-min-heap
3. https://medium.com/@randerson112358/min-heap-deletion-step-by-step-1e05ff9d3932
4. https://www.geeksforgeeks.org/insertion-and-deletion-in-heaps/
5. https://en.wikipedia.org/wiki/Min-max_heap
6. https://www.geeksforgeeks.org/binary-heap/
7. https://www.geeksforgeeks.org/trie-insert-and-search/

                                

 

AVL Tree

Pengertian AVL Tree

AVL Tree adalah tree yang hanya boleh memiliki perbedaan tinggi/height maksimal satu antara subtree di kiri dan di kanan. Dengan adanya AVL tree, waktu pencarian akan dipersingkat dan lebih sederhana.

Gambar tersebut merupakan contoh dari AVL Tree karena perbedaan tinggi dari subtree kanan dan subtree kiri adalah 1.

Insertion

Insertion pada AVL tree sama seperti insertion pada BST, yang lebih kecil dari pada root akan berada di sebelah kiri dan yang lebih besar akan berada di sebelah kanan. Masalah yang biasa terjadi pada insertion di sini adalah bisa saja treenya tidak akan seimbang. Pada syarat AVL kita hanya diperbolehkan memiliki tinggi maksimal 1/-1 saja. Untuk membuat AVL tree tetap seimbang kita akan menggunakan dua teknik yaitu, single rotation dan double rotation. Jangan lupa untuk arah rotasi juga ada dua ya! right rotate dan left rotate.

1. Single Rotation

T1, T2, T3 and T4 are subtrees.
         z                        z                  
        / \                      / \                   
       y   T4                  T1   y
      / \           atau           / \
     x   T3                       T2  x             
    / \                              / \
  T1   T2                           T3  T4

Kita diperbolehkan menggunakan single rotation jika bentuk dari AVL tree seperti diatas. Jadi, dari root lurus kekiri bawah (leaf) ataupun dari root lurus ke kanan bawah (leaf). Cara untuk melakukan rotasinya adalah sebagai berikut.

T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

Dari tulisan tersebut kira dapat lihat cara untuk menggunakan single rotation. Pada tree yang pertama kita lihat bahwa disana terdapat perbedaan 2 level lebih banyak di subtree kiri. Oleh karena itu, kita harus rotasikan z yang awalannya adalah root dari tree (dan juga merupakan poros untuk dirotasikan), menjadi subtree di kanan. Sehingga y akan menjadi root baru dan semuanya akan kembali seimbang antara subtree kanan dan kiri. 

Permasalahan selanjutnya adalah bagaimana dengan T3 jika subtree kanan dan kiri y sudah terisi karena y telah menjadi root baru? Jawabannya adalah kita masukkan T3 kedalam subtree kiri z, mengapa? karena sebelumnya T3 merupakan anak kanan dari y yang nilainya lebih besar dari x tetapi lebih kecil dari z, sehingga saat single rotation telah dilakukan T3 akan pindah kedalam subtree kiri dari z.

2. Double Rotation

     z                  z           
    / \                / \         
   y   T4             T1  y
  / \        atau        / \
T1   x                  x   T2                  
    / \                / \    
  T2   T3             T3  T4    

Untuk double rotation kita hanya diperbolehkan memakainya jika bentuk tree seperti diatas, dari root sampai leaf bengkok dan tidak lurus kebawah. Cara untuk merotasikannya adalah sebagai berikut.

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

Dari tulisan diatas kita dapat melihat bahwa bentuk tree dari root sampai leaf bengkok. Perbedaan level pada subtree di kiri dan subtree di kanan adalah dua. Untuk melakukan double rotation kita harus mengetahui porosnya terlebih dahulu. Karena namanya saja double rotation berarti kita juga memiliki 2 poros yang harus dirotasikan. Poros pertama yang harus di rotasikan pada tree diatas adalah y karena y merupakan awalan yang membuat tree menjadi bengkok. Kita rotasikan y ke kiri sehingga memiliki bentuk tree baru seperti gambar kedua. Jika dilihat lebih baik lagi, kita dapat melihat bahwa gambar kedua mirip sekali dengan tree yang sudah kita bahas di single rotation. Oleh karena itu, poros kedua adalah rootnya yaitu z, z di rotasikan ke kanan sehingga x menjadi root yang baru dan z menjadi subtree bagian kanan dari x. Jangan lupa untuk memindahkan T3 ke subtree kiri dari z!

Deletion

Jika kita ingin menghapus suatu node dalam AVL tree kita dan kita ingin memastikan agar tree tersebut masih memenuhi syarat AVL, kita harus menambahkan operasi penghapusan BST standar untuk melakukan beberapa penyeimbangan ulang.

Dari dua gambar diatas kita dapat mengetahui jika node 32 sedang dihapus dan setelah dihapus kita akan kembali melihat bentuk tree itu lagi dan perbaiki tree tersebut jika ada yang tidak seimbang. Dari tree tersebut yang menjadi tidak seimbang adalah 44 yang akan ditandai dengan z, 62 akan ditandai dengan y dan 78 akan ditandai dengan x. Setelah itu kita dapat melihat jika dari root sampai leaf memiliki jalur lurus, sehingga kita akan melakukan single rotation dan porosnya berada pada z / node 44 yang akan kita rotate ke kiri sehingga, kita mendapatkan tree yang sama seperti gambar kedua. Sama seperti sebelumnya, 50 akan menjadi anak kanan dari z/node 44 karena node 50 sebelumnya merupakan anak kiri dari node 66 sehingga saat node 66 menjadi root yang baru, node 50 akan pindah menjadi anak kanan dari node 44 karena nilainya lebih besar dan node 62 subtree kanan dan kirinya sudah full.

Sekian penjelasan tentang AVL tree dari saya, semoga dapat membantu kalian semua. Terima kasih

Nama : Reinhart Perbowo Pujo Leksono

NIM ; 2301857254

Source :

1. https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
2. https://www.geeksforgeeks.org/avl-tree-set-2-deletion/

Binary Search Tree

Sebelum kita masuk kedalam pengertian Binary Search Tree(BST) saya akan menjelaskan kembali apa sih Binary Tree itu? Binary Tree adalah pohon yang dimana setiap simpulnya hanya boleh memiliki dua anak/subtree kedua anak/subtree tersebut HARUS terpisah. Kegunaan dari binary tree ini sendiri adalah untuk mengurutkan data-data yang disusun secara ascending(dari kecil ke besar) maupun descending(dari besar ke kecil).

Sekarang kalian telah mengetahui apa itu Binary Tree, selanjutnya adalah Binary Search Tree(BST). Sebenarnya BST tidak berbeda dengan Binary Tree, Binary Search Tree atau biasa kita sebut dengan BST adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap child node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

Operasi-operasi yang terdapat dalam BST:

• find(x) : untuk menemukan elemen x dalam BST.
• insert(x) : untuk memasukan elemen baru x dalam BST.
• remove(x) : untuk mengeluarkan/mendelete elemen x dalam BST.

Sekarang saya akan memberitahu kalian tentang aturan dalam memasukan/menginsert key dalam BST:

1. Untuk root, kita bisa langsung memasukannya tanpa masalah.
2. Untuk child, jika child yang kita masukkan nilainya lebih kecil daripada parent maka nilai tersebut akan dimasukan kedalam cabang/subtree kiri dan sebaliknya jika nilainya lebih besar daripada parent maka nilai tersebut akan dimasukkan kedalam cabang/subtree kanan.

untuk bagian deletion merupakan hal yang menurut saya lumayan ribet dan susah karena memiliki banyak sekali syarat.

contoh : 

25

/     \

20      30

/           \

10          45

Jika kita mau menghapus leaf(bagian dimana dia tidak memiliki cabang lagi biasanya berada di bagian paling bawah). Kita dapat langsung mendelete bagian tersebut dengan cara remove(45)/remove(10) nanti key tersebut akan langsung dibuang.

Tetapi yang membuat BST menjadi susah adalah jika kita ingin mendelete key yang masih memiliki cabang. Nah cara untuk mendeletenya adalah kita harus menggantikan key dengan leaf. contohnya:

55

/     \

30      70

/  \       \

10  40     85

Jika kita ingin menghapus key yang memiliki cabang kita harus menggantikannya dengan cabang yang memiliki nilai lebih besar. misalnya kita mau mendelete key 70 maka, remove(70) kemudian diganti dengan childnya yaitu 85.

Jika kita ingin mengganti root maka kita harus mengganti root dengan child yang memiliki nilai paling besar dari cabang root kiri berarti kita harus memilih cabang yang kanan dalam child kiri.

misalnya remove(55) lalu kita ganti dengan child kana dari cabang kiri sehingga root yang baru adalah 40.

berikut adalah contoh source code BST

#include <stdio.h>
#include <stdlib.h>

//inisialisasi struct
struct data{
 int number;
 //pointer untuk menampung percabangan kiri dan kanan
 data *left, *right;
}*root;

//fungsi push untuk menambah data
void push(data **current, int number){
 //jika pointer current kosong maka akan membuat blok data baru
 if((*current)==NULL){
  (*current) = (struct data *)malloc(sizeof data);
  //mengisi data
  (*current)->number=number;
  (*current)->left = (*current)->right = NULL;
 //jika tidak kosong, maka akan dibandingkan apakah angka yang 
 //ingin dimasukkan lebih kecil dari pada root
 //kalau iya, maka belok ke kiri dan lakukan rekursif 
 //terus menerus hingga kosong
 }else if(number < (*current)->number){
  push(&(*current)->left, number);
 //jika lebih besar, belok ke kanan
 }else if(number >= (*current)->number){
  push(&(*current)->right, number);
 }
}

//preOrder : cetak, kiri, kanan
void preOrder(data **current){
 if((*current)!=NULL){
  printf("%d -> ", (*current)->number);
  preOrder(&(*current)->left);
  preOrder(&(*current)->right);
 }
}

//inOrder : kiri, cetak, kanan
void inOrder(data **current){
 if((*current)!=NULL){
  inOrder(&(*current)->left);
  printf("%d -> ", (*current)->number);
  inOrder(&(*current)->right);
 }
}

//postOrder : kiri, kanan, cetak
void postOrder(data **current){
 if((*current)!=NULL){
  postOrder(&(*current)->left);
  postOrder(&(*current)->right);
  printf("%d -> ", (*current)->number);
 }
}

//searching data
void search(data **current, int number){
 //jika pointer current memiliki data
 if((*current)!=NULL){
  //cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
  if(number<(*current)->number){
   search(&(*current)->left,number);
  //jika lebih besar, maka belok ke kanan
  }else if(number>(*current)->number){
   search(&(*current)->right,number);
  //jika sama dengan, maka angka ketemu
  }else{
   printf("Found : %d", (*current)->number);
  }
 //jika tidak ada data lagi (not found)
 }else{
  printf("Not Found.");
 }
}

void main(){
 push(&root, 11);
 push(&root, 22);
 push(&root, 13);
 push(&root, 15);
 push(&root, 9);
 inOrder(&root);
 printf("\n");
 preOrder(&root);
 printf("\n");
 postOrder(&root);
 printf("\n");
 search(&root,91);
 getchar(); 

} 

Terima kasih atas perhatiannya, jika ada yang kurang jelas atau kurang materinya, tolong langsung saja komen dibawah 😁. 

Nama : Reinhart Perbowo Pujo Leksono

NIM : 2301857254

Source : 

- https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/

- powerpoint Data Structure di Binusmaya.

  

Hashing Table & Binary Tree

Halo semuanya! Sekarang saya ingin membahas singkat tentang Hashing Table dan Binary Tree. 

A. Hashing Table

Hashing tree adalah sebuah struktur data yang terdiri dari sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap baris menjadi angka lokasi record tersebut dalam sebuah tabel.

 Keunggulan dari hash table ini sendiri adalah pencarian dan waktu akses yang cepat. Tetapi ada kenegatifannya juga dari hash table yaitu jika record(sesuatu yang kita cari dalam hash table) memiliki angka yang sama, maka hal ini dapat menyebabkan bentrokan/collision antar record. Untuk mengatasi masalah ini dibutuhkan collision resolution policy(kebijakan resolusi bentrokan) untuk menentukan lokasi record dalam tabel sehingga tidak menyebabkan bentrokan antar record kembali.

Operasi yang digunakan dalam hash table:

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel.
• find: diberikan sebuah key, temukan nilai yang sesuai dengan key.
• remove: diberikan sebuah key, temukan nilai yang sesuai dengan key, lalu hapus nilai tersebut.
• getIterator: mengembalikan iterator, yang memeriksa nilai satu demi satu.

Cara untuk mendeklarasikan hash table :

typedef struct hashtbl {

hash_size size;

struct hashnode_s **nodes;

hash_size (*hashfunc)(const char *);

} HASHTBL;

dibawah ini merupakan struct yang digunakan untuk menunjuk kepada unsur pertama yang terhubung dengan daftar :

struct hashnode_s {

char *key;

void *data;

struct hashnode_s *next;

}

B. Binary Tree

Binary Tree adalah pohon yang dimana setiap simpulnya hanya boleh memiliki dua anak/subtree kedua anak/subtree tersebut HARUS terpisah. Kegunaan dari binary tree ini sendiri adalah untuk mengurutkan data-data yang disusun secara ascending(dari kecil ke besar) maupun descending(dari besar ke kecil).

Mungkin sampai disini kalian masih bingung cara memakai binary tree bagaimana. Oleh karena itu, saya akan memberikan contoh pemakaian binary tree.

Misalnya kita memiliki angka yang diacak yaitu 4 2 7 1 3. Aturan saat “insert” kedalam binary tree ini adalah dengan membandingkan data yang akan dimasukkan dengan kondisi root saat itu. Ok, mari kita telaah! angka pertama yang akan menjadi “root” adalah 4, maka angka tersebut akan menjadi paling atas. Lalu berikut nya 2, nah disini kita akan membandingkan 2 dengan 4, 2 lebih kecil dibanding 4, maka dia akan diletakkan dikir. Lalu 7, karena 7 lebih besar dari 4, maka 7 diletakkan disebelah kanan. Lalu 1, 1 lebih kecil dibandingkan 4 maka akan masuk ke sebelah kiri, namun karena sebelah kiri sudah memiliki “root” yaitu 2, maka 1 akan dibandingkan kembali dengan 2, karena 1 lebih kecil dibandingkan dengan 2, maka 1 diletakkan disebelah kiri dari 2. Begitu juga berlaku dengan 3. Binary tree akan memiliki bentuk seperti berikut :

1. 4
2. / \
3. 2 7
4. / \
5. 1 3

Bagi kalian yang baru mengetahui tentang binary tree, berikut adalah istilah-istilah yang dimiliki oleh tree itu sendiri :

• Parent : predecssor satu level di atas suatu node.
• Child : successor satu level di bawah suatu node.
• Sibling : node-node yang memiliki parent yang sama dengan suatu node.
• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
• Size : banyaknya node dalam suatu tree.
• Height : banyaknya tingkatan/level dalam suatu tree.
• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
• Leaf : node-node dalam tree yang tak memiliki seccessor.
• Degree : banyaknya child yang dimiliki suatu node.

Dibawah ini merupakan contoh dari Binary tree :

Berikut adalah penjelasan singkat dari saya, jika ada salah dan mungkin ada yang kurang penjelasannya bisa bertanya di kolom komentar. Terima kasih.

Nama : Reinhart Perbowo Pujo Leksono

NIM : 2301857254

Sumber:

1. https://id.quora.com/Apa-kegunaan-Binary-Tree-dalam-pemrograman
2. https://www.google.com/search?q=binary+tree+example&tbm=isch&ved=2ahUKEwiN98uEi5LoAhVTHHIKHTgICxEQ2-cCegQIABAA&oq=binary+tree+example&gs_l=img.3...0.0..415221...0.0..0.0.0.......0......gws-wiz-img.ny0982zKyr8&ei=ZaxoXs2wK9O4yAO4kKyIAQ&bih=722&biw=1536&safe=strict
3. http://muqoddasrengmadureh.blogspot.com/2013/01/algoritma-dan-struktur-data-hashing.html

Stack dan queue

Stack dan queue

Sekarang saya akan membahas singkat tentang stack dan queue. 

1. STACK

Dalam program yang berbasis stack, biasanya menggunakan sistem First In Last Out(FILO) karena input yang dimasukan itu menumpuk/stack. Dalam arti lain input pertama akan menjadi tail dan input terakhir akan menjadi head yang mana head yang baru/inputan terakhir akan menjadi elemen pertama yang dikeluarkan. 

Operasi-operasi yang ada di stack adalah : 

1. Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

Berikut adalah gambar untuk memperjelas STACK.

2. QUEUE

Seperti yang kita ketahui, queue dalam bahasa Indonesia adalah antrian. Oleh karena itu, Program berbasis Queue biasanya memakai sistem First In First Out(FIFO). Dalam arti lain data pertama yang diinput akan menjadi data pertama yang dikeluarkan.

Operasi-operasi yang ada di queue adalah:

1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.
2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.
3. EnQueue : berfungsi memasukkan data kedalam antrian.
4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.
5. Clear : Menghapus seluruh Antrian
6. IsEmpty : memeriksa apakah antrian kosong
7. IsFull : memeriksa apakah antrian penuh.

Berikut adalah penjelasan singkat dari saya, jika ada salah dan mungkin ada yang kurang penjelasannya bisa bertanya di kolom komentar. Terima kasih.

Nama : Reinhart Perbowo Pujo Leksono

NIM : 2301857254

Sumber:

1. https://www.google.com/search?q=gambar+ilustrasi+stack&tbm=isch&ved=2ahUKEwiJ47zq3pHoAhX_BbcAHQ9HA8IQ2-cCegQIABAA&oq=gambar+ilustrasi+stack&gs_l=img.3...0.0..449394...0.0..0.0.0.......0......gws-wiz-img.dbmiBbLDD94&ei=C35oXsmxL_-L3LUPj46NkAw&safe=strict

2. https://www.google.com/search?q=gambar+ilustrasi+queue&tbm=isch&ved=2ahUKEwi4rN2-35HoAhXZaCsKHVuHCSAQ2-cCegQIABAA&oq=gambar+ilustrasi+queue&gs_l=img.3...0.0..290542...0.0..0.0.0.......0......gws-wiz-img.O1qncpHwjD8&ei=vH5oXrjeHNnRrQHbjqaAAg&bih=722&biw=1536&safe=strict

3. https://furqonubd.wordpress.com/2013/05/20/stack-and-queue/

Linked List

Perkenalkan nama saya Reinhart Perbowo Pujo Leksono, disini saya akan memberikan kesimpulan mengenai pelajaran pada bab hari ini. Sebelumnya mari kita mengingat kembali apa itu linked list. Linked List saling terhubung dengan bantuan variabel pointer masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field. Linked List memiliki beberapa Jenis, yang pertama adalah Circular Single Linked List, Doubly Linked List, dan Circular Double Linked List. 

1. Circular Single Linked List

Dalam circular single linked list, node terakhir dari list berisi pointer menuju node pertama dalam list. Hal ini dapat membuat circular linked list menjadi sebuah loop. Berikut merupakan gambaran dari single linked list. Dalam list juga tidak dapat berisi NULL.

Dari gambar berikut kalian dapat melihat bahwa Single Linked List memiliki bentuk seperti loop. karena node pada tail kembali lagi ke head.

2. Doubly Linked List

Doubly Linked List adalah struktur data yang memiliki dua list, satu yang berisi referensi ke data berikutnya dan yang satu lagi berisi referensi ke data sebelumnya. Berikut adalah gambar untuk memperjelas pengertian dari doubly linked list.

3. Circular Double Linked List

Circular Double Linked List merupakan linked list yang sama dengan circular single linked list yang menggunakan pointer yang memiliki dua field, field pertama adalah field yang menunjuk pointer selanjutnya, dan field kedua adalah field yang menunjuk ke pointer sebelumnya.



Berikut adalah gambar dari Circular Double linked list. Dari sini, kita dapat melihat bahwa circular double linked list merupakan campuran dari circular single linked list dan double linked list, mengapa? Karena pada Circular double linked list memiliki pointer yang menuju field berikutnya(next), menuju field sebelumnya (Previous), dan memiliki loop atau pointer yang berasal dari tail menuju ke head kembali.


Berikut adalah artikel dari saya mengenai Linked List dan jenis-jenisnya. Semoga Artikel ini dapat membantu kalian. Bila ada yang kurang dapat di tambahkan di kolom komentar. Terima Kasih.

Referensi :
1. Power Point tentang Linked List
2. https://en.wikipedia.org/wiki/Doubly_linked_list
3. https://www.youtube.com/results?search_query=circular+linked+list+in+data+structure+using+c+
4. https://www.javatpoint.com/circular-singly-linked-list
5. https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/

Reinhart Perbowo Pujo Leksono - 2301857254