Leftist Tree, Tries & Hashing

Heap & Deap

Heap

Heap terbagi menjadi 3, yaitu :
- min-heap
- max-heap
- min-max heap

min-heap
dalam min-heap, elemen / node yang terkecil berada di root atau terletak paling atas. dan semakin kebawah semakin besar. itu berarti node yang terbesar berada dileaf, tetapi bisa dileaf yang mana saja.
contoh min-heap:

max-heap

max-heap merupakan kebalikan dari min-heap dimana yang berada di root adalah node paling besar dan makin kebawah makin kecil.

contoh max-heap:

aplikasi heap

contoh aplikasi heap adalah Priority Queue dimana dalam Priority Queue ini terdapat beberapa operasi seperti:

(dalam min-heap)

- find-min : yaitu untuk menemukan nilai terkecil dalam heap tersebut yang pastinya terdapat di root

- insert : tentu saja kita dapat memasukkan elemen / node baru kedalam  heap

- delete-min : karena ini seperti queue maka yang kita delete adalah root atau nilai terkecil dalam heap

(dalam max-heap)

- find-max : untuk menemukan nilai terbesar dalam heap yang pastinya terdapat di root

- insert : memasukkan node baru kedalam heap

- delete-max : menghapus nilai terbesar dalam heap / root

(RBT) Red Black Tree

Red Black Tree merupakan Binary Search Tree yang terdiri dari 2 warna. Sebuah BST dikatakan RBT apabila memenuhi kondisi berikut :

1. setiap node memiliki warna, baik merah atau hitam
2. root adalah hitam secara default / otomatis
3. semua external node adalah hitam
4. jika sebuah node berwarna merah, maka kedua anaknya berwarna hitam. itu berarti tidak ada child merah yang memiliki parent merah
5. setiap node ke external node keturunan memiliki jumlah node hitam yang sama

Terdapat 2 operasi pada RBT yaitu Insert dan Delete

- Insert
insert pada RBT sama seperti pada konsep BST dan setiap node baru berwarna merah. jika parent berwarna hitam maka tidak ada violation dan tinggal insert saja node tersebut, tetapi jika parent berwarna merah maka violation terjadi (sesuai aturan nomor 4).
untuk memperbaiki violation tersebut maka:
  - misalkan:
Q = node baru
P = parentnya
S = sibling P (parent Q)
jika parent tidak memiliki sibling, S  = hitam (external node)
jika S = merah, ganti P dan S menjadi hitam dan parent P menjadi merah
jika S hitam maka lakukan rotasi seperti rotasi pada AVL, lalu ubah pivot rotasi terakhir menjadi hitam dan anaknya menjadi merah.

contoh 1 (node baru X): recolor

 contoh 2 (node baru X): single rotate

 contoh 3 (node baru Y): double rotate

- Delete

delete pada RBT juga sama seperti BST, hanya pada RBT ada beberapa kondisi mengenai warna, yaitu:

   - misalkan:

M = target delete

C = pengganti

jika M = merah, C = merah langsung ganti

jika M = merah, C = hitam langsung ganti

jika M = hitam, C = merah langsung ganti dan recolor C = hitam

jika M = hitam, C = hitam akan menciptakan token double black di posisi C

C = N

S = sibling

Sl = sibling left

Sr = sibling right

P = parent

kondisi jika ada token double black:

- kondisi 1 jika S = merah, SL & SR = hitam

maka reverse color P dan S dan rotate di P , token black tetap ada di N. cek kondisi lagi

- kondisi 2 jika s = hitam, SL & SR = hitam

maka recolor S = red , token black pindah ke P

jika warna P = merah recolor jadi hitam, jika P = hitam maka terjadi double black lagi

- kondisi 3 jika S = hitam , SL / SR = merah

maka rotate di parent (single/double), parent baru mengikuti warna parent lama dan kedua anaknya jadi hitam , lalu token black hilang

nb : jika token double black berada pada node merah, maka node tsb menjadi hitam dan

token double black hilang.

contoh delete:

www.binus.ac.id

www.skyconnectiva.com

Stack & Implementation

