Tree

Tree (Pohon)

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen.

Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root.

 

Contoh : 

             Direktori/folder pada windows atau linux.

A. Terminologi Pada Tree

         
      Contoh Tree :

B. Operasi Dasar

• Create: membentuk sebuah tree baru yang kosong.
•  Clear: menghapus semua elemen tree.
• Empty: mengetahui apakah tree kosong atau tidak.
•  Insert: menambah node ke dalam Tree secara rekursif.  Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri.  Untuk data pertama akan menjadi elemen root.
• Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu.  Syaratnya adalah tree tidak boleh kosong.
•  Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
• Count: menghitung jumlah node dalam Tree.
• Height : mengetahui kedalaman sebuah Tree
• Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree
• Child : mengetahui anak dari sebuah node (jika punya)

C. BST (Binary Search Tree) 

      Suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.

Tiap node dalam binary tree hanya boleh memiliki paling banyak dua child. 

     Contoh BST :

D. Tree Traversal

       Teknik menyusuri tiap node dalam sebuah tree secara sistematis, sehingga semua node dapat dan hanya satu kali saja dikunjungi

Ada tiga cara traversal

preorder

inorder

postorder

Untuk tree yang kosong, traversal tidak perlu dilakukan

1. Preorder (SLR)

1. Simpul / Node nya
2. Subtree sebelah kiri (Left)
3. Subtree sebelah kana (Right) 

         Contoh :

      Implementasi dalam bahasa C

      struct node {

                         struct node *left;

                         struct node *right;

                         char                 label;

                         }

                          void preorder(struct node *p)

                         {

                          if (p==NULL)  return;       jika empty-tree, tidak perlu lakukan

                          printf(“visit %c ”, p->label);  tampilkan label node yang dikunjungi

                          preorder(p->left);            traverse the left subtree

                          preorder(p->right);　　　　traverse the right subtree

                          }

2. Inorder (LSR)

1. Subtree sebelah kiri (Left)
2. Simpul / Node nya
3. Subtree sebelah kana (Right)

          contoh :

     Implementasi dalam bahasa C

     struct node {

                        struct node *left;

                        struct node *right;

                        char                 label;

                       }

                        void inorder(struct node *p)

                       {

                        if (p==NULL)  return;       jika empty-tree, tidak perlu lakukan

                        inorder(p->left);            traverse the left subtree

                        printf(“visit %c ”, p->label);  tampilkan label node yang dikunjungi

                        inorder(p->right);　　　　traverse the right subtree

                        }

3. Postorder (LRS)

1. Subtree sebelah kiri (Left)
2. Subtree sebelah kana (Right)
3. Simpul /Node nya 

          contoh :

     Implementasi dalam bahasa C

     struct node {

                        struct node *left;

                        struct node *right;

                        char                 label;

                       }

                         void postorder(struct node *p)

                       {

                         if (p==NULL)  return;       jika empty-tree, tidak perlu lakukan

                         postorder(p->left);            traverse the left subtree

                         postorder(p->right);　　　　traverse the right subtree

                         printf(“visit %c ”, p->label);  tampilkan label node yang dikunjungi

                       }

             Contoh Preorder, Postorder, Inorder

Notasi Prefix,Infix, dan Postfix

Dalam struktur data yang kita pelajari secara umum ada 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika,yaitu Prefix,Infix,dan postfix.Dan untuk mengetahui notasi-notasi yang diatas itu,sebelumnya kita harus mengenal dan mengetahui indikator yang ada di notasi itu tersebut.

    Notasi ini terbentuk dari Operand dan Operator.
Operand adalah data atau nilai yang membantu dalam proses,sedangkan Operasi adalah fungsi yang digunakan dalam proses.



contohnya:
A+B*C
2 + 5 * 3
Keterangan: A ,B ,C ,2 ,3 ,5 adalah Operand.
+,*  adalah Operator.

   Setelah kita mengenal dan mengetahui dengan Operand dan Operator, maka mari kita mengenal juga tingkat/ level yang ada didalam notasi tersebut:
-( ) (Kurung).
- ^ (Pangkat).
- * / (Perkalian / Pembagian).
- + - (Penjumlahan / Pengurangan).

Notasi ada 3 jenis, yaitu Prefix,Infix dan Postfix yang seperti kita ketahui di atas:

1.Prefix adalah notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.
   contoh: A + B * C (infix).
   maka notasi prefixnya adalah: +A*BC.

   Pemecahannya:

                A+B*C

        Diketahui ada 3 operand yaitu: A, B, C dan 2 operand yaitu: +, *.proses dimulai dengan melihat dari hirarkhi oprator.Contoh diatas operator yang tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand yaitu B*C, prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand,sehingga fungsi B*C, notasi prefixnya menjadi *BC.

