Introduction to Basic Data Structures and Algorithms

Introduction to Basic Data Structures and Algorithms

Basic types of Data Structures.

• As previously stated, anything that can store data is referred to as a data structure, hence Integer, Float, Boolean, Char, and so on are all data structures. Primitive Data Structures are what they're called.
• Then there are complicated Data Structures, which are used to store enormous amounts of data that are linked together. The following are some examples of Abstract Data Structure:

Basic types of Data Structures.

1. Linked List
2. Tree
3. Graph
4. Stack, Queue etc.

All of these data structures enable us to execute various data operations. We choose these data structures based on the sort of operation that will be performed. In subsequent courses, we will delve further into these data structures.

Characteristic	Description
Linear	In Linear data structures, the data items are arranged in a linear sequence. Example: Array
Non-Linear	In Non-Linear data structures, the data items are not in sequence. Example: Tree, Graph
Homogeneous	In homogeneous data structures, all the elements are of same type. Example: Array
Non-Homogeneous	In Non-Homogeneous data structure, the elements may or may not be of the same type. Example: Structures
Static	Static data structures are those whose sizes and structures associated memory locations are fixed, at compile time. Example: Array
Dynamic	Dynamic structures are those which expands or shrinks depending upon the program need and its execution. Also, their associated memory locations changes. Example: Linked List created using pointers

What is the definition of an algorithm?

• An algorithm is a finite set of instructions or logic that must be written in a specific order to complete a set goals. An algorithm is not a complete programme or code; rather, it is the basic logic (solution) of a problem, which can be stated in a flowchart or as a high-level description in pseudocode.

The following properties must be met by every algorithm:

1. Input- There should be 0 or more inputs given externally to the algorithm.
2. Output- There should be at least 1 output as a result.
3. Definiteness- Every step of the algorithm should be clear and well defined.
4. Finiteness- The algorithm should have finite number of steps.
5. Correctness- Every step of the algorithm must generate a correct output.

If an algorithm takes less time to perform and requires less memory space, it is said to be efficient and fast. The following properties are used to evaluate an algorithm's performance:

1. Time Complexity.
2. Space Complexity.

Time Complexity.

• The term "time complexity" refers to the amount of time it takes for a programme to operate from start to finish. 
• It's generally a good idea to attempt to minimize the time required to a bare minimum, so that our algorithm runs as quickly as feasible. In the next parts, we will go through Time Complexity in further depth.

NOTE: 

• Before diving into data structures, you should have a solid understanding of programming, whether in C or C++, Java, Python, or another language.

Space Complexity.

• It is the amount of memory space used by the algorithm while it is being executed. For multi-user systems and circumstances with limited memory, space complexity must be regarded seriously.

The following components of an algorithm typically demand space:

Instruction Space: 

• This is the amount of space necessary to store the program's executable version. This space is constant, but it varies depending on how many lines of code are in the application.

Data Space: 

• This is the amount of space needed to hold the values of all the constants and variables (including temporary variables).

Environment Space: 

• This is the amount of space needed to store the environmental data required to resume the suspended function.

The Characteristics of Good Algorithms

• Input and output must be well specified.
• Each stage of the algorithm should be simple and straightforward.
• Among the numerous various approaches to address an issue, algorithms should be the most effective.
• Computer code should not be included in an algorithm. Rather, the algorithm should be designed in a way that allows it to be utilized in a variety of programming languages.

Algorithm 1: Add two numbers entered by the user

Step 1: Start

Step 2: Declare variables num1, num2 and sum. 

Step 3: Read values num1 and num2. 

Step 4: Add num1 and num2 and assign the result to sum.

        sum←num1+num2 

Step 5: Display sum 

Step 6: Stop

Algorithm 2: Find the largest number among three numbers

Step 1: Start

Step 2: Declare variables a,b and c.

Step 3: Read variables a,b and c.

Step 4: If a > b

           If a > c

              Display a is the largest number.

           Else

              Display c is the largest number.

        Else

           If b > c

              Display b is the largest number.

           Else

              Display c is the greatest number.  

Step 5: Stop

Algorithm 3: Find Root of the quadratic equation ax2 + bx + c = 0

Step 1: Start

Step 2: Declare variables a, b, c, D, x1, x2, rp and ip;

Step 3: Calculate discriminant

         D ← b2-4ac

Step 4: If D ≥ 0

              r1 ← (-b+√D)/2a

              r2 ← (-b-√D)/2a 

              Display r1 and r2 as roots.

        Else     

              Calculate real part and imaginary part

              rp ← -b/2a

              ip ← √(-D)/2a

              Display rp+j(ip) and rp-j(ip) as roots

Step 5: Stop      

       

Algorithm 4: Find the factorial of a number

Step 1: Start

