Data Structures and Algorithms 2074

Binary Search Tree

A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

• All keys in the left sub-tree of the root are smaller than the key in the root node
• All keys in the right sub-tree of the root are greater than the key in the root node
•  The left and right sub-trees of the root are again binary search trees

Example:

Given the following sequence of numbers,

        14, 4, 15, 3, 9, 14, 18

The following binary search tree can be constructed:

Algorithm to search the element in BST

void BinSearch(struct bnode *root , int key)

{

    if(root == NULL)

    {

        printf(“The number does not exist”);

        exit(1);

    }

    else if (key == root->info)

    {

        printf(“The searched item is found”):

    }

    else if(key < root->info)

        return BinSearch(root->left, key);

    else

        return BinSearch(root->right, key);

}

Algorithm to insert the element in BST

void insert(struct bnode *root, int item)

{

    if(root=NULL)

    {

        root=(struct bnode*)malloc (sizeof(struct bnode));

        root->left=root->right=NULL;

        root->info=item;

    }

    else

    {

        if(item<root->info)

            root->left=insert(root->left, item);

        else

            root->right=insert(root->right, item);

    }

}

E.g.

Algorithm to delete the element in BST

struct bnode *delete(struct bnode *root, int item)

{

    struct bnode *temp;

    if(root==NULL)

    {

        printf(“Empty tree”);

        return;

    }

    else if(item<root->info)

         root->left=delete(root->left, item);

    else if(item>root->info)

         root->right=delete(root->right, item);

    else if(root->left!=NULL &&root->right!=NULL)   //node has two child

    {

        temp=find_min(root->right);

        root->info=temp->info;

        root->right=delete(root->right, root->info);

    }

    else

    {

        temp=root;

        if(root->left==NULL)

             root=root->right;

        else if(root->right==NULL)

             root=root->left;

        free(temp);

    }

    return(temp);

}

Finding minimum element function:

struct bnode *find_min(struct bnode *root)

{

    if(root==NULL)

         return0;

    else if(root->left==NULL)

         return root;

    else

         return(find_min(root->left));

}

E.g.

1. Deleting leaf Node

2. Deleting node with right child

3. Deleting node with left child

4. Deleting a node having both right and left child

Circular linked list is a sequence of elements in which every element has link to its next element in the sequence and the last element has a link to the first element in the sequence.

Circular linked lists can be used to help the traverse the same list again and again if needed. A circular list is very similar to the linear list where in the circular list the pointer of the last node points not NULL but the first node.

Example:

Circular list has no end.

Stack as a circular List

To implement a stack in a circular linked list, let pstack be a pointer to the last node of a circular list. Actually there is no any end of a list but for convention let us assume that the first node(rightmost node of a list) is the top of the stack.

An empty stack is represented by a null list.

The structure for the circular linked list implementation of stack is:

struct node

{

int info;

struct node *next;

};

typedef struct node NodeType;

NodeType *pstack=NULL;

PUSH function:

void PUSH(int item)

{

    NodeType newnode;

    newnode=(NodeType*)malloc(sizeof(NodeType));

    newnode->info=item;

    if(pstack==NULL)

    {

        pstack=newnode;

        pstack->next=pstack;

    }

    else

    {

        newnode->next=pstack->next;

        pstack->next=newnode;

    }

}

POP function:

void POP()

