[2018] 5 - Binary Search Tree - 2101673042 - Kevin Surya Pranata

Welcome back to my Blog
Now I want to explain you about Binary Search Tree

But before that, have you heard about graph? Binary Tree ?
What are they ? Let just started

Let just recall what we have in tree
Root which is the most top node
Leaf which the the most lowest node
Ancestor which is all the node above it's node
Descendant which is all node below it's node
Child which is (all) node right below it's node

Now what is graph ?
Graph is tree but some node has more than one parent

Like this example








Now let's talk about Binary Tree.
Binary Tree that has exactly one root node and have at most 2 child node

Now we shall discuss about Binary Search Tree.
It's like binary tree, has exactly one root node, and each parent has exactly at most 2 node
But it has some following rules applied on the tree
Basically all child at left is not greater than the parent value
and all child at right is greater than the parent value

 Above is an example of binary search tree with our following rules

Now, in BST we have some operations
find or search,
insert or push, and
remove or pop
Because we applied rules on our tree and it becomes BST, finding or searching in BST is quite easy

Now we talk about search
Let say we want to search value X
We start to find from our root
Now if our root if not same as X
Then if X is less than root we search recursively on left (child) sub tree
Else if our X is greater than the root we recursively search on right (child) sub tree
and so on and till you find the X

we have this following code
struct node* search(struct node *curr,int X){
  if(!curr) return NULL;
  if(X == curr->data) return curr;
  if(x < curr->data) return search(curr->left,X);
  return search(curr->right,X);
}

Now let's talk about operations <Insertion>
In BST insertion can be done by recursive with applying same main rules
Let's start by set our root node key as
now we begin at root and we ask question, is it greater or not
if it greater than we insert it into right child from it's parents, starting the question
do loop until you found an empty node to put X
(X will always be a new leaf)
Here I show you algorithm of insertion in BTS

Now in this case we want to add 35 to our node

