Minggu, 17 Mei 2020

Heap and Tries

Heap and Tries


HEAP
Suatu heap tree adalah Complete Binary Tree (CBT) di mana harga-harga key pada node-nodenya sedemikian rupa sehingga haga-harga key pada node-node anaknya tidak ada yang lebih besar dari harga key pada node orang tuanya.

Heap tree memiliki properties seperti :

  • Min Heap
    • Setiap node lebih kecil dari masing-masing childnya
    • Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node
Sumber : http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html

  • Max Heap
    • Kebalikan dari Min-Heap, dimana root dari Max-Heap merupakan node dengan bilangan terbesar, dan nilai/bilangan children nya selalu lebih kecil dibandingkan parent nya (semakin kebawah semakin kecil)
Sumber : http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html

  • Min-Max Heap
    • adalah heap yang urutan Min dan Max nya selang seling
    • Syarat Min-Max Heap:
      • Min pada level 0 (root) selalu yang terkecil
      • Max pada Level 1 selalu yang terbesar
Sumber : http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html


Implementasi Priority Queue
  • heap tree bermanfaat untuk mengimplementasikan priority queue. Sebagai suatu priority queue, heap tree memerlukan beberapa metoda sebagai berikut:
    • Metoda untuk menginisialisasi suatu CBT (Complete Binary Tree) a secara umum menjadi heap tree.
    • Metoda untuk mengambil data paling besar, yaitu root dari heap tree. 
    • Metoda untuk menambahkan satu key baru ke dalam heap tree. 
    • Metoda untuk menyusun ulang menjadi heap tree kembali setelah dilakukan metoda b atau c 

Insertion Heap
  • Saat sebuah data baru dimasukkan dalam heap, maka data langsung ditempatkan di index terakhir dalam heap. Setelah itu, data di-upheap. Maksudnya, data dibandingkan dengan parentnya. Bila lebih kecil, maka swap dengan parentnya. Hal ini dilakukan sampai data tersebut lebih besar dari parentnya.
Deletion Heap
  • Jika dalam insertion dipakai Upheap, maka dalam deletion dipakai Downheap. Deletion dalam heap otomatis menghapus node root dari heap. Jadi, delete min dalam min heap dan delete max dalam max heap.
  • Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.

TRIES
   
  • Tries adalah tree yang dilakukan untuk menyimpan array asosiatif
  • Properties pada tries:
    1. Setiap vertex/node merepresentasikan satu huruf
    2. Root merepresentasikan karakter kosong
  • Aplikasi pada trees adalah fitur auto-complete yang ada pada web-browser
Sumber : https://brilliant.org/wiki/tries/

Rabu, 29 April 2020

AVL Tree, B-Tree, dan Red-Black Tree

AVL TREE


  • AVL Tree merupakan bentuk binary tree yang diseimbangkan, di mana perbedaan antara ketinggian sub pohon kiri dan kanan tidak boleh lebih dari satu untuk semua node.
  • Tujuan AVL Tree adalah mempersingkat dan menyederhanakan waktu pencarian dari suatu data.
Contoh AVL Tree
Sumber : https://www.geeksforgeeks.org/avl-tree-set-1-insertion/



Contoh binary tree biasa (bukan AVL Tree)
Sumber : https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

  • Operasi dalam AVL Tree meliputi :
    1. Insert
      • Left-Left Case (Single Rotation)
      • Right-Right Case (Single Rotation)
      • Left-Right Case (Double Rotation)
      • Right-Left Case (Double Rotation)
    2. Delete
      • Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
      • Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
  • Single Rotation dan Double Rotation
    • Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image).
Sumber : http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html

    • Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 3. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4 (≥ 0), tinggi subtree T2 harus sama dengan T3 (≥ 0). Node yang ditambahkan akan menjadi child dari subtree T2 atau T3. Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image).
Sumber : http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html

  • CONTOH :
    • * insert: 5,6,7,0,4,3,8
    • * delete: 3,4,8




B-TREE

  • B-Tree adalah bagian dari binary tree, dimana bentuk penyederhanaan dan penyeimbangan sekaligus dari binary tree.
  • Aturan pada B-Tree : m = order
    • Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
    • Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
    • Root memiliki anak minimal 2, selama root bukan leaf
    • Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
    • Data yang tersimpan pada node harus terurut secara inorder
    • Semua leaf berada pada level yang sama, level terbawah