{

    NodeType *temp;

    if(pstack==NULL)

    {

        printf(“Stack underflow\\n');

        exit(1);

    }

    else if(pstack->next==pstack) //for only one node

    {

        printf(“poped item=%d”, pstack->info);

        pstack=NULL;

    }

    else

    {

        temp=pstack->next;

        pstack->next=temp->next;

        printf(“poped item=%d”, temp->info);

        free(temp);

    }

}

Queue as a circular List

By using a circular list, a queue may be specified by a single pointer q to that list. node(q) is the rear of the queue and the following node is its front.

Insertion function:

void insert(int item)

{

    NodeType *nnode;

    nnode=( NodeType *)malloc(sizeof(NodeType));

    nnode->info=item;

    if(pq==NULL)

          pq=nnode;

    else

    {

        nnode->next=pq->next;

        pq->next=nnode;

        pq=nnode;

    }

}

Deletion function:

void delet(int item)

{

    NodeType *temp;

    if(pq==NULL)

    {

        printf(“void deletion\\n”);

        exit(1);

    }

    else if(pq->next==pq)

    {

        printf(“poped item=%d”, pq->info);

        pq=NULL;

    }

    else

    {

        temp=pq->next;

        pq->next=temp->next;

        printf(“poped item=%d”, temp->info);

        free(temp);

    }

}

Huffman algorithm is a technique of compressing data to reduce its size without losing any of the details. It is generally useful to compress the data in which there are frequently occurring characters.

Using the Huffman tree, we can compress the string to a smaller size.

Procedure for construction of Huffman tree

1. Calculate the frequency of each character in the string.

2. Sort the characters in increasing order of the frequency. These are stored in a priority queue Q.

3. Make each unique character as a leaf node.

4. Create an empty node z. Assign the minimum frequency to the left child of z and assign the second minimum frequency to the right child of z. Set the value of the z as the sum of the above two minimum frequencies.

5. Remove these two minimum frequencies from Q and add the sum into the list of frequencies.

6. Insert node z into the tree.

7. Repeat steps 3 to 5 for all the characters.

8. For each non-leaf node, assign 0 to the left edge and 1 to the right edge.

Example:

Let us take any four characters and their frequencies:

Now sort these characters according to their frequencies in non-decreasing order.

Here before using Huffman algorithm the total number of bits required is

= 2*(6+3+2+1) = 24 bits.

The tree constructed for the above example is shown below:

Now from variable length code we get following code sequence.

Thus after using Huffman algorithm the total number of bits required is

=1*3+2*3+3*2+6*1=21 bits

Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm.

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

Algorithm to convert infix to postfix expression

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5.  If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Example:

Infix expression: A*B+C

Postfix expression: AB*C+

Tower of Hanoi (TOH) is a mathematical puzzle which consists of three pegs named as origin, intermediate and destination and more than one disks. These disks are of different sizes and the smaller one sits over the larger one.

In this problem we transfer all disks from origin peg to destination peg using intermediate peg for temporary storage and move only one disk at a time.

Algorithm for TOH problem:

Let’s consider move ‘n’ disks from source peg (A) to destination peg (C), using intermediate peg (B) as auxiliary.

1. Assign three pegs A, B & C

2. If n==1

Move the single disk from A to C and stop.

3. If n>1

a) Move the top (n-1) disks from A to B.

b) Move the remaining disks from A to C

c) Move the (n-1) disks from B to C

4. Terminate

Example for 3 disks: 7 moves

Doubly linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.

In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field. Every node in a double linked list contains three fields and they are shown in the following figure...

Here, 'link1' field is used to store the address of the previous node in the sequence, 'link2' field is used to store the address of the next node in the sequence and 'data' field is used to store the actual value of that node.

Example:

• In double linked list, the first node must be always pointed by head.
• Always the previous field of the first node must be NULL.
• Always the next field of the last node must be NULL

Representation of doubly linked list

struct node

{

int info;

struct node *prev;

struct node *next;

};

typedef struct node NodeType;

NodeType *head=NULL:

A binary tree is a finite set of elements that are either empty or is partitioned into three disjoint subsets.

• The first subset contains a single element called the root of the tree.
• The other two subsets are themselves binary trees called the left and right sub-trees of the original tree.

Each element of a binary tree is called a node of the tree.

There are three types of binary tree:

1. Complete binary tree

A binary tree in which every internal nodes has exactly two children and all leaf nodes are at same level is called complete binary tree.

In complete binary tree:

• Tree of depth ‘d’ contains 2^d nodes at level d.
•  Depth of d of a binary tree will have 2^d+1-1 nodes (total nodes).
• Depth of d will have 2^d leaves and 2^d-1non-leaf nodes (internal nodes).
• No. of external nodes=No. of internal nodes+1.

E.g.

2. Strictly binary tree

A binary tree in which every node has either two or zero number of children is called strictly binary tree.

• In this tree every non-leaf node in a binary tree has nonempty left and right sub-trees.

• A strictly binary tree with n leaves always contains 2n-1 nodes.

