[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