Step 2: Declare variables n, factorial and i.

Step 3: Initialize variables

          factorial ← 1

          i ← 1

Step 4: Read value of n

Step 5: Repeat the steps until i = n

     5.1: factorial ← factorial*i

     5.2: i ← i+1

Step 6: Display factorial

Step 7: Stop

Algorithm 5: Check whether a number is prime or not

Step 1: Start

Step 2: Declare variables n, i, flag.

Step 3: Initialize variables

        flag ← 1

        i ← 2  

Step 4: Read n from the user.

Step 5: Repeat the steps until i=(n/2)

     5.1 If remainder of n÷i equals 0

            flag ← 0

            Go to step 6

     5.2 i ← i+1

Step 6: If flag = 0

           Display n is not prime

        else

           Display n is prime

Step 7: Stop 

Algorithm 6: Find the Fibonacci series till the term less than 1000

Step 1: Start 

Step 2: Declare variables first_term,second_term and temp. 

Step 3: Initialize variables first_term ← 0 second_term ← 1 

Step 4: Display first_term and second_term 

Step 5: Repeat the steps until second_term ≤ 1000 

     5.1: temp ← second_term 

     5.2: second_term ← second_term + first_term 

     5.3: first_term ← temp 

     5.4: Display second_term 

Step 6: Stop

Few more detail about Data Structure

Time Complexity of an Algorithms

B-Tree

B-Tree in Data Structure.

Every node in a binary search tree, such as an AVL Tree or a Red-Black Tree, can only have one value (key) and a maximum of two children, but there is another type of search tree known as a B-Tree that allows a node to store more than one value (key) and have more than two children.

• The Height Balanced m-way Search Tree, also known as B-Tree, was created by Bayer and McCreight in 1972. It was then given the name B-Tree.
• B-Tree can be defined as follows...

"B-Tree is a self-balanced search tree with multiple keys in every node and more than two children for every node."

• A B-tree is a method of placing and locating files (called records or keys) in a database. (The meaning of the letter B has not been explicitly defined.) The B-tree algorithm minimizes the number of times a medium must be accessed to locate a desired record, thereby speeding up the process.
• Here, number of keys in a node and number of children for a node is depend on the order of the B-Tree. 
• Every B-Tree has order.

B-Tree of Order m has the following properties...

1. All the leaf nodes must be at same level.
2. All nodes except root must have at least [m/2]-1 keys and maximum of m-1 keys.
3. All non leaf nodes except root (i.e. all internal nodes) must have at least m/2 children.
4. If the root node is a non leaf node, then it must have at least 2 children.
5. A non leaf node with n-1 keys must have n number of children.
6. All the key values within a node must be in Ascending Order.

For example, B-Tree of Order 4 contains maximum 3 key values in a node and maximum 4 children for a node.

Example..

The following operations are performed on a B-Tree...

1. Search
2. Insertion
3. Deletion

Search Operation in B-Tree

B-Tree

• The search operation in a B-Tree is similar to that of a Binary Search Tree.
• The search procedure in a Binary search tree begins at the root node, and we make a 2-way decision every time we make a decision (we go to either left subtree or right sub-tree).
• In a B-Tree, the search process also begins at the root node, but we make an n-way decision each time, where n is the total number of children a node has.
• The search operation in a B-Tree has a temporal complexity of O(log n). The following is how the search is carried out...

Searching in B Trees is similar to that in Binary search tree. For example, if we search for an item 49 in the following B Tree. The process will something like following :

1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.

• Searching in a B tree depends upon the height of the tree. The search algorithm takes O(log n) time to search any element in a B tree.

The insertion operation is performed as follows...

Step 1: 

• Check whether tree is Empty.

Step 2: 

• If tree is Empty, then create a new node with new key value and insert into the tree as a root node.

Step 3: 

• If tree is Not Empty, then find a leaf node to which the new key value cab be added using Binary Search Tree logic.

Step 4: 

• If that leaf node has an empty position, then add the new key value to that leaf node by maintaining ascending order of key value within the node.

Step 5: 

• If that leaf node is already full, then split that leaf node by sending middle value to its parent node. Repeat tha same until sending value is fixed into a node.

Step 6: 

• If the splitting is occurring to the root node, then the middle value becomes new root node for the tree and the height of the tree is increased by one.

Example..

Construct a B-Tree of Order 3 by inserting numbers from 1 to 10.

Deletion in B-Tree

At the leaf nodes, deletion is also conducted. It can be a leaf node or an inside node that needs to be deleted. In order to delete a node from a B tree, use the following algorithm.

• Determine the location of the leaf node.
• If the leaf node has more than m/2 keys, delete the required key from the node.
• If the leaf node lacks m/2 keys, fill in the gaps with the element from the eighth or left sibling.