Sehingga hasil sementara dari notasi prefix adalah:
      A+*BC

        Selanjutnya mencari prefix untuk operator yang berikutnya yaitu  +, cara yang dilakukan sama seperti diatas, operator + diapit oleh operand, yaitu A dan *BC, gabungkan operand,sehingga menjadi A*BC,lalu pindahkan operator kedepan operand,sehingga hasil akhir menjadi :
     +A*BC.


2.Infix adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand.
   Contoh :          
                 - A + B * C
                 - (A + B) * C
                 - A - (B + C) * D ^ E


3.Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.
   Contoh : A + B * C ( infix).
maka notasi postfix adalah ABC*+.

Pemecahannya:

                  A + B * C

     Diketahui ada 3 operand yaitu : A,B,C dan 2 operator yaitu : +, *. proses dimulai dengan melihat dari hirarkhi operator.Contoh diatas operator yang tertinggi adalah * kemudian +.

Tanda * diapit oleh kedua operand yaitu B dan C yaitu B*C, postfix dengan menggabungkan operand B dan C menjadi BC,lalu memindahkan operator ke belakang operand C, sehingga fungsi B*C, notasi postfixnya menjadi BC*.Sehingga hasil sementara dari notasi postfix adalah A + BC*

      Selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +, dengan cara yang dilakukan sama seperti di atas, operator + diapit oleh 2 operand, yaitu : A dan BC* gabungkan operand tersebut,sehingga menjadi ABC*,lalu pindahkan operator + kebelakang operand ABC*.
Sehingga hasil akhir  menjadi :   ABC*+.

contoh Notasi Huruf :

Contoh Notasi Angka:

Queue

Queue (Antrian)

A.    Pengertian Queue (Antrian)

Queue (Antrian) adalah suatu kumpulan data yang mana penambahan data / elemen hanya dapat dilakukan pada sisi belakang sedangkan penghapusan / pengeluaran elemen dilakukan pada sisi depan.

Jenis struktur data antrian sering digunakan untuk menstimulasikan keadaan dunia nyata. Antrian banyak dijumpai dalam kehidupan sehari-hari. Misal : antrian registrasi mahasiswa, tiket kereta api dan lain-lain.

Berbeda dg stack, prinsip yg digunakan dalam antrian adalah FIFO ( First In First Out ). Dengan kata lain, urutan keluar elemen akan sama dengan urutan masuknya.

Dalam antrian tidak semuanya dilakukan secara FIFO murni, contoh yg relevan dalam bidang komputer adalah Time-sharing Computer System, dimana ada sejumlah penakai ( user ) yg menggunakan sistem tsb secara serempak. Karena sistem ini biasanya menggunakan processor, dan sebuah memory utama. Jika processor sedang dipakai oleh seorang user, maka user yang lain harus antri sampai gilirannya.

           

Antrian ini tidak akan dilayani secara FIFO murni tetapi biasanya didasarkan pada suatu prioritas tertentu. Antrian yang memasukkan unsur prioritas dinamakan dengan ANTRIAN PRIORITAS ( PRIORITY QUEUE )

Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya. DEQUEUE adalah mengeluarkan satu elemen dari suatu antrian. Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya sehingga membutuhkan variabel Head dan Tail

           

Deklarasi Queue :

B.     Operasi dalam Queue

1.       Create ( )

a.       Untuk menciptakan dan menginisialisasi Queue

b.      Dengan cara membuat Head dan Tail = -1

2.      IsEmpty ( )

a.       Untuk memeriksa apakah Antrian sudah penuh atau belum

b.      Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty

c.      Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah

d.    Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail

3.      IsFull

a.       Untuk mengecek apakah Antrian sudah penuh atau belum

b.      Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh 

4.      Enqueue (data)

a.       Untuk menambahkan elemen ke dalam antrian, penambahan elemen selalu ditambahkan di elemen paling belakang.

b.      Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail

5.      Dequeue()

a.       Digunakan untuk menghapus elemen terdepan/pertama dari antrian

b.      Dengan cara mengurangi counter Tail dan menggeser semua elemen antrian kedepan.

c.       Penggeseran dilakukan dengan menggunakan looping

6.      Clear()

a.       Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1

b.      Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya 

7.      Tampil

a.       Untuk menampilkan nilai-nilai elemen antrian

b.      Menggunakan looping dari head s/d tail