5 - Binary Search Tree - 2101711356 - Farhan Adji Nugroho

Binary Search Tree

Sub Topics :

Binary Search Tree :

1.     Operations : Search, Insertion, Deletion

2.     Program Examples

3.     Expression Tree Concept

4.     Create Expression Tree from Prefix

5.     Create Expression Tree from Postfix

6.     Create Expression Tree from Infix

7.     Prefix, Postfix, Infix, Traversal

Binary Search Tree Operations

Binary Search Tree memiliki operasi dasar yaitu :

1.     find(x) : untuk mencari nilai “x” di dalam binary search tree

2.     insert(x) : untuk menambah nilai “x” kedalam binary search tree

3.     remove(x) : untuk menghapus nilai “x” dari binary search tree

Operasi : Search

Karena binary search tree tidak bersifat linear jadi untuk pencarian data lebih mudah.

Contoh :

-        Jika key yang ingin kita cari adalah X.

-        Kita memulai dari bagian root pada tree

-        Jika root berisi X maka search berakhir dan pencarian ditemukan.

-        Jika nilai X lebih kecil dari root, maka cari secara rekursif pada sub-tree yang sebelah kiri, jika tidak ditemukan cari secara rekursif di sub-tree yang sebelah kanan.

Dan codenya adalah :

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);

}

Operasi : Insertion

Untuk melakukan insert dalam binary search tree dapat dilakukan dengan rekursif

Contoh :

Jika X adalah node baru yang ingin di input

-        Dimulai dari root

-        Jika nilai X kurang dari key node, maka input X ke dalam sub-tree kiri. Jika tidak, maka masukkan X ke dalam sub-tree kanan.

-        Ulangi hingga kita menemukan node kosong untuk menginput X ( X akan selalu menjadi leaf baru).

Dan algoritmanya adalah :

Step 1:    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 dengan Ilustrasinya seperti berikut :

Kita ingin menginput node baru bernilai 35.

Lakukan perbandingan muali dari root, jika nilai node baru lebih besar dari root maka liat perbandingan selanjutnya di sub-tree sebelah kanan, pada contoh di atas nilai node baru lebih besar dari pada root 35 > 30, maka di cek di node kanan selanjutnya apakah node baru  lebih besar daripada node tersebut.

Pada contoh di atas, node baru lebih kecil dari node yang ditunjuk 35 < 37, maka lakukan perbandingan selanjutnya di node child sebelah kiri dari node yang ditunjuk (37).

          

Lalu lakukan perbandingan lagi, pada BST tersebut node baru lebih besar daripada node yang ditunjuk 35 > 32. Maka node tersebut di insert pada node child sebelah kanan dari node yang di tunjuk (32).  Maka hasil akhirnya menjadi :

       

Operasi : Deletion

Ada 3 kemungkinan yang ada pada operasi delete pada binary search tree :

1.      Jika key yang ingin dihapus berada pada leaf, maka tinggal hapus saja node tersebut.

2.     Jika key yang ingin dihapus memiliki 1 child, hapus node tersebut dan hubungkan child ke parentnya dari parent child itu.

3.     Jika key yang ingin dihapus memiliki 2 children, lalu temukan child yang paling kanan dari sub-tree kirinya (node X), replace key dengan key P dan remove P secara rekursif (atau secara bergantian kita dapat memilih anak yang paling kiri dari sub-tree kanan).

Algoritmanya adalah :

Step 1: 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

Step 2: End

contoh operasi deletion dengan ilustasi :

jika kita ingin menghapus nilai 21 pada BST  dan nilai 21 berada pada leaf.

maka, tinggal hapus nilai 21 tersebut.

Jika kita ingin menghapus nilai 37 pada BST tersebut, maka turunan dari node tersebut sebelah kiri yang paling besar di hubungkan ke atas.

Lalu 35 pindah ke node tempat node yang di hapus (37).

Jika kita ingin menghapus node 30, maka cari nilai yang paling besar dari sub-tree kiri. Pada BST tersebut (26).

      

Lalu, 30 dihapus dan node 26 dipindahkan ke atas (posisi node 30).

     

Read More

4 - Introduction to Tree, Binary Tree, and Tree Expression - 2101711356 - Farhan Adji Nugroho

Introduction to Tree, Binary Tree, and Expression Tree

Sub Topics

Tree & Binary Tree:

-        Tree Concept

-        Binary Tree Concept

-        Type of Binary Tree

-        Property of Binary Tree

-        Representation of Binary Tree

-        Expression Tree Concept

-        Create Expression Tree from Prefix, Postfix and Infix

-        Prefix, Postfix and Infix Traversal

·       Konsep Tree

