Selasa, 27 Maret 2018

5-Binary Search Tree-2101632055-YOEL JORDANIO IMANUEL

Binary Search Tree

Sebelum kita belajar lebih lanjut lagi tentang Binary Search Tree atau sering disingkat BST.  Bapak Henry Chong , dosen saya , mereview ulang apa itu binary tree.

Jadi, Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimaldua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut
tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.


Berikut adalah contoh dari Binary Tree :

Image result for contoh binary tree



Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. BST maksimal mempunyai anak hanya 2 node.





Dosen saya menjelaskan tujuan dari binary search tree(BST) adalah untuk memudahkan program dalam melakukan proses pencarian. Jika kita ingin menghapus node di angka 8 maka kita akan menggantinya dengan angka yang paling besar di leaf kiri atau dengan angka paling kecil di leaf kanan.



Ini adalah graf, dan ini bukan binary search tree, karena rootnya (angka 2) mempunya tiga node ,yaitu 1,4,3 yang berarti ia mempunyai loopingan.
Image result for apa itu grap tree

Syarat Aturan  Dari Binary Search Tree :

  • Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
  • Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :

  • PreOrder : Print data, Cek ke kiri, Cek ke kanan
  • InOrder : Cek ke kiri, print data, Cek ke kanan
  • Post Order :Cek ke kiri, Cek ke kanan, print data



Berikut saya sarankan untuk membuka video ini untuk mendalami ilmu yang lebih dalam lagi.









Berikut saya lampirkan codingan tentang BST :


#include<iostream>
#include<cstdlib>
using namespace std;

class BinarySearchTree{
      private:
      struct node{
             node* left;
             node* right;
             int data;
      };
      node* root;
      
      public:
             BinarySearchTree(){
             root = NULL;
             }
             
             bool isEmpty() const {return root==NULL;}
             struct node* newNode(int data){
             struct node* node = new(struct node);
                    node->data = data;
                    node->left = NULL;
                    node->right = NULL;
                    return(node);
             }
                    
             struct node* insert(struct node* node, int data){
                    if(node == NULL){
                             return(newNode(data));
                    }
                    else{
                         
                    if (data <= node->data) node->left = insert(node->left, data);
                    else node->right = insert(node->right, data);
                    return(node);
                    }
             }
             void insert(int data){
                  if(isEmpty()){
                                 root = newNode(data);
                                      }else{
                                            insert(root,data);
                                      }
                                 }
                                 
             void printTree(struct node* node){
                  if(node == NULL)return;
                  /*InOrder
                  printTree(node->left);
                  cout<<" "<<node->data;
                  printTree(node->right); 
                  
                  /*PreOrder
                  cout<<" "<<node->data;
                  printTree(node->left);
                  printTree(node->right);*/
                  
                  /*PostOrder
                  printTree(node->left);
                  printTree(node->right);
                  cout<<" "<<node->data;*/
             }
             void callPrintTree(){
                  printTree(root);
             }
             
             int callLookup(int target){
                 return lookup(root,target);
                 }
                 int lookup(struct node* node,int target){
                     if(node==NULL) return 0;
                     
                     if(node->data == target)return 1;
                     else{
                          if(target < node->data)
                          return lookup(node->left,target);
                          else
                          return lookup(node->right,target);
                          }
                     }
              
             int callMin(){
                 return min(root);
                 }
                 int min(struct node* node){
                     if(node->left==NULL) return node->data;
                     else return min(node->left);
                     }
                     
             int callMax(){
                 return max(root);
                 }
                 int max(struct node* node){
                     if(node->right==NULL)return node->data;
                     else return max(node->right);
                     }
                     
             int callDept(){
                 return dept(root);
                 }
                 int dept(struct node* node){
                     if(node == NULL) return 0;
                     else{
                          int l = dept(node->left);
                          int r = dept(node->right);
                          if(l < r) return 1 + r;
                               else return 1 + l;
                                     
                               }
                          }
                 
};