Stack
Stack bisa dibilang sebagai array linear karena stack berupa tumpukan. Istilah dalam Stack yaitu LIFO ( Last In First Out) atau FILO (First In Last Out). Contoh dalam kehidupan sehari - hari seperti tumpukan buku atau piring.
Dalam Stack terdapat 2 variabel, yaitu TOP dan MAX.
Top digunakan untuk menunjukkan elemen paling atas dari Stack. sedangkan Max untuk menunjukkan jumlah data dalam Stack.
Jika Top = NULL maka berarti Stack kosong, jika Top = Max - 1 berarti Stack penuh.
Pada Stack, jika menambah data maka Top akan naik, tetapi jika ada hapus data maka Top akan turun.
Beberapa operasi pada Stack :
- is_empty(); = untuk mengecek stack kosong
- is_full(); = untuk mengecek stack penuh
- top(); atau peek(); = untuk kembali ke index top
- push(x); = untuk menambah x pada Top didalam stack
- pop(); = untuk menghapus data dari Top dalam stack

Representasi Stack dalam array:

Representasi Stack dalam Linked List:

Dalam Linked Stack, setiap node memiliki 2 bagian:

- 1 bagian untuk menyimpan data

- 1 bagiannya lagi untuk menyimpan alamat dari node selanjutnya

Start pointer pada linked list digunakan sebagai Top, dan semua penambahan serta pengurangan data dilakukan di node yang ditunjuk oleh TOP.

Code untuk Stack: 

Untuk menambah data :

      struct stack *push (struct stack *top, int val){

         struct stack *ptr;

         ptr = (struct stack*) malloc (sizeof(struct stack*));

         ptr -> data = val;

         if (top == NULL){

              top = ptr;

              top -> next = NULL;

         } else {

              ptr -> next = top;

              top = ptr;

         }

         return top;

      }

Untuk menghapus data :

      struct stack *pop (struct stack *top){

         struct stack *ptr;

         ptr = top;

         if (top == NULL){

              printf(“\n STACK UNDERFLOW”);

         } else {

              top = top -> next;

              printf(“\nThe deleted value: %d”, ptr -> data);

              free(ptr);

         }

         return top;

      }

Untuk menampilkan data :

      struct stack *display(struct stack *top){

         struct stack *ptr;

         ptr = top;

         if (top == NULL){

              printf(“\n STACK IS EMPTY”);

         } else {

              while(ptr != NULL){

                  printf(“\n%d”, ptr -> data);

                  ptr = ptr -> next;

              } 

         }

         return top;

      }

Notasi Infix, Prefix, dan Infix

      

Prefix : operator ditulis sebelum operand

Infix : operator ditulis diantara operand

Postfix : operator ditulis setelah operand

Kita butuh notasi Prefix dan Postfix karena notasinya tidak membutuhkan kurung () untuk menghitungnya.

Prefix dan Postfix lebih mudah dihitung / dievaluasi oleh komputer.

Depth First Search (DFS) dan Breadth First Search (BFS)

Depth First Search merupakan algoritma untuk mencari didalam tree atau graph. DFS dimulai dari root hingga kebawah. Breadh First Search juga merupakan algoritma untuk mencari, bedanya dengan DFS, BFS mencari dengan menyebar kiri kekanan, sedangkan DFS mencari lurus hingga kedalaman.

Contoh DFS yang benar :

Contoh BFS :

www.binus.ac.id

www.skyconnectiva.com

Tree

Tree
Tree merupakan kumpulan dari 1 atau lebih node.

Dalam Tree,
- node paling atas disebut Root
- garis yang menghubungkan parent (orang tua) ke child (anak) disebut Edge
- node yang tidak memiliki children (anak) disebut Leaf
- node yang memiliki parent yang sama disebut Sibling
- degree dari node adalah total subtree dari node tersebut
- ketinggian / kedalaman suatu tree merupakan degree maksimum dari node dalam tree
- jika ada edge yang menghubungkan P ke Q maka P disebut Ancestor dari Q, sedangkan Q disebut Descendant dari P

Contoh Tree beserta keterangannya:
             
                