Sumber : http://suciantinovi.blogspot.com/2014/05/b-tree-and-heap-deap.html
  • Operasi pada B-Tree
    • Insert
      • Anggap data yang mau di insert adalah key
      • Posisikan key pada node yang sesuai, seperti pada BST dan 2-3 Tree, anggap node tersebut A
      • Jika A adalah node dengan jumlah data kurang dari m-1, maka langsung masukan saja
      • Jika A adalah node dengan jumlah data m-1, maka masukan nilai tengah kemudian masukan ke parentnya. Kemudian anggaplah parent tersebut A. Kemudian periksa kembali sesuai aturan point ke 3 dan 4.
    • Search
      • Searching pada B-Tree mirip seperti 2-3 Tree. Pertama-tama kita bandingkan dengan rootnya terlebih dahulu kemudian cek apakah sama dengan rootnya atau lebih kecil atau lebih besar atau bahkan diantara rootnya (jika root memiliki lebih dari 1 data).
    • Delete
      • Anggap node yang mau di delete adalah key
      • Delete dilakukan pada leaf. Meskipun pada saat menghapus node parent, kita tetap menganggapnya menghapus leaf, karena ketika parent dihapus lalu digantikan oleh anak terbesar subtree kiri atau anak terkecil subtree kanan sama saja kita seolah-olah menghapus anak yang menggantikannya. dimana anak tersebut selalu berada pada posisi leaf. maka leaf tersebut dianggap P.
      • Jika ukuran P > m/2 maka langsung delete saja data yang ingin dihapus
      • Jika ukuran P = m/2 maka : perhatikan siblingnya (anggap sibling adalah Q)
      • Q > m/2, maka rotasi pada P
      • Q = m/2, satukan P dan Q





RED-BLACK TREE

Contoh kasus:
a. Insert 1,2,3,4,5,6,7,8.








b. Insert 5,6,7,0,4,3,8



c. Delete from case a: all prime number in sequence, (hapus deret prima dari paling kecil)




d. Delete from case b: 0,3,4,5,6,7,8




Senin, 30 Maret 2020

Rangkuman Semester 2 (Before UTS)

RANGKUMAN

========================================================================
1. LINKED LIST

PENGERTIAN LINKED LIST

  • Linked list adalah sebuah struktur data linear yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan).

  • Perbedaan linked list dan array adalah pada lokasi penempatan elemen, dimana pada linked list elemen tidak ditempatkan di lokasi memori yang berdekatan dan elemen-elemen tersebut dihubungkan dengan pointer.
  • Terdapat beberapa macam linked list:
  1. Circular Single Linked List
  2. Doubly Linked List
  3. Circular Doubly Linked List

1. Circular Single Linked List
  • Circular Single Linked List adalah Single Linked List yang pointer nextnya kembali menunjuk pada head linked list tersebut, sehingga terbentuk sebuah siklus berulang.
  • Tidak ada storing nilai NULL pada linked list.


2. Doubly Linked List
  • Doubly Linked List adalah sebuah tipe linked list yang kompleks dimana node mengandung pointer yang menunjuk ke node sebelumnya serta node berikutnya dalam sebuah urutan.

  • Terdapat beberapa fungsi yang dapat dijalankan pada Double Linked List:
    • Insert
  • Insert dapat dilakukan dalam beberapa situasi berikut:
1. Add a node at the front
Node baru selalu ditambahkan sebelum head dari Linked List yang diberikan.

2. Add a node after a given node
Pointer ditandai ke node sebagai prev_node dan node yang baru ditambahkan setelah given node.

3. Add a node at the end
Node baru selalu ditambahkan setelah last node dari given linked list.

  • Delete
    • Tahapan dari delete linked list antara lain:
    1. Find previous node of the node to be deleted
    2. Change the next of previous node
    3. Free memory for the node to be deleted
    • Delete Linked List dapat dilakukan di beberapa situasi:
      1. If the node to be deleted is the only node
      2. If the node to be deleted is head
      3. If the node to be deleted is tail
      4. If the node to be deleted is not in head or tail

3. Circular Doubly Linked List

  • Sama seperti circular single linked list, tetapi seluruh node (masing-masing nya) memiliki 2 (two) pointers.

========================================================================
2. STACK & QUEUE


PENGERTIAN STACK & QUEUE