int main(){
    BinarySearchTree b;
    b.insert(5);
    b.insert(3);
    b.insert(9);
    b.insert(1);
    b.insert(4);
    b.insert(6);
    //b.callPrintTree();
    cout<<b.callLookup(4)<<endl; //output : 1
    cout<<b.callLookup(2)<<endl; //output : 0
    cout<<b.callMin()<<endl; //output : 1
    cout<<b.callMax()<<endl; //output : 9
    cout<<b.callDept()<<endl; // output : 3
    
  getchar();
    return 0;}





















Yoel Jordanio Imanuel
2101632055








Selasa, 20 Maret 2018

4-Introduction to Tree, Binary Tree And Expression Tree-2101632055-YOEL JORDANIO IMANUEL

Introduction to Tree, Binary Tree And Expression Tree



DEGREE of TREE = 3
DEGREE of C = 2
HEIGHT = 3
PARENT of C = A
CHILDREN of  A = B, C, D
SIBILING of F = G
ANCESTOR of F = A, C
DESCENDANT of C = F, G



Tree Concept

1. Node at the top is called as root.
2. A line connecting the parent to the child is edge.
3. Nodes that do not have children are called leaf.
4. Nodes that have the same parent are called sibling.
5. Degree of node is the total sub tree of the node.
6. Height/Depth is the maximum degree of nodes in a tree.
7. If there is a line that connects p to q, then p is called the ancestor of q, and q is a descendant of p.


Binary Tree Concept 

- Binary tree is a rooted tree data structure in which each node has at most two children.

- Those two children usually distinguished as left child and right child.

- Node which doesn’t have any child is called leaf.



A sample of binary tree
of 9 nodes, rooted on
node which contains 18.

Leaves are nodes which
contain 9, 12, 10 and 23.













Type of Binary Tree

PERFECT binary tree is a binary tree in which every level are at the same depth.

COMPLETE binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfect binary tree is a complete binary tree.

SKEWED binary tree is a binary tree in which each node has at most one child.

BALANCED binary tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).



PERFECT Binary Tree





COMPLETE Binary Tree
A perfect binary tree is also a complete binary tree.




SKEWED Binary Tree










Property of Binary Tree
Maximum number of nodes on level k of a binary tree is 2k.

Maximum number of nodes on a binary tree of height h is 2h+1 - 1.
Maximum nodes
of a binary tree of
height 3
= 1 + 2 + 4 + 8
= 20 + 21 + 22 + 23
= 24 – 1
= 15




Representation of Binary Tree
Implementation using linked list

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



struct node {
int data;
struct node *left;
struct node *right;
struct node *parent;
};

struct node *root = NULL;


Expression Tree Concept
Recall our discussion on stack application about arithmetic notation (session 6).

struct tnode {
char chr;
struct tnode *left;
struct tnode *right; };

It is a binary tree.
Create Expression Tree from Prefix
We can create an expression tree from a prefix by recursive.


Selasa, 13 Maret 2018

3-Linked List Implementation II-2101632055-YOEL JORDANIO IMANUEL

Linked List Implementation II 


Stack Concept
Stack is a linear data structure which can be implemented by either using an array or a linked list.
The elements in a stack are added and removed only from one end, which is called the top.
The data are stored in Last In First Out (LIFO) way.


Array Representation
Stack has two variables:
TOP which is used to store the address of the topmost element of the stack
MAX which is used to store the maximum number of elements that the stack can hold
If TOP = NULL, then indicates that the stack is empty
If TOP = MAX – 1, then the stack is full


   0    1   2   3    4   5    6    7   8
TOP=4, insertion and deletion will be done at this position