Keterangan :
- Degree dari Tree tersebut adalah 3
- Degree dari B adalah 2
- Height (ketinggian) = 3
- Parent (orang tua) dari C = A
- Children (anak) dari A = B, C, D
- Siblings (saudara) dari E = F
- Ancestor (leluhur) dari F = A, B
- Descendant (keturunan) dari B = E, F
- Root = A
- Leaf = E, F, G

Binary Tree
Binary Tree adalah rooted tree data structure dimana setiap node paling banyak memiliki 2 child.
2 child ini biasanya dibedakan menjadi left child dan right child.
Perbedaan Binary Tree dengan Binary Search Tree :

Binary Tree boleh tidak urut, jadi antara left child, parent dan right child nilainya bebas tidak harus urut.
Tetapi pada Binary Search Tree harus urut, left child harus lebih kecil dari parent dan right child harus lebih besar dari parentnya.

Selain Binary, terdapat juga Unary dan Ternary.

Jenis - jenis Binary Tree:

- Perfect Biinary Tree : Binary Tree dimana setiap level punya node yang sama

- Complete Binary Tree : Binary Tree yang disalah satu levelnya boleh ada yang belum terisi, Perfect Binary Tree merupakan Complete Binary Tree

- Skewed Binary Tree : Binary Tree dimana setiap node memiliki paling banyak 1 child

Binary Tree dalam array:

               

Keterangan:

- Index pada array menunjukkan nomor node

- Index 0 adalah node Root

- Index left child adalah 2p + 1 dimana p adalah index parent

- Index right child adalah 2p + 2

- Index parent adalah (p - 1) / 2

Binary Tree dalam Linked List:

        struct node {

            int data;

            struct node *left;

            struct node *right;

            struct node *parent;

         };

         struct node *root = NULL;

Prefix, Postfix, Infix

                       

Prefix  : *+ab/-cde