1. If the left sibling has more than m/2 elements, shift the intervening element down to the node where the key is deleted and push the largest element up to its parent.
2. If the right sibling has more than m/2 items, shift the intermediate element down to the node where the key is deleted and push the smallest element up to the parent.

• Create a new leaf node by merging two leaf nodes and the parent node's intervening element if neither sibling has more than m/2 elements.
• If the parent has less than m/2 nodes, repeat the operation on the parent as well.

If the node to be removed is an internal node, its in-order successor or predecessor should be used instead. The process will be same as the node is deleted from the leaf node because the successor or predecessor will always be on the leaf node.

Let us see the Example:

• Remove node 53 from the B Tree of order 5, as indicated in the diagram.

• 53 is present in the right child of element 49. Delete it.

• Now there is only 57 items remaining in the node, and the minimal number of elements required in a B tree of order 5 is 2. 
• It's less than that, and the elements in its left and right subtrees aren't enough, so combine it with the left sibling and parent's intervening element, i.e. 49.

The B tree is used in following manners.

• Because accessing values held in a huge database that is saved on a disc is a very time consuming activity, B tree is used to index the data and enable fast access to the actual data stored on the discs.
• In the worst situation, searching an un-indexed and unsorted database with n key values takes O(n) time. In the worst-case scenario, if we use B Tree to index this database, it will be searched in O(log n) time.

Binary Search Tree

A Binary Search Tree (BST) is a tree in which all nodes have the properties listed below: 

• The left sub-tree of a node has a key that is less than or equal to the key of its parent node.
• A node's right sub-tree has a key that is greater than its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Representation of Binary Search Tree.

BST is a set of nodes organized in such a way that they all have the same BST qualities. A key and a value are assigned to each node. The required key is compared to the keys in BST during the search, and if found, the related value is obtained.

Following is a pictorial representation of BST −

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

Basic Operations

Following are the basic operations of a tree −

• Search − Searches an element in a tree.
• Insert − Inserts an element in a tree.
• Pre-order Traversal − Traverses a tree in a pre-order manner.
• In-order Traversal − Traverses a tree in an in-order manner.
• Post-order Traversal − Traverses a tree in a post-order manner.

Node

• Define a node having some data, references to its left and right child nodes.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Search Operation

• Start searching for an element from the root node whenever possible. 
• Then, if the data is less than the key value, look in the left subtree for the element. 
• If not, look for the element in the right subtree. For each node, use the same algorithm.

Algorithm for Serching.

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   return current;
}

Insert Operation

• Before inserting an element, make sure it's in the right place. 
• Begin your search at the root node, then look for an empty spot in the left subtree and insert the data if the data is less than the key value. 
• If not, look find an empty place in the right subtree and fill it in.

Algorithm

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}        

Tree Traversal

Traversal is a method of traversing all of a tree's nodes and printing their values. We always begin at the root (head) node since all nodes are connected by edges (links). That is, we cannot reach a node in a tree at random. We can cross a tree in three different ways.

• In-order Traversal
• Pre-order Traversal
• Post-order Traversal

Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.

In-order Traversal

• The left subtree is visited first, second by the root, and finally the right subtree in this traversal approach. Always keep in mind that any node could be a subtree in and of itself.
• The output of a binary tree traversed in order produces sorted key values in ascending order.

• We begin with A and move to its left subtree B using in-order traversal. In the same way, B is traversed in sequence. The process continues until all nodes have been visited. The output of this tree's in-order traverse will be

D → B → E → A → F → C → G

Algorithm

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Pre-order Traversal

• In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

• Starting with A, we visit A first, then move to its left subtree B, following pre-order traversal. B is also visited in a pre-order manner. The process continues until all nodes have been visited. The output of this tree's pre-order traversal will be

A → B → D → E → C → F → G

Algorithm

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Post-order Traversal

• In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.

• We begin at A and proceed to the left subtree B using pre-order traversal. B is also traversed in the reverse order. The process continues until all nodes have been visited. The output of this tree's post-order traversal will be

D → E → B → F → G → C → A

Algorithm

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

BFS (Breadth First Search)

When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a breadthward motion and uses a queue to remember to retrieve the next vertex to start a search.

Initialize the queue.

We start from visiting S (starting node), and mark it as visited.

We then see an unvisited adjacent node from S. In this example, we have three nodes but alphabetically we choose A, mark it as visited and enqueue it.

Next, the unvisited adjacent node from S is B. We mark it as visited and enqueue it.

Next, the unvisited adjacent node from S is C. We mark it as visited and enqueue it.

Now, S is left with no unvisited adjacent nodes. So, we dequeue and find A.

From A we have D as unvisited adjacent node. We mark it as visited and enqueue it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the program is over.