Pertemuan 6-Binary Search Tree -Benedick Asdyo-2101631090

Tree adalah graf yang tidak ada loop.
Binary tree adalah tree yang anak setiap node maksimal 2.
Binary search tree adalah Binary Tree yang memiliki aturan bahwa setiap child node sebelah kiri selalu lebih kecil nilainya dari pada root node atau sebaliknya. Penggunaan binary search tree atau BST ini adalah untuk mempercepat atau memperkecil waktu untuk mencari sebuah data.

Operasi - operasi dalam BST atau Binary Search Tree ini adalah: Search, Insertion, dan Deletion.
seperti namanya search merupakan operasi untuk memasukan data ke dalam Binary Search tree, Search adala pencarian data dalam Binary Search Tree dan deletion adalah penghapusan data dalam Binary search tree. 

Search

Algoritma dalam mencari sebuah data dalam Binary Search Tree:
Cek data yang ingin di cari dari lvl tertinggi jika yang dicari lebih kecil dari node yang kira tunjuk geser ke bagian kiri tree, jika lebih besar kita cari di node paling kanan , begitu seterusnya hingga datanya ketemu

struct node* search (struct node *curr, int X) {

  if ( curr == NULL ) return NULL;

  // X is found

  if ( X == curr->data ) return curr;

  // X is located in left sub tree

  if ( X  < curr->data ) return find(curr->left, X);

•

  // X is located in right sub tree

  return find(curr->right, X);

 

Insertion

Algoritma dalam memasukan data kedalam Binary Search Tree adalah sama seperti insertion, namum setiap memasukan data kita harus seperti men search data dari root treenya lalu menaruh data itu jika child dari node yang dikunjungi kurang dari dua ,untuk penempatan mengikuti aturan biasa dikiri jika lebih kecil dari parent atau dikanan jika lebih besar
psuedo code:

IF TREE = NULL, then 

  Allocate memory for TREE

            SET TREE->DATA = VAL

      SET TREE->LEFT = TREE ->RIGHT = NULL

        ELSE

      IF VAL < TREE->DATA

       Insert(TREE->LEFT, VAL)

      ELSE

  Insert(TREE->RIGHT, VAL)

           [END OF IF]

       [END OF IF]

Step 2: End

contoh gambar :

Deletion
dalam penghapusan ada beberapa kasus yang perlu diperhatikan antara lain :
- Jika data yang ingin di hapus ada di leaf maka langsung saja hapus data tersebut
-Jika data yang ingin di hapus memiliki satu child maka hapus node tersebut dan sambungkan anaknya ke parent yang tadi kita hapus
-Jika data yang ingin di hapus memiliki 2 child maka cari child paling kiri dari node tersebut dan ganti node yang ingin di hapus dengan left most child lalu hapus left most child pada tempat asalnya


psuedo-code:

: IF TREE = NULL, then 

       Write “VAL not found in the tree”

        ELSE IF VAL < TREE->DATA

         Delete(TREE->LEFT, VAL)

        ELSE IF VAL > TREE->DATA

       Delete(TREE->RIGHT, VAL)

        ELSE IF TREE->LEFT AND TREE->RIGHT

       SET TEMP = findLargestNode(TREE->LEFT)

       SET TREE->DATA = TEMP->DATA