1. Stack
  • Stack adalah linear data structure yang elemennya hanya dapat di insert dan di delete dari satu sisi, yang disebut top

  • Stack sendiri memiliki konsep yang mirip dengan tumpukan piring, dimana jika kita ingin meletakkan piring, maka kita akan meletakan piring di paling atas (insert), serta ketika ingin mencuci piring tersebut, maka piring yang kita ambil adalah piring paling atas juga (delete).
  • Prinsip yang dipakai dalam stack adalah LIFO (Last In First Out), artinya elemen yang dimasukkan terakhir adalah yang dikeluarkan pertama.
  • Fungsi insert dalam stack dinamakan push operation, sedangkan fungsi delete dalam stack dinamakan pop operation.


    2. Queue
      • Queue adalah linear data structure yang elemennya hanya dapat di-insert dari satu sisi yang disebut rear dan hanya dapat di delete dari satu sisi juga yang disebut front.
      sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/
      • Konse queue mirip dengan konsep orang mengantri, dimana orang baru akan mengantri di urutan paling belakang (insert) dan yang akan dilayani dahulu adalah orang yang paling depan (delete).
      • Prinsip yang dipakai dalam queue adalah prinsip FIFO (First In First Out), dimana elemen yang dimasukkan pertama akan dikeluarkan pertama juga.
      • Fungsi insert dalam queuedinamakan enqueue operation, sedangkan fungsi delete dalam stack dinamakan dequeue operation.
      sumber : https://www.hackerearth.com/practice/notes/stacks-and-queues/

      • Kelemahan queue adalah ketika pointer left sudah mencapai elemen maximal, maka elemen sebelumnya yang di delete akan kosong (left to right). Sehingga diperlukan Circular Queue, dimana ketika pointer right/rear telah mencapai MAX, maka pointer right akan berlaku sebagai index 0 kembali, Sehingga menghasilkan bentuk siklus/circular.



      • Pengaplikasian queue antara lain pada:
        • Deques
        • Priority Queues
        • Breadth-First-Search (BFS)




      <<Perbedaan Antara Stack dan Queue>>

      sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/




      NOTASI INFIX, POSTFIX, DAN PREFIX

      Terdapat dua istilah dalam infix, postfix, prefix, yaitu:
      • Operator : tanda operasi (contoh : '+' , '-' , '*' ,  dll)
      • Operand : sebuah objek yang ada pada operasi matematika (contoh : 2 + 5, maka operand nya adalah 2 dan 5)


      Infix : operator ditulis di antara operand ( misal : (2 * 5) + 10 ) --> operand, operator, operand
      Prefix : operator ditulis sebelum operand ( misal : + * 2 5 10 ) --> operator, operand, operand
      Postfix : operator ditulis setelah operand ( misal : 2 5 * 10 + ) --> operand, operand, operator

      Kenapa perlu menggunakan notasi prefix/postfix?
      • Tidak perlu menggunakan tanda kurung untuk menentukan precedence, sehingga mempermudah komputer dalam mengoperasikan operasi hitung, yang artinya mempercepat dan menghemat alokasi memori komputer.
      Catatan :
      • Hal penting dalam membuat notasi prefix/postfix adalah memahami urutan prioritas (precedence) dari operasi hitung, dan apabila terdapat precedence yang sama dalam satu operasi hitung, maka menggunakan associative (left to right atau right to left --> tergantung dari operasi yang digunakan).

      Contoh :
      Infix : ( (1 + 3) / (100 * 5) ^ 30 )
      Prefix : / + 1 3 ^ * 100 5 30
      Postfix : 1 3 + 100 5 * 30 ^ /


      Contoh penerapan stack dalam konversi infix to prefix / infix to postfix :

      • Infix to Prefix




      • Infix to Postfix





      BFS dan DFS

      Algoritma dalam melintasi atau melakukan pencarian dalam tree atau graph dapat menggunakan BFS dan DFS berikut:

      1. Breadth-First-Search (BFS)
      • Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu.
      • BFS merupakan salah satu bentuk penerapan queue, dimana algoritma ini memerlukan sebuah antrian (queue) untuk menyimpan simpul yang telah dikunjungi.
      Visit order : A, B, C, D, E

      • Catatan : tiap simpul hanya dapat dikunjungi satu kali lalu masuk ke dalam antrian, sehingga memerlukan boolean untuk menandai simpul yang sudah dikunjungi atau belum.
      • Algoritma :
      1. Kunjungi simpul v
      2. Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu
      3. Kunjungi simpul-simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya.

      2. Depth-First-Search (DFS)
      • DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman.
      • Cara kerja : 
        • Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.
        • Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.
      • DFS merupakan salah satu penerapan stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon /tree. Selain itu DFS dapat diselesaikan dengan cara rekursif.
      Visit order: A, C, B, E, D

      • Algoritma :
      1. Masukkan simpul root ke dalam tumpukan dengan push
      2. Ambil dan simpan isi elemen (berupa simpul pohon) dari tumpukan teratas
      3. Hapus isi stack teratas dengan prosedur pop
      4. Periksa apakah simpul pohon yang disimpan tadi mempunyai anak simpul
      5. Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack
      6. Jika tumpukan kosong --> berhenti, tapi jika tidak --> kembali ke langkah 2

      <<Perbedaan Antara BFS dan DFS>>

      sumber : https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/



      ========================================================================
      3. HASHING AND HASH TABLE, TREE, AND BINARY TREE


      HASHING AND HASH TABLES

      • Hashing adalah teknik yang digunakan untuk menggunakan fungsi khusus yang dinamakan Hash function yang digunakan untuk memetakan nilai /objek dengan unique key tertentu untuk mengakses elemen dengan lebih cepat.
      • Efisiensi dari pemetaan/mapping bergantung dari efisiensi dari fungsi yang digunakan.
      • Dalam hashing, string characters biasanya ditransformasi ke nilai atau key yang lebih pendek yang menggambarkan original string tersebut.

      • Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value didapatlah hash value.
      • Kelebihan dari hash table antara lain sebagai berikut:
        1. Hash table relatif lebih cepat
        2. Kecepatan dalam insertions, deletions, maupun searching relatif sama
      • Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).
        • Dengan hash function didapat :
      Gambar 1.0
      • Maka data 13 akan disimpan pada index 0, data 25 akan disimpan di index 12, dst.
      • Untuk melakukan pencarian kembali suatu data, maka cukup menggunakan hash function yang sama dan mendapat hash index yang sama juga.
      • Misal : mencari data 27 --> h = 27 (mod 13) = 1

      • Hash function dapat dibentuk dari beberapa metode:
        1. Mid-square
          • Teknik yang dilakukan dengan mengkuadratkan nilai string/identifier dan diambil nilai tengahnya sebanyak jumlah digit yang diinginkan. 
          • Fungsi : h(k) = s
            • k = key
            • s = hash key
          • Contoh:
        2. Division (paling sering digunakan)
          • Teknik ini dilakukan dengan cara membagi string/identifier dengan menggunakan operasi modulus, kemudian sisa pembagiannya dijadikan alamat relatifnya.
          • Fungsi : h(z) = z mod M
            • z = key
            • M = nilai untuk membagi key nya, biasanya bilangan prima, ukuran table, atau ukuran memori yang digunakan
          • Contoh :
        3. Folding
          • Teknik ini dilakukan dengan cara membagi key value ke beberapa bagian dan selanjutnya menjumlahkan semua bagian-bagian yang telah dipecah tersebut.
          • Contoh :
        4. Digit Extraction
          • Teknik yang dilakukan dengan menentukkan digit dari angka yang sudah diberikan dan dijadikan sebagai hash address.
          • Contoh :
          • - Misal x = 14.568
          • - Jika yang di extract adalah nomor pertama, ketiga, dan kelima, maka hash code nya adalah : 158
        5. Rotating Hash
          • Teknik dengan memanfaatkan method division atau mid-square
          • Setelah nilai hash code/address nya didapat, lalu dilakukan rotasi
          • Misal :
          • - Hash address yang sudah didapat : 20021
          • - Hasil rotasi : 12002

      • (Lihat gambar 1.0)
      • Terdapat tabrakan (collision) pada k = 13 dan k = 39, dimana keduanya memiliki hash index yang sama, yaitu 0.
      • Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.
      • Berikut ini cara-cara yang digunakan untuk mengatasi collision :
        • Closed hashing (Open Addressing)
          • Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. Cara untuk mencari alamat lain tersebut antara lain :
          • Linear Probing
            • Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus (h+1) mod m.
        • Open hashing (Separate Chaining)
          • Dalam chaining, tiap string di simpan dalam chain (linked list), sehingga jika ada collision, kita hanya perlu untuk iterate/pengulangan dari chain.




      TREES & BINARY TREE

      • Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many).
      • Node pada tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.

      • Istilah umum dalam tree :
        1. Predecessor : node yang berada diatas node tertentu
        2. Successor : node yang berada di bawah node tertentu
        3. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
        4. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama
        5. Parent : Predecessor level di atas suatu node
        6. Child : successor satu level di bawah suatu node
        7. Sibling : node-node yang memiliki parent yang sama dengan suatu node
        8. Subtree : bagian dari tree yang berupa suatu node beserta descendant nya dan memiliki semua karakteristik dari tree tersebut
        9. Size : banyaknya node dalam suatu tree
        10. Height : banyaknya tingkatan/level dalam suatu tree
        11. Root : satu-satunya node khusus dalam tree yang tak punya predecessor
        12. Leaf : node-node dalam tree yang tak memiliki successor
        13. Degree : banyaknya child yang dimiliki suatu node

      • Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.

      leaf = 2, 5, 11, 4

      • Tipe-tipe binary tree :
        • Perfect binary tree : pohon biner yang semua node leafnya berada pada kedalaman yang sama dari node root.
      Depth = 4
      • Complete binary tree : Mirip dengan perfect binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

      • Skewed binary tree : binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

      • Implementasi binary tree menggunakan array
      • Index di array menggambarkan nomor node
      • Index 0 adalah root node
      • Index left child adalah 2p+1, p adalah index parent
      • Index right child adalah 2p+2
      • Index parent adalah (p-1)/2
      • Implementasi binary tree dengan linked list
        • struct node {
            int data;
            struct node *left;
            struct node *right;
            struct node *parent;
          };
          struct node *root = NULL;
                          

      • Expression tree concept
        • Misal :
                           
      • Prefix  : *+ab/-cde
      • Postfix      : ab+cd-e/*
      • Infix          : (a+b) * ((c-d)/e)



      ========================================================================
      3. BINARY SEARCH TREE

      • Binary Search Tree (BST) adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node.
      • Aturan binary search tree :
        1. Setiap node mempunyai value dan tidak ada value yang double
        2. Value yang ada di kiri tree lebih kecil dari rootnya
        3. Value yang ada di kanan tree lebih besar dari rootnya
        4. Kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )
      Sumber : https://www.programiz.com/dsa/binary-search-tree

      • Operasi dalam binary search tree :
        • Find(x)     : find value x didalam BST ( Search )
          • Memulai Pencarian Dari Root
          • Jika Root adalah value yang kita cari , maka berhenti
          • Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
          • Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan
      sumber : https://www.programiz.com/dsa/binary-search-tree

        • Insert(x)   : memasukan value baru x ke BST ( Push )
          • Dimulai dari root
          • jika x lebih kecil dari node value (key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
          • jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
          • Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )


      sumber : https://www.programiz.com/dsa/binary-search-tree

        • Remove(x)  : menghapus key x dari BST ( Delete )
          • Terdapat 3 case remove:
            • Jika value yang ingin dihapus adalah Leaf (Daun) atau paling bawah , langsung delete


            • Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
            • Jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) ATAU dengan cari dari right sub-tree anak kiri paling terakhir(leaf) (kanan,kiri)
      kita ingin delete node(37) memiliki 2 anak , jadi kita bisa ambil  (35 atau 42 ) untuk menggantikan value(37)


      ========================================================================


      SOURCE CODE ASSIGNMENT
      MINI MARKET CASHIER SIMULATOR


      #include <stdio.h>
      #include <ctype.h>
      #include <string.h>
      #include <strings.h>
      #include <stdlib.h>


      struct tnode{
          char namaProduk[50];
          int qtyProduk;
          int price;
          struct tnode *prev, *next;
      }*head = NULL, *tail = NULL;

      void pushCertainNode(char namaProduk[50], int qtyProduk, int price){
      struct tnode *newNode = (struct tnode*)malloc(sizeof(struct tnode));
      struct tnode *ptr = head;
          strcpy( newNode->namaProduk, namaProduk);
          newNode->qtyProduk = qtyProduk;
          newNode->price = price;
      newNode->prev = NULL;
      newNode->next = NULL;

          if(head == NULL){
      head = tail = newNode;
      }
          else if(strcasecmp(namaProduk, head->namaProduk) < 0){      // push depan
      newNode->next = head;
              head->prev = newNode;
              head = newNode;
      }
      else if(strcasecmp(namaProduk, tail->namaProduk) >= 0){     // push belakang
      if(strcasecmp(namaProduk, tail->namaProduk) == 0){
                  tail->qtyProduk += newNode->qtyProduk;
              }else{
              tail->next = newNode;
          newNode->prev = tail;
          tail = newNode;
              }
      }
      else{
              while(strcasecmp(namaProduk, ptr->next->namaProduk) >= 0) ptr = ptr->next;  //push tengah
              if(strcasecmp(namaProduk, ptr->namaProduk) == 0){
                  ptr->qtyProduk += newNode->qtyProduk;
              }else{

              newNode->prev = ptr;
      newNode->next = ptr->next; 
      ptr->next->prev = newNode; 
      ptr->next = newNode;
              }
      }
      }

      void popCertainNode(char namaProduk[50]){
      struct tnode *ptr = head;

          if(head == tail && strcasecmp(head->namaProduk, namaProduk) == 0){
      head = tail = NULL;
      free(ptr);
              printf("Produk berhasil dihapus!\n");
      }
      else if(strcasecmp(head->namaProduk, namaProduk) == 0){
      head = head->next;
              head->prev = NULL;
              free(head->prev);
              printf("Produk berhasil dihapus!\n");
      }
      else if(strcasecmp(tail->namaProduk, namaProduk) == 0){
      tail = tail->prev;
              tail->next = NULL;
              free(tail->next);
              printf("Produk berhasil dihapus!\n");
      }
      else{
      while(strcasecmp(ptr->namaProduk, namaProduk) != 0) {
                  if(ptr->next == NULL){
                      break;
                  }
                  else ptr = ptr->next;
              }
              if(strcasecmp(namaProduk, ptr->namaProduk) == 0){
                  ptr->prev->next = ptr->next;
                  ptr->next->prev = ptr->prev;
                  free(ptr);
                  printf("Produk berhasil dihapus!\n");
                  
              }
              else printf("Produk tidak ditemukan!\n");
      }
      }

      void editQty(char namaProduk[50], int qtyProdukBaru){
          struct tnode *newNode = (struct tnode*)malloc(sizeof(struct tnode));
      struct tnode *ptr = head;

          strcpy(newNode->namaProduk, namaProduk);
          newNode->qtyProduk = qtyProdukBaru;
      newNode->prev = NULL;
      newNode->next = NULL;

          if(head == NULL) return;
      else{
              while(strcasecmp(namaProduk, ptr->namaProduk) != 0){
                  if(ptr->next == NULL){
                      break;
                  }else ptr = ptr->next;
              }
              if(strcasecmp(namaProduk, ptr->namaProduk) == 0){
                  ptr->qtyProduk = newNode->qtyProduk;
                  printf("Jumlah produk berhasil di edit!\n");
              }
              else printf("Produk tidak ditemukan!\n");
      }
      }

      void printData(){
      struct tnode *ptr = head;
      if(head==NULL) return;
      else{

              for(int i = 0; i < 27; i++) printf("*");   
              printf(" INDOMARKET ");
              for(int i = 0; i < 26; i++) printf("*");
              puts("");

              for(int i = 0; i < 25; i++) printf("*");   
              printf(" DATA PEMBELIAN ");
              for(int i = 0; i < 24; i++) printf("*");
              puts("");
              
              printf("|%10sNama Produk%-10s|%1sQty%-1s|%3sHarga%-3s|%1sTotal Harga%-1s|\n", "","","","","", "", "", "");      // |31| + |5| + |11| + |13|
              for(int i = 0 ; i < 65 ; i++) printf("=");
              puts("");

              while(ptr!=NULL){
          printf("|%-31s| %-3d | Rp %-6d | Rp %-8d |\n", ptr->namaProduk, ptr->qtyProduk, ptr->price, (ptr->price * ptr->qtyProduk));
          ptr = ptr->next;
      }
              
              for(int i = 0 ; i < 65 ; i++) printf("=");
      puts("");
      }
      }

      void printBill(){
      struct tnode *ptr = head;
          int countTotalPrice = 0;

      if(head==NULL) return;
      else{

              for(int i = 0; i < 23; i++) printf(" ");   
              printf(" INDOMARKET ");
              for(int i = 0; i < 22; i++) printf(" ");
              puts("");

              for(int i = 0; i < 21; i++) printf("*");   
              printf(" STRUK BELANJA ");
              for(int i = 0; i < 21; i++) printf("*");
              puts("");
              
              printf("Qty %10sNama Barang%-10s %2sHarga%-2s %3sJumlah%-2s\n", "","","","","", "");  
              
              for(int i = 0 ; i < 57 ; i++) printf("-");
              puts("");

              while(ptr!=NULL){
                  printf("%-3d %-31s Rp %-6d Rp %-8d\n", ptr->qtyProduk, ptr->namaProduk, ptr->price, (ptr->price * ptr->qtyProduk));
          countTotalPrice = countTotalPrice + (ptr->price * ptr->qtyProduk);
                  ptr = ptr->next;
      }
              puts("");
              printf("%4s", ""); printf("TOTAL%-5s:", ""); //15
              printf("%-31s", ""); printf("Rp %-8d\n", countTotalPrice);
              puts("");

              printf("%23s%-22s\n", "", "Terima Kasih");
              printf("%20s%-19s\n", "", "'Kindness is Free'"); //16
      }
      }




      int main(){
          struct tnode *ptr = head;
          int menu;
          char inputNamaProduk[50];
          int inputQtyProduk;
          
          int randomPrice;
          int randomUpper = 500000, randomLower = 1000;
          
          int j = 0;
          char namaProdukToUpper;


          do{
              system("cls");
              printf("=== IndoMarket ===\n");
              printf("1. Input produk\n");
              printf("2. Edit jumlah produk\n");
              printf("3. Hapus produk\n");
              printf("4. Lihat Keranjang Pembelian\n");
              printf("5. Checkout\n");
              printf("Pilih menu >> ");
              scanf("%d", &menu);
              getchar();
              system("cls");
              switch (menu)
              {
              case 1: // INPUT PRODUK

                  printf("* Input Produk *\n");
                  printf("Masukkan nama produk: ");
                  
                  gets(inputNamaProduk);
                  
                  j = 0;
                  while(inputNamaProduk[j]){
                      namaProdukToUpper = inputNamaProduk[j];
                      toupper(namaProdukToUpper);
                      j++;
                  }
                  

                  printf("Masukkan jumlah produk: ");
                  scanf("%d", &inputQtyProduk);


                  randomPrice = ((rand() % (randomUpper - randomLower + 1)) + randomLower); //harga random, batas atas = upper, batas bawah = lower
                
                  pushCertainNode(inputNamaProduk, inputQtyProduk, randomPrice);
                  
                  system("cls");
                  printf("Produk berhasil di input!\n");
                  getchar();
                  printf("\nTekan enter untuk kembali ke menu!\n");
                  getchar();
                  break;
              
              case 2: // EDIT JUMLAH PRODUK
                  printf("* Edit Jumlah Produk *\n");

                  if(head==NULL) {
                      system("cls");
                      printf("Belum ada data, silahkan masukkan data terlebih dahulu!\n");
                  }
                  else {
                      system("cls");
                      printData();

                      printf("Masukkan nama produk yang ingin di edit: ");
                      gets(inputNamaProduk);
                      printf("Masukkan jumlah produk yang benar: ");
                      scanf("%d", &inputQtyProduk);

                      system("cls");
                      editQty(inputNamaProduk, inputQtyProduk);
                      getchar();
                      
                  }
                  printf("\nTekan enter untuk kembali ke menu!\n");
                  getchar();
                  break;
              
              case 3: // HAPUS PRODUK
                  printf("* Hapus Produk *\n");

                  if(head==NULL) {
                      system("cls");
                      printf("Tidak ada data!\n");
                  }
                  else{
                      printData();
                      printf("Masukkan nama produk yang ingin di hapus: ");
                      gets(inputNamaProduk);
                      
                      system("cls");
                      popCertainNode(inputNamaProduk);
                  }

                  printf("\nTekan enter untuk kembali ke menu!\n");
                  getchar();
                  break;
              
              case 4: // LIHAT DATA PEMBELIAN
              if(head==NULL) {
                      system("cls");
                      printf("Tidak ada data!\n");
              } else printData();
                  printf("\nTekan enter untuk kembali ke menu!\n");
                  getchar();
                  break;
              case 5: // CHECKOUT
                  if(head==NULL) {
                      system("cls");
                      printf("Tidak ada data pembelian!\n");
                  }
                  else{
                      printBill();
                  }
                  getchar();
                  break;
              }
          } while(menu != 5);

          return 0;
      }