Linked List Representation
Technique of creating a stack using array is easier, but the drawback is that the array must be declared to have some fixed size.
In a linked stack, every node has two parts:
One that stores data
One that stores the address of the next node
The START pointer of the linked list is used as TOP
All insertions and deletions are done at the node pointed by the TOP
If TOP = NULL, then it indicates that the stack is empty
Stack Operations
push(x) : add an item x to the top of the stack.
pop() : remove an item from the top of the stack.
top() : reveal/return the top item from the stack.





Stack Applications
There are several applications using stack data  struct :

Prefix : operator is written before operands
Infix : operator is written between operands
Postfix : operator is written after operands
Infix, Postfix, and Prefix Notation

Why do we need prefix/postfix notation?
Prefix and postfix notations don’t need brackets to prioritize operator precedence.
Prefix and postfix is much easier for computer to evaluate.
Evaluation: Infix Notation
Evaluate a given infix expression: 4 + 6 * (5 – 2) / 3.

To evaluate infix notation, we should search the highest precedence
operator in the string.
4 + 6 * (5 – 2) / 3 search the highest precedence operator, it is ( )
4 + 6 * 3 / 3 search the highest precedence operator, it is *
4 + 18 / 3 search the highest precedence operator, it is  /
4 + 6 search the highest precedence operator, it is +
10

Evaluation: Postfix Notation
Manually
Scan from left to right
7   6   5   x   3   2   ^   –    + , scan until reach the first operator
7   6   5   x   3   2   ^   –    + , calculate 6 x 5
7   30           3   2   ^   –    + , scan again until reach next operator
7   30           3   2   ^   –    + , calculate 32
7   30           9             –    + , scan again to search next operator
7   30           9             –    + , calculate 30 – 9
7   21                                + , scan again
7   21                                + , calculate 7 + 24
28 , finish



Evaluation: Postfix Notation
String Stack

4 6 5 2 – * 3 / +
4 6 5 2 – * 3 / + 4 push(4)
4 6 5 2 – * 3 / + 4 6 push(6)
4 6 5 2 – * 3 / + 4 6 5 push(5)
4 6 5 2 – * 3 / + 4 6 5 2 push(2)
4 6 5 2 – * 3 / + 4 6 3 pop 2, pop 5, push(5 – 2)
4 6 5 2 – * 3 / + 4 18 pop 3, pop 6, push(6 * 3)
4 6 5 2 – * 3 / + 4 18 3 push(3)
4 6 5 2 – * 3 / + 4 6 pop 3, pop 18, push(18 / 3)
4 6 5 2 – * 3 / + 10 pop 6, pop 4, push(10)   the result



Evaluation: Prefix Notation
Manually
Scan from right to left

+   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


Repeat until finish
Conversion: Infix to Postfix Notation
Manually

A + B – C x D ^ E / F   , power has the highest precedence
A + B – C x D E ^ / F   , put ^ behind D and E
A + B – C x D E ^ / F   , x  and / have same level precedence
A + B – C D E ^ x / F   , put x at the end
A + B – C D E ^ x / F   , continue with the same algorithm till finish
A + B – C D E ^ x F /
A + B – C D E ^ x F /
A B + – C D E ^ x F /
A B + – C D E ^ x F /
A B + C D E ^ x F / –   , this is the Postfix notation


Algorithm:
Scan the string from left to right, for each character in the string:
If it is an operand, add it to the postfix string.
If it is an open bracket, push it into stack.
If it is a close bracket, pop the stack until you found an open bracket. Add each popped element to the postfix string.
If it is an operator, pop while the stack’s top element has higher or equal precedence than the scanned character. Add each popped element to the postfix string. Push the scanned character into stack.
After you have scanned all character, pop all elements in stack and add
them to postfix string.