E.g.

3. Almost complete binary tree

A almost complete binary tree is a binary tree in which every level of the tree is completely filled except the last level. Also, in the last level, nodes should be attached starting from the left-most position.

A binary tree is a almost complete binary tree (of height h , we take root node as 0 ) if and only if :-

• Level 0 to h-1 represent a full binary tree of height h-1
• One or more nodes in level h-1 may have  0, or 1 child nodes

• If F, G are nodes in level h-1, then F has  more child nodes than G if and only if F is to the left of G , i.e. the last level (h) can be missing leaf nodes, however the ones present must be shifted to the left

E.g.

Pre-order Traversal 

In Pre-Order traversal, the root node is visited before left child and right child nodes. In this traversal, the root node is visited first, then its left child and later its right child. This pre-order traversal is applicable for every root node of all subtrees in the tree.

Algorithm:

.

E.g.

The preorder traversal output of the given above tree is: A B D H I E C F G

In-order Traversal:

In In-Order traversal, the root node is visited between left child and right child. In this traversal, the left child node is visited first, then the root node is visited and later we go for visiting right child node. This in-order traversal is applicable for every root node of all subtrees in the tree. This is performed recursively for all nodes in the tree

Algorithm:

E.g.

The inorder traversal output of the given tree is: H D I B E A F C G

Sorting is the technique to arranging the items of list in any specific order which may be ascending or descending order.

Bubble sort algorithm arranges values by iterating over the list several times and in each iteration the larger value gets bubble up to the end of the list. This algorithm uses multiple passes and in each pass the first and second data items are compared. if the first data item is bigger than the second, then the two items are swapped. Next the items in second and third position are compared and if the first one is larger than the second, then they are swapped, otherwise no change in their order. This process continues for each successive pair of data items until all items are sorted.

Algorithm for Bubble Sort
Let a[n] be an array list of size n.

void bubbleSort(int a[], int n)

{

    int i, j, temp;

    for(i = 0; i < n; i++)

    {

        for(j = 0; j < n-i-1; j++)

        {

            if( a[j] > a[j+1])

            {

                // swap the elements

                temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

            } 

        }

    }

Example:

Consider the array list:

                                                                               Source: w3resource.com

Sequential Search

In this technique, we access each element of list one by one sequentially and see whether it is desired element or not. i.e. the key element is compared with the first element of the list, if the match is found, then search is successful and return the position of key. Otherwise next element of the list is compared with key and this process is continued till the key is found or list is completely searched.

Algorithm:

LinearSearch(A, n,key)

{

    for(i=0;i<n;i++)

    {

        if(A[i] == key)

            return i;

    }

    return -1;    //-1 indicates unsuccessful search

}

Binary Search

Binary search is an extremely efficient search technique that searches the given item in minimum possible comparisons in the already sorted list of given elements. The logic behind the technique is:

1. First find the middle element of the list

2. Compare the mid-element with searched item.

    There are three cases:

      a. If it is a desired element then search is successful.

      b. If it is less than desired item then search only in the first half of the list.

      c. If it is greater than desired item then search in the second half of the list.

Algorithm:

BinarySearch(A,l,r, key)

{

    if(l= = r)

    {

        if(key = = A[l])

            return l+1;         //index starts from 0

        else

            return 0;

    }

     else

    {

        m = (l + r) /2 ;

        if(key = = A[m])

                return m+1;

        else if (key < A[m])

                return BinarySearch(l, m-1, key) ;

        else

                return BinarySearch(m+1, r, key) ;

    }

}

Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which, we can traverse every vertex of the graph. 

The Kruskal's algorithm is given as follows:

1. List all the edges of G with non-decreasing order of their weights.

2. Select an edge of minimum weight. This will be the first edge of T.

3. At each stage, select an edge of minimum weights from all remaining edges of G if it doesn’t form a cycle with previously selected edges in T. Then add the edge to T.

4. Repeat step 3 until n-1 edges have been selected.

Example:

Edges of given graph with non-decreasing order of their weights:

Pick edge (1, 6): No cycle is formed, include it. 

Pick edge (4,3): No cycle is formed, include it. 

Pick edge (2,7): No cycle is formed, include it.