Tree adalah koleksi dari satu node atau lebih.

Keterangan :

Path – path mengacu pada urutan node di sepanjang garis pada tree.

Root – Node di bagian teratas tree disebut sebagai root. Hanya ada satu root per tree dan satu path dari root node ke node manapun.

Parent – setiap node kecuali root memiliki satu garis ujung ke atas node yang disebut parent.

Child – Node di bawah sebuah node tertentu yang dihubungkan dengan garis kebawah yang disebut child node.

Leaf – node yang tidak memiliki anak disebut sebagai leaf node.

Subtree – subtree merupakan turunan dari sebuah node.

Levels – level sebuah node mewakili generasi sebuah node. Jika root node pada tingkat 0, maka node anak berikutnya berada pada level 1, generasi berikutnya di tingkat 2, dan seterusnya.

Siblings­-node yang memiliki parent node sama disebut sebagai sibling.

Degree – adalah total subtree dari sebuah node.

Height/Depth-  adalah tingkat maksimum degree dari sebuah nodes dalam tree

jika ada garis yang menghubungkan p dengan q, kemudian p disebut sebagai ancestor dari q, dan q adalah descendant dari p.

·       Konsep Binary Tree

-Sebuah pengorganisasian secara hirarki dari beberapa buah node, dimana masing-masing node tidak memiliki child lebih dari dua.

-Implementasi binary tree bisa dilakukan menggunakan struktur data linked list. Masing-masing node terdiri dari tiga bagian yaitu sebuah data/info dan dua buah pointer yang dinamakan pointer kiri/kanan.

           

Tipe dari Binary Tree

-        Perfect Binary tree

Adalah binary tree yang setiap levelnya memiliki depth yang sama.

-        Complete Binary Tree

Adalah binary tree dimana setiap level, kecuali yang terakhir terisi penuh, dan semua node terisi dikiri sebanyak mungkin.

Skewed Binary Tree

Adalah binary tree dimana setiap node memiliki paling banyak satu child.

           

-        Balanced Binary Tree

Adalah binary tree dimana tidak ada leaf yang jauh dari root daripada leaf lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda).

           

Jumlah maksimal node

Jumlah maksimal node pada setiap level adalah 2ⁿ

Jumlah maksimum dari node pada binary tree adalah 2ⁿ⁺¹-1

Jumlah maksimum node dari binary tree of height 3. = 1+2+4+8 = 2⁰ + 2¹+2²+2³=2⁴-1 = 15.

           

Jumlah minimum height dari binary tree pada n node adalah 2log(n) dan jumlah maksimum height pada binary tree of n node adalah n-1

Skewed binary tree memiliki maximum height.

·       Representasi Binary Tree

-        Implementasi menggunakan array

Index on array represents node number

Index 0 is Root node

Index Left Child is 2p + 1, where p is parent index

Index Right Child is 2p + 2

Index Parent is (p-1)/2

-        Impelementasi menggunakan Linked List

struct node {

     int data;

     struct node *left;

     struct node *right;

     struct node *parent;

};

struct node *root = NULL;

·       Expression Tree Concept

Prefix               : *+ab/-cde

Postfix             : ab+cd-e/*

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

Kita akan menggunakan struktur ini untuk setiap node di tree :

struct tnode {

     char chr;

     struct tnode *left;

     struct tnode *right;
};

ini adalah binary tree.

·       Create Expression Tree from Prefix

Kita dapat membuat expression tree dari prefix dengan rekursif.

char s[MAXN];

int  p = 0;

void f(struct tnode *curr) {

     if ( is_operator(s[p]) ) {

           p++; curr->left  = newnode(s[p]);

           f(curr->left);

           p++; curr->right = newnode(s[p]);

           f(curr->right);

     }
}

Main function

struct tnode *root = newnode(s[0]);

f(root);

·       Prefix Traversal

melakukan prefix atau postfix di expression tree sangat simpel.

void prefix(struct tnode *curr) {

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

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

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

dalam prefix, kita harus di print/process sebelum child diproses.

·       Postfix Travesal

void postfix(struct tnode *curr) {

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

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

}

Dalam postfix, kita harus print/process setelah child diproses.

·       Infix Traversal

sebagai contoh * + a b c didalam prefix akan dikodekan dalam infixx sebagai a + b * c dengan kode sebelumnya, sedangkan infix adalah ( a + b ) * c.

a + b * c : b dikalikan dengan c dan kemudian ditambah a

( a + b ) * c : a di tambahkan dengan b dan kemudian dikali dengan c.

Prefix               : *+abc

Postfix             : ab+c*

Wrong infix     : a+b*c

Correct Infix    : (a+b)*c

Read More