Conversion: Infix to Postfix Notation
String Stack Postfix String

 4 + 6 * (5 – 2) / 3
 4 + 6 * (5 – 2) / 3 4
 4 + 6 * (5 – 2) / 3 + 4
 4 + 6 * (5 – 2) / 3 + 4 6
 4 + 6 * (5 – 2) / 3 + * 4 6
 4 + 6 * (5 – 2) / 3 + * ( 4 6
 4 + 6 * (5 – 2) / 3 + * ( 4 6 5
 4 + 6 * (5 – 2) / 3 + * ( – 4 6 5
 4 + 6 * (5 – 2) / 3 + * 4 6 5 2
 4 + 6 * (5 – 2) / 3 + * / 4 6 5 2 –
 4 + 6 * (5 – 2) / 3 + / 4 6 5 2 – *
 4 + 6 * (5 – 2) / 3 + / 4 6 5 2 – * 3
 4 + 6 * (5 – 2) / 3 4 6 5 2 – * 3 / +



Algorithm:
Search for the operator which has the highest precedence
Put that operator before the operands
Repeat until finish

Conversion: Infix to Prefix Notation
Manually

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 ,

It is quiet similar with the conversion from Infix to Postfix.
You can learn it by yourself


Depth First Search
Depth First Search (DFS) is an algorithm for traversing or searching
in a tree or graph.
DFS has many applications, such as:
- Finding articulation point and bridge in a graph
- Finding connected component
- Topological sorting
- etc.
DFS can be implemented by a recursive function or an iterative
procedure using stack, their results may have a little differences on
visiting order but both are correct.

Depth First Search
Algorithm:

Prepare an empty stack
Push source/root into stack
Mark source/root
While stack is not empty
Pop an item from stack into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into stack
Depth First Search




Other Stack Applications Stacks are widely used to:
- Reverse the order of data
- Convert infix expression into postfix
- Convert postfix expression into infix
- Backtracking problem
- System stack is used in every recursive function
- Converting a decimal number into its binary equivalent

Queue
Queue is an important data structure which stores its elements in an ordered manner
Example:
People moving on an escalator. The people who got on the escalator first will be the first one to step out of it.
People waiting for a bus. The person standing in the line will be the first one to get into the bus
Luggage kept on conveyor belts
Cars lined for filling petrol
Cars lined at a toll bridge



Linked List Representation
Similar with stack, technique of creating a queue using array is easy, but its drawback is that the array must be declared to have some fixed size.
In a linked queue, every element has two parts
One that stores the data
Another that stores the address of the next element
The START pointer of the linked list is used as the FRONT
All insertions will be done at the REAR, and all the deletions are done at the FRONT end.
If FRONT = REAR = NULL, then it indicates that the queue is empty


QUEUE

Queue Operations
push(x) : add an item x to the back of the queue.
pop() : remove an item from the front of the queue.
front() : reveal/return the most front item from the queue.


Circular Queue Queue Applications

Deques
Two variants of a double-ended queue, include:
Input restricted deque
In this dequeue insertions can be done only at one of the dequeue while deletions can be done from both the ends.
Output restricted deque
In this dequeue deletions can be done only at one of the dequeue while insertions can be done on both the ends.

Priority Queue
A priority queue is an abstract data type in which the each
element is assigned a priority.
The general rule of processing elements of a priority queue
can be given as:
An element with higher priority is processes before an element with lower priority
Two elements with same priority are processed on a first come first served (FCFS) basis


Deletion:
Deletion is a very simple process in this case. The first node of the
list will be deleted and the data of that node will be processed first


Breadth First Search
Breadth First Search (BFS) like DFS is also an algorithm for
traversing or searching in a tree or graph.
We start at the root of the tree (or some arbitrary node in
graph) and explore all neighboring nodes level per level until
we find the goal.
BFS has many applications, such as:
Finding connected component in a graph.
Finding shortest path in an unweighted graph.
Ford-Fulkerson method for computing maximum flow.
etc.
Breadth First Search
The difference between DFS and BFS iterative
implementation is only the data structure being used.

DFS uses stack while BFS uses queue.
Breadth First Search
Algorithm:

Prepare an empty queue
Push source/root into queue
Mark source/root
While queue is not empty
Pop an item from queue into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into queue
Breadth First Search