Binary Search Tree

A.     Binary Search Tree

Binary search tree (BST) are data structure with binary tree concept or known as sorted version of binary tree are made to help fast searching, rapid sorting and easy insertion and deletion.

There are some rules for BST:

·        Every node has a value

·        Left value will always smaller than the root

·        Right value will always bigger than the root

·        Right tree or left tree can be another root or can have child, so BST have recursive function.

These rules are there to made searching process efficient.

B.     Binary Search Tree Operation

BST have three basic operation

1.      Find/Searching

Because BST is sorted searching in BST is easy. We only need to use some rules.

1.      Start searching at root.

2.      If the root contains the value, then we can return the value and stop searching process.

3.      If the value is less than root key then search recursively on left sub tree until the value is found, otherwise if the value is higher than recursively search on right sub tree.

2.      Insertion

As we know inserting is inputting new data into the tree. Insertion in BST is done recursively.

1.      We give the value we want to input.

2.      We begin at root.

3.      If the root value is lower then the value then goes into left sub tree and make the value as root value, otherwise go into right sub tree.

4.      Repeat until we found an empty node to put new value.

3.      Remove/deletion

There are 3 cases which should be considered:

1.      If the deleted node is in a leaf, just delete that node

2.      If the deleted node is in a node which has one child, delete that node and connect its child to its parent

3.      If the deleted node is in a node which has two children, find the right most child of its left sub tree (node P), replace its with P and remove P recursively. (or alternately you can choose the left most child of its right sub tree)

Hashing and Binary Tree

1.  Hashing

Hashing are a transformation from string to a shorter value or a value that represent that string. It used to take index or item in database because of the shorter time for finding item using hash key.

Other than faster data take. Hashing used in encrypt digital signature. Digital signature modified with hash function into hash value and receipt to receiver. using the same hash function, receiver will get the message-digest and will compare it with received message-digest. (they must be identical.)

Hash function used for indexing value or original key and will used every time the data will be taken. So, hashing will always operate in one way and don’t need to “reverse engineer” hash function with analysing hash value.

There are many ways to hash a string into a key. The following are some of the important methods for constructing hash functions.

•        Mid-square

•        Division (most common)

•        Folding

•        Digit Extraction

•        Rotating Hash

2.   Hash Table

Hashing can be used to make hash table thought hash function. Hash table is a table where we store a data temporary for efficiency data searching. Hash table will have index of the table in from of hashed key while the value is the original string.

The size of hash table is usually several orders of magnitude lower than the total number of possible string, so several string might have a same hashed-key. If that happen that will induce a collision because two data will have a same key.to resolve it we can use one of this method:

A.   Close Hashing

Close Hashing use empty memory without using memory outside of array used. Close hashing search new address if the aimed address is already filled. There are 3 way to search for another address.

a.   Linear Probing,

If the array is filled, linear probing will check next array until get empty array. Linear Probing use ((h+1) mod m) equation.

b.   Quadratic Probing

                Quadratic Probing search new address using more complex quadratic                      equation. There is no fixed equation for this probing you can make the                    formula you will use.

                  Example:

                  h,(h+i²)mod m,(h-i²)mod m, … ,(h+((m-1)/2)²)mod m, (h-((m-1)/2)²)mod m

                  with i = 1,2,3,4, … , ((m-1)/2).

                  This mean you will check (h+1)mod m, if filled then check (h-1)mod m, if                      filled check(h+1)mod m, if filled to check(h+4)mod m, and continue until                      get empty array.

c.    Double Hashing

Double Hashing use second hash function to save collided key value. Second hash function used when the original hash function is filled with hash function itself. But this method need more array address than the data and need more memory to minimize collision.

B.    Open Hashing

Basically, open hashing is making the value of hash table into array of pointer that followed by linked list, with the head point to the array of pointer and following data is connected to the head. The downside is this method will make a long LinkedList if the data override each other.

3.     Binary Tree

          A tree is a non-linear data structure that represents the hierarchical relationships among the data objects using connected node from up to down. In tree each node will have maximum two child(node) connected with the node.

          They are named left and right. The node in the tree doesn’t have to be stored contiguously and can be stored anywhere and linked by pointers. Binary tree is a tree that have maximum 3 level of root (upper node). Binary tree is saved as implicit in array, and this method will save memory if you make a full binary tree.

          In binary tree the child node will be found at i+1, and i+2 index, even when the father (upper node) will found at ((i-1)/2)

A.    Element of binary tree

·       Node

·       Root is the upper node

·       Leaf is root without children

·       Sibling is two node who have same parent

·       Degree of node is the total sub tree of the node.

·       Height/Depth is the maximum degree of nodes in a tree.

·       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.

    B.    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”).

Stack and Queue

1.      Stack

Stack is one of data structure concept that store data in orderly way. For stack the data order is LIFO or Last In First Out manner.  It’s was like you see a pile of chair it’s was make with chair stacked from the bottom one but when you need a chair you take the last (upper one) first.

There are 2 way you can make a stack. The first one is using array and the second is using linked list. Even thought using array is easier when using array, we need to declare a fixed size, but linked list doesn’t need to declare size and can keep make a new space.so when we don’t know the size of stack we make it using linked list.

   a.      Stack Operation

There are 3 operation for stack:

-        Push(x)  : push is operation to add x to top of the stack.

-        Pop()      :pop is operation to remove an item from the top of the stack.

-        Top()      :top is operation to return the top from the stack.

We must remember to use a same push and pop so if you push from head you need to pop from head to because LIFO order.

   b.      Stack Application

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

-        Depth First Search.

   2. Infix, Postfix, and Prefix Notation

Infix, Postfix, and Prefix Notation are one of stack application. For simple they can be explained like:

        -        Prefix     : operator is written before operands

        -        Infix       : operator is written between operands

        -        Postfix   : operator is written after operands

3.      Queue

Queue is like stack both are concept that store data in an order. but in queue we use FIFO or First In First Out order. If stack was like a pile of chair queue was like a line for restaurant if you line first, you can go in first.

               To make queue we use the same ways with stack. We can make queue using array and using linked list. Same with stack, using array are easier but because the size is fixed, we need to use linked list if we don’t know the size.

   a.      Queue Operation

 There are 3 operation for queue:

-        Push(x) :push is operation to add x to the back of the queue.

-        Pop()     :pop is operation to remove an item from the front of the stack.

-        Top()     :top is operation to return the front from the stack.

If stack must use the same push and pop in queue, we must use different push and pop so if you push the front you must pop the back. It was because the first in will go out first (FIFO).

   b.      Queue Application.

-        Deques

-        Priority Queues

-        Breadth First Search

   c.      Type of Queue

-        Circular queue

Circular queue is queue where the first index is connected with the last index.so first index will come after last index.

-        Deques

Deques is queue where we do deletion and insertion from both side. There are 2 type of queue, input restriction and output restriction deque. Input restriction mean deletion can happen at both side but insertion can only happen in one side and the output restriction is the opposite.

-        Priority queue

Priority queue is queue where we assign an priority to each element. Queue will procced the highest priority first, if there are same priority it will procced with First Come First Served basis.

4.      Deep first search and breadth first search
   a.      Deep First Search
              Deep first search (DFS) is algorithm for traversing in tree or graph. DFS start at the root
         of the tree and explore ass far as possible along each branch before backtracking.
         
   b.Breadth First Search
              Breadth first search (BFS) like DFS is also an algorithm for traversing or searching in a tree or graph. BFS start at the root of the tree and explore all neighboring nodes level per level until we find   the goal.
   

      The difference between both are only in the data structure concept that used. DFS use  stack while BFS use queue.