(this picture's purely adapted from our shared resources)

Then we ask question is it greater or not from our parent

In this case 35 (new node) > 30 (root<parent>)

Then we continue search to the right child

Now we check the right node which is our cure asking question (37)
is it greater or leaser than our new node (35)
we know that 37 is > 35 in other words 35 < 37 then we continue asking into the next left node which is (32)

Nah you see that it's the leaf of the tree, means that it's almost there !!
Asking final question before putting it new node into our tree
is it greater or leaser than our current asking ? 32 < 52 || 52 > 32 means we put the next right child from current (32) is new node (35)

Now we have this new tree [:

Now don't waste any time, let me explain another operations Deletion !!!
There are three(3) cases which should be minded and considered:
is the key in leaf ?
is the key has one child ?
is the key has two child ?
What should you do ,  LOL. Easy
if it's on the leaf just delete that node (free)
if it's has one child then just connect the child node into the parents node
if it's has two child , then find the right most child on it's left sub tree (let say it's node P)
then replace it's key (node want to delete) with P's key and remove P recursively.
(for alternate you can choose the left most child of its right sub tree) [;

here it's algorithn

you can use this algorithm in case you want to delete a node from BTS

Let's see this following example

in this example we want to delete(21)

what should we do? According to our algorithm if it's on leaf of the tree then you just 

free(it's node) as simple as that.

Now let say we have this example 

in this case we want to delete (37) from our tree

according to algorithm (35) should take over (37) from it's place

how we done that??

by doing overwrite (swap) and then free it's old (35) on the leaf

now we have this example

now let say we want to delete our root

nah found the number that want to overtake it's root

it's the highest number in left child which is (26)

and then swap and reconnect all the tree recursively to it's parents? 

Eh maybe I explain it wrong but, you may see this picture

that all above is code you may use to make BTS operation

resources : shared material binusmaya.ac.id
google.com

regards author
Kevin Surya Pranata
2101673042
In Math We Unite

[2018] 4 - Introdicton to Tree_ Binary Tree and Expression Tree - 2101673042 - Kevin Surya Pranata

Welcome Back ^_^
Today we shall discuss about Tree

In Tree we will learn about 

-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

Let's just start

Tree Concept

A tree is recursively defined as a set of one or more nodes where one node is designated as the root of the tree and all the remaining nodes can be partitioned into non-empty sets each of which is a sub-tree of the root.

 

There are :

Root Node , which is the topmost node in tree . Our root node in that picture is A

Edge . Line that connecting the parent to the child

Sub-trees . If the root node is not NULL , then the trees T1 ,T2 , T3 are called sub trees of A

Leaf node , is a node that has no children

Path , a sequence of consecutive edges . For example path from node A to I is A,D,I

Ancestor node , is all node that have connected edges above it's node 

                            For example ancestor of G is C,G

Descendant node , is all node that have connected edges below it's node

                            For example descendant of A is B,C,D,E,F,G,H,I,J,K

Level number . Level is started from ROOT which is Zero (0).  All children nodes has +1 level number from it's parents

                           For example level from node K is 3

Degree . Degree of a node is equal to the number of children that a node has. The degree of a leaf node is zero.

In-degree .  In-degree of a node is the number of edges arriving at that node.

Out-degree . Out-degree of a node is the number of edges leaving that node.

Now we will discuss about Binary Tree

Binary tree is a rooted tree data structure in which node has at MOST two (2) children
Those two children usually known as left child and right child.
Node which doesn't have any child is called leaf
Let examine this tree

From this tree we known that this tree has 9 nodes, and it's root is 18
This tree has 4 leaves which is node with number 9 - 12 - 10 - 23

There are four type of Binary Tree

Perfect Binary Tree

Complete Binary Tree

Skewed Binary Tree

Balanced Binary Tree

Perfect Binary Tree is a binary tree in which every level are at the same depth
this is the picture


Complete Binary Tree is like Perfect Binary Tree , but except possibly the last is don't have child, 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 every node has exactly just one child
This the picture of Skewed one






Balanced Binary Tree is a binary tree in which no leaf is much farther away from the root than any other leaf. In other words means that it's look balanced for a reason




 After you saw this following tree above us. What do you think?
We can count on maximum numbers of nodes on a level.
With formula Max on level k = 2^k
On level 0 = 2^0 = 1
On level 1 = 2^1 = 2
On level 2 = 2^2 = 4
On level 3 = 2^3 = 8
On level 4 = 2^4 = 16
and so on :)

Now if we'd like to count total number of nodes on a binary tree of an height let say n
How do we count that?
Well as you can see
Level 0 = 1 = 2^0
Level 1 = Level 0 + 2^1 = 1 + 2 = 3 = 4 - 1 =2^2 - 1
Level 2 = Level 1+ 2^2 = 3 + 4 = 7 = 8 - 1 =2^3 - 1
Level 3 = Level 2 + 2^3 = 7 + 8 = 15 = 2^4 - 1
on Level n then = 2^(n+1) - 1
that's the formula

Now we will learn about representation of binary tree in array 

Let examine this picture




With this following manners we can transpose any tree into array correctly and wisely not to do so
but let we try
Index 0 is reserved for the root node
Now the index of left child is 2p+1 , p is the parent index
Meanwhile the index of right child is 2p+2
If you'd like to find the index of any child is (p-1)/2  with round down

Now we will learn about representation binary tree using linked list

please examine this picture again :)

As you can see. Each node has 3 links and has a value let say an int data
so it has code declaration like this
struct node{
  int data;
  struct node *left;
  struct node *right;
  struct node *parent;
};

struct node *root = NULL;
//nah this one is to declare that if our tree is empty then we set the root NULL

Now we want to discuss about Expression Tree Concept
Here we want to discuss such that arithmetic notation using expression tree

Let examine this tree

In Infix it's actually (a+b)*((c-d)/e)
If we manage to make that to prefix and postfix
Prefix : *+ab/-cde
Postfix : ab+cd-e/*

If you wondering the structure code of this tree
struct tnode{
  char chr; 
  struct tnode *left;
  struct tnode *right;
} 

Now if we want to create an expression tree from a prefix, we can use recursive
this is the code

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

char s[MAXN];
int p = 0 ;
void f(struct tnode *curr){
 if(is_operator(s[p])){
  p++; curr->next = newnode(s[p]);
  f(curr->left);
  p++; curr->right = newnode(s[p]);
  f(curr->right);
 }
}

Now. Doing a prefix or postfix traversal in an expression tree is simple
This code will help you understand

void prefix(struct tnode *curr){
 print("%c",curr->chr);
 if(curr->next != 0 ) prefix(curr->left);
 if(curr->next != 0 ) prefix(curr->right);
}

take a note : you have to print / process before its child are processed
BUT in postfix

void postfix(struct tnode*curr){
 if(curr->next != 0 ) prefix(curr->left);
 if(curr->next != 0 ) prefix(curr->right); 
 print("%c",curr->chr);
}

in postfix, you have to print / process after is child have been processed

Now I will show you how to make infix, but remember with infix, computer and user
may found ambiguity , then we shall use brackes to help understanding

void infix(tnode *curr) {

  if ( is_operator(curr->chr) ) putchar( '(' );

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

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

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

  if ( is_operator(curr->chr) ) putchar( ')' );

}

Imagine  if we have * + a b c

The resulting infix we have is ((a+b)*c)     [:

Now I want to share formula to use if you'd like to have any  postfix or prefix [?]

Have a good day everybody !