       Delete(TREE->LEFT, TEMP->DATA

 ELSE

  SET TEMP = TREE

  IF TREE->LEFT = NULL AND TREE ->RIGHT = NULL

  SET TREE = NULL

  ELSE IF TREE->LEFT != NULL

  SET TREE = TREE->LEFT

  ELSE

  SET TREE = TREE->RIGHT

  FREE TEMP  





Nama : Benedick Asdyo
NIM   : 2101631090

Pertemuan 5 -Introduction to Tree, Binary Tree And Expression Tree- -Benedick Asdyo-2101631090

 Tree
merupakan graf tanpa adanya cycle atau koleksi dari satu atau lebih node
Istilah dalam tree:

contoh tree

 Node dari tree =  A,B,C,D,E,F,G
Root dari tree = A(Node teratas) 

DEGREE dari Tree = 3

DEGREE dari C = 2

tinggi tree = 3

PARENT of C = A

CHILDREN dari  A = B, C, D

SIBILING dari F = G

ANCESTOR dari F = A, C

DESCENDANT dari C = F, G

 Binary Tree
-seperti namanya, binary tree adalah tree yang setiap node nya memiliki children maksimal 2
-Node tanpa children disebut leaf
-contoh 

-jumlah node pada level tertentu dapat dihitung dengan rumus 2^level
-jumlah maksimal seluruh node dengan ketinggian h dapat dihitung dengan 2^h-1
-tinggi maksimal dari binary tree dapat dicari dengan rumus log n basis 2

 -Tipe-tipe binary tree:
PERFECT binary tree adalah binary tree yang setia levelnya memliki depth yang sama.

COMPLETE binary tree adalah Hampir sama dengan perfect binary tree, tapi semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas berbeda.

SKEWED binary tree adalah binary tree yang setiap nodenya hanya memiliki 1 anak

-Implementasi dengan linked list :

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

•

struct node *root = NULL;

 Konsep expression tree

 

Prefix  : *+ab/-cde

Postfix    : ab+cd-e/*

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

 untuk prefix kita tulis dulu operatornya baru childrennya dari kiri
untuk postfix kita tulis dulu childrennya baru parentnya(seperti saat menggambarkan tree untuk fungsi rekursif)
untuk infix kita perlu bantuan kurung agar operatornya dijalankan dengan benar






Nama : Benedick Asdyo
NIM   : 2101631090

Pertemuan 4-Implementasi Linked List 2-Benedick Asdyo-2101631090

 Stack adalah suatu urutan elemen data yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. analogi stuck dalam kehidupan sehari-hari adalah tumpukan piring dimana pada umumnya tumpukannya ditambah di atas dan jika diambil juga dari atas. Data dalam stack disimpan dengan konsep LIFO(Last In First Out).

Operasi yang umum digunakan dalan stack ada 3:
- pop() mengeluarkan elemen paling atas
- push() memasukan elemen di paling atas
- top() mereturn nilai dari elemen paling atas

Implementasi penggunaan stack pada umumnya untuk:

•Infix evaluation

•Postfix evaluation

•Prefix evaluation

•Infix to Postfix conversion

•Infix to Prefix conversion

•Depth First Search

Sebelum mengetahui apa itu prefix,infix dan postfix, Ada baiknya kita mengetahui apa itu operator dan operand.
Operand adalah nilai asal yang digunakan didalam proses operasi
operator adalah instruksi yang diberikan untuk mendapatkan hasil dari proses tersebut.

prefix berarti operator nya di taruh sebelum operand
infix berarti operatornya berada di tengah operand(seperti yang biasa ditulis (contoh = 5+2))
postfix berarti operatornya diratuh di akhir operand
contoh:

Prefix	Infix	Postfix
* 4 10	4 * 10	4 10 *
+ 5 * 3 4	5 + 3 * 4	5 3 4 * +
+ 4 / * 6 – 5 2 3	4 + 6 * (5 – 2) / 3	4 6 5 2 – * 3 /  +

operator bila di sajikan atau ditulis dengan prefix dan postfix kita tidak usah menuliskan "( )" untuk yang ingin dikerakan dahulu, selain itu postfix dan prefix lebih mudah dimengerti oleh komputer sehingga dapat mempersingkat run time

cara mengevaluasi notasi infix :
*dikerjakan dengan string
4 + 6 * (5 – 2) / 3

4 + 6 * (5 – 2) / 3  cari precedence operator terbesar yaitu( )

4 + 6 * 3 / 3  cari precedence operator terbesar yaitu *

4 + 18 / 3  cari precedence operator terbesar yaitu  /

4 + 6  cari precedence operator terbesar yaitu +

10 (hasil)

cara mengevaluasi notasi postfix:

kerjakan dari kiri ke kanan

7   6   5   x   3   2   ^   –    +  , scan hingga sampai operator

7   6   5   x   3   2   ^   –    +  , hitung 6 x 5

7   30           3   2   ^   –    +  , lanjurkan scan hingga sampai operator

7   30           3   2   ^   –    +  , hitung 32

7   30           9             –    +  , lanjutkan scan hingga sampai operator

7   30           9             –    +  , hitung 30 – 9

7   21                                +  , scan lagi

7   21                                +  , hitung 7 + 24

28    , finish

 cara ini dapat ditulis dengan menggunakan stack:
- scan string dari kiri ke kanan
- jika ketemu operand push itu ke stack
- jika operator lakukan pop 2x
kompleksitas O(n^2)

Cara mengevaluasi prefix

+   7   –   x   6   5   ^   3   2

+   7   –   x   6   5   ^   3   2

+   7   –   x   6   5   9

+   7   –   x   6   5   9 

+   7   –   30           9

+   7   –   30           9

+   7   21

+   7   21

28
untuk algoritma bila menggunakan stack sama dengan postfix hanya saja scan dari kanan ke kiri

cara mengubah infix ke prefix
cari operator dengan tingkat tertinggi dan ubah ke prefix lakukan untuk semua operator
untuk lebih jelasnya dapat dilihat di contoh:

A + B – C x D ^ E / F

A + B – C x ^ D E / F

A + B – C x ^ D E  / F

A + B – x C ^ D E  / F

A + B – x C ^ D E / F

A + B – / x C ^ D E F

A + B – / x C ^ D E F

+ A B – / x C ^ D E F

+ A B – / x C ^ D E F

– + A B / x C ^ D E F  , prefix

Dept First Search(DFS)

merupakan algoritma untuk mentraversing atau mencari data dari graf atau root

dilakukan dengan konsep rekursif

berikut algoritma nya:

1. Masukkan root ke dalam stack dengan push
2. simpan isi elemen root ke stack
3. Hapus isi stack teratas dengan pop
4. Periksa apakah root pohon yang disimpan tadi memiliki cabang
5. Jika ya, push semua cabangl yang dibangkitkan ke dalam stack
6. Jika stack kosong stop(base case dari rekursif), tapi jika tidak kembali ke langkah dua

prosedur pengecekan DFS dapat diketik seperti:

void DFS_printPreOrder(simpul *root){

    if(root!=NULL){

        stack S;

        createEmptyStack(&S);

        push(root, &S);

 

        while(isStackEmpty(S) != 1){

            printf("%c ", S.top->elemen->huruf);

            simpul *node = peek(S);

            pop(&S);

 

            if(node->right != NULL){

                push(node->right, &S);

            }

            if(node->left != NULL){

                push(node->left, &S);

            }

        }

        printf("\n");

    }

}

Nama : Benedick Asdyo
NIM   : 2101631090