Postfix  : ab+cd-e/*

Infix  : (a+b)*((c-d)/e)

Cara mengubah Infix, Prefix dan Postfix.

Infix -> LVR

Prefix -> LRV

Postfix -> VLR

ingat KaBaTaKu (Kali Bagi Tambah Kurang)

contoh:

             2 + a + (b / 2) * 3

maka:

prefix : + 2 + a * / b 2 3

postfix : 2 a b 2 / 3 * + *

tugas :      c / a * 2 + 3 / 12 + 21

prefix :     + / + / c * a 2 3 12 21

postfix :    c a 2  * / 3 + 12 / 21 +

Implementasi Prefix dalam Linked List:

     void prefix(struct tnode *curr) {

        printf( “%c “, curr->chr );

        if ( curr->left  != 0 ) prefix(curr->left);

        if ( curr->right != 0 ) prefix(curr->right);
     }

Postfix :

     void postfix(struct tnode *curr) {

        if ( curr->left  != 0 ) postfix(curr->left);

        if ( curr->right != 0 ) postfix(curr->right);
        printf( “%c“, curr->chr );

     }

Infix:

     void infix(struct tnode *curr) {

        if ( curr->left  != 0 ) infix(curr->left);

        printf( “%c“, curr->chr );

        if ( curr->right != 0 ) infix(curr->right);
     }

www.binus.ac.id

www.skyconnectiva.com

Session 3 (Dosen Tamu) - Algoritma dan Struktur Data

Algoritma
Algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria.

Struktur Data
Struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.



Array
Array merupakan kumpulan elemen data yang sama karena elemen data tersebut harus memiliki tipe data yang sama (homogen). 

Linked List
Linked List merupakan struktur data yang dinais dimana elemennya dapat ditambah atau dihapus kapan saja karena dijalankan saat run-time. Setiap elemen pada Linked List disebut node (titik). Keuntungan dari Linked List adalah lebih menghemat memori karena elemen yang tersedia sesuai kebutuhan yang ingin dipakai saja.



Perbedaan Array dan Linked List

Dosen Tamu
Pada Senin, 10 Maret 2014 kelas besar Struktur Data 42PGT kedatangan dosen tamu bernama Ongky Pribadi, S.Kom. (CMIIW). Beliau bekerja sebagai programmer freelance dan dulunya lulusan Sistem Informasi. Beliau memilih untuk tidak bekerja dikantoran dan lebih memilih freelance. Saat ini beliau telah membuat banyak aplikasi untuk berbagai perusahaan dan beliau biasanya melakukan maintenance jika diperlukan. Misalnya dengan program yang hanya memerlukan 2 modul bisa berharga 12 juta untuk membuatnya, sedangkan untuk maintenance bisa mencapai 300ribu perdatang. Intinya bekerja dibagian teknologi seperti programmer merupakan pekerjaan yang memberikan gaji yang cukup besar.

www.binus.ac.id
www.skyconnectiva.com

Linked List Implementation

Linked List

Linked List merupakan struktur data yang dinamis dimana elemennya dapat ditambah atau dihapus kapan saja karena dijalankan saat run-time, tidak seperti array yang bila memesan memori sebanyak 5, maka bila diisi lebih dari itu akan error dan array dijalankan pada saat compile-time.
Setiap elemen pada Linked List disebut node (titik).
Keuntungan dari Linked List ini yaitu lebih menghemat memori karena elemen tersedia sesuai kebutuhan yang ingin dipakai saja.
Linked List dibedakan menjadi beberapa jenis, seperti :

1. Single Linked List
2. Double Linked List
3. Circular Single Linked List
4. Circular Double Linked List

Single Linked List

Single Linked List berarti hanya menggunakan single / 1 pointer saja pada Linked Listnya.

Dalam Single Linked List terdapat Push Depan dan Push Belakang untuk menambah, sedangkan Pop Depan, Pop Belakang untuk menghapus. Pada Single Linked List hanya terdapat -> (next).

            

             

Contoh Push Depan :

void pushDepan(int number)
{
    curr = (struct data*)malloc(sizeof(struct data));
    curr->number = number;
    curr->next = NULL;

    if (head==NULL)
    {
        head=tail=curr;
    }
    else
    {
        curr->next = head;
        head = curr;
    }
    tail->next = NULL;
}

Contoh Push Belakang :

void pushBelakang(int number)
{
    curr = (struct data*)malloc(sizeof(struct data));
    curr->number = number;
    curr->next = NULL;

    if(head==NULL)
    {
        head = tail = curr;
    }
    else
    {
        tail->next = curr;
        tail = curr;
    }
}

Contoh Pop Depan :

void popDepan()
{
    if(head==NULL)
    {
        printf("data not found");
        getchar();
        head = tail = curr = NULL;
    }
    else
    {
        curr=head;
        if(head==tail)
        {
            head = tail = NULL;
        }
        else
        {
            head = head->next;
            free(curr);
        }                    
    }
}

Contoh Pop Belakang :

void popBelakang()
{
    if(head==NULL)
    {
        printf("data not found");
        getchar();
        head = tail = curr = NULL;
    }
    else
    {
        curr = head;
        if (head==tail)
            head = tail = NULL;
        else
        {
            while (curr->next!=tail)
                curr = curr->next;
                tail = curr;
                curr = curr->next;
                tail->next = NULL;
        }
        free(curr);
    }
}

Double Linked List

Double Linked List merupakan Linked List yang berpointer ganda (2). Pada Double Linked List terdapat -> (next) dan <- (prev).

                        

Circular Single Linked List

Pada Circular Single Linked List, node terakhir berisi pointer yang menunjuk ke node pertama dan tidak ada yang memuat nilai NULL pada list. Pada Linked List ini hanya menggunakan satu pointer (next).

                       

Circular Double Linked List

Pada Circular Double Linked List, sama saja seperti Circular Single Linked List, hanya pada Linked List ini menggunakan pointer ganda (prev dan next).

                         

www.binus.ac.id

www.skyconnectiva.com

Pointer, Array and Introduction to Data Structure

Pointer (penunjuk) ->

pointer adalah tipe data yang nilainya berisi nilai dari tempat yang lain dalam memori komputer dengan menunjuk alamatnya karena dia memang digunakan sebagai penunjuk.

operator yang digunakan dalam pointer :
& (tanda dan) = untuk menunjuk alamat
* (tanda bintang atau kali) = untuk menunjuk isi

contoh dari penggunaan pointer : 

        int a;
        int *b;
        b = &a;
        *b = 5;
maka disini nilai a menjadi 5.

Array []
array merupakan kumpulan elemen data yang sama karena elemen data tersebut harus memiliki tipe data yang sama (homogen). 
index array dimulai dari 0. contohnya : array[15] maka index akan dimulai dari 0 - 14, sedangkan pada 15 akan diisi "null string".

array 1 dimensi :
array 1 dimensi seperti kotak memanjang.
contoh :

        int array[4] = { 0, 1, 2, 3 };

array 2 dimensi :
array 2 dimensi seperti kotak yang memiliki baris dan kolom.
contoh :

        int x[3][4] = { {1, 2, 3, 4},

                              {5, 6, 7, 8},

                              {9, 10, 11, 12}

                           };

array multidimensi :
array multidimensi merupakan array yang memiliki ruang - ruang yang tidak terbatas dimensinya sesuai keinginan user.
contoh :

        int x[4][3][5] = {{{1, 2, 3}, {0, 4, 3, 4}, {1, 2}},

                               {{9, 7, 5}, {5, 7, 2}, {9}},       

                               {{3, 3, 5}, {2, 8, 9, 9}, {1, 2, 1}},

                               {{0}, {1}, {0, 1, 9}}

                                };

cara memasukkan nilai kedalam array :
- inisialisasi
- inputan user
- memberi nilai pada elemen

operasi yang dapat dilakukan pada array:

•Traversal

•Insertion

•Searching

•Deletion

•Merging

•Sorting

bedanya array dengan struct adalah array harus homogen, sedangkan struct heterogen.
contoh struct :

        struct ttl {
char tempat[100];
int tanggal[5];
char bulan[20];
int tahun[5];
};

struct identitas {
char nama[100];
char alamat[100];
int umur[10];
struct ttl a [100];
};
pada struct tersebut terdapat struct dalam struct dan untuk mengakses struct menggunakan . (dot / titik).

Struktur Data
struktur data merupakan susunan/pengaturan data, baik dimemori komputer atau penyimpanan disk.
contoh dari beberapa tipe struktur data:

– Arrays
array seperti yang sudah dijelaskan diatas.

– Linked lists
linked list merupakan struktur data yang dinamis dimana elemennya dapat ditambah atau dihapus kapan saja karena dijalankan saat run-time, sedangkan array dijalankan pada saat compile-time.
setiap element disebut node (titik).
keuntungan dari linked list adalah lebih menghemat memori karena elemen tersedia sesuai kebutuhan yang ingin dipakai saja.

– Queues
queue merupakan elemen yang seperti antrian (FIFO = First In First Out). jadi dimana yang duluan mengantri maka akan selesai/keluar lebih dulu.

– Stacks
stacks bisa dibilang array linear karena stacks berupa tumpukan (FILO = First In Last Out).

– Binary trees
binary tree berbentuk seperti pohon yang memliki anak/cabang kebawah dan setiap cabang dihubungkan oleh titik.
setiap titik memiliki left pointer, right pointer dan elemen data.

Tipe data
tipe data adalah kumpulan objek dan operasi yang dapat dilakukan pada objek tersebut.
contohnya pada int, objeknya adalah 1, 2, 3, 4 dst. maka operasi yang dapat dilakukan pada objek tersebut adalah +, -, /, *, dll.
jika tipe datanya adalah char, maka objeknya seperti 'A', 'B', atau array of char maka objeknya "qwertyuiop", dll. operasi yang dapat dilakukan pada objek tersebut adalah strcmp, strcpy, dll yang terdapat dalam library <string.h>.

Tipe data abstrak

         data yang disusun sedemikian rupa sehingga spesifikasi objek dan spesifikasi operasi pada objek dipisahkan dari representasi dari objek dan pelaksanaan operasi.

www.binus.ac.id

www.skyconnectiva.com