2-3 Trees and 2-3-4 Trees

2-3 Trees 

A 2-3 Tree is a data(tree) structure where every bode with children has either two children and two data elements 

2-3 Tree Structure

Properties 

1. Every internal node is a 2-node or a 3-node 
2. All leaves are at the same level 
3. All data is kept in sorted order.

Operations

1. Search 

               Similar to BST, since the data elements in each node is ordered 

2. Insertion

              Works by searching for the proper location of the key and adds it there. If the node becomes a 4-node, then the split from the 2-nodes and the middle key is moved up to the parent.

3. Deletion 

            Reverse of insertion

2-3-4 trees 

2-3-4 trees are self balancing data structure. The time complexity for the trees involve O(log(n))

Properties: 

• Every node is a 2-, 3- or a 4- node and hold 1,2,or 3 data elements respectuvely 
• All leaves are kept at same depth 
• All data is kept in sorted order.

Operations and working functions are similar to 2-3 Trees as explained above.

Blogs to refer: 1,2 

AVL Trees

AVL Tree is a self balancing Binary Search tree named after Soviet inventors George Adelson Velsky and Evangi Landis.

A height balanced BST is known as Avl which can have at most 1 difference with children.Height at leaves usually start with 0 but for AVL trees we do it from 1(for the ease of understanding).Here the difference between the left and right subtrees cannot be more than one for all nodes.Operations like Lookup, insertion and deleting all take  O(log(n)) time in both the average and worst case.

Operations:

Searching: Process is similar to search in ordinary Binary search tree.

Insertion: To make sure given tree remains AVL after every insertion. 

So we must rebalance, without violating the BST rule. The Insert operation involves two rotation 

1. Left Rotation 
2. Right Rotation

Steps to follow for Insertion:

1. Perform standard BST insert
2. Starting from w, find first unbalanced node
3. Rebalance the tree in the following ways accordingly 
1. Left Left case (Right Rotation)
2. Left right case (Left and right rotation)
3. Right Right case (Left Rotate)
4. Right left case (Right and Left Rotation)

AVL Tree Rebalancing

Algorithm

1.Perform normal BST insertion 2.Current node must be one of the ancestors of the newly inserted node. Update the height of the current node. 3.Get the balance factor(left-right subtree height) of the current node 4.If balance factor is greater than 1, then the current node is unbalanced and wer are either in the 1st case or second case to check whether it is 1st compare the newly inserted key with the key in left subtree root. 5.If balance factor is less than -1, then the current node is balanced and wer are either in 3rd case or 4th case.To check if it is 3rd ,compare the newly inserted node with node in the right subtree.


Deletion: Deletion follows the same procedure as Insertion except in place of insert we delete.


Blogs to follow: 1, 2, 3

Binary Search Trees (BST)

Binary Search Tree is a node based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with key's less than the node's key
• The right subtree of a node contains only nodes with keys greater than node's key
• The left and right subtree each must also be a binary search tree
• The tree must not have no duplicate nodes

The above properties provide an ordering among keys such that operations like 

1. Search
2. Min 
3. Max 

can be done fast enough.The tree actions are 

1. Search 
2. Insert 
3. Delete

There are many types of binary trees. Few among them are self balancing trees like 

1. AVL Trees
2. Red Black Trees
3. Splay Trees

All operations take time directly proportional to the height of the tree. Complexity at worst crosses O(h).

Optimal Binary Search Tree

If we do not plan to modify a search tree and if we know how exactly often each item will be accessed.We can construct an optimal binary search tree (with an average cost of looking up an item).

Also refer to Day - Stout - Warren Algorithm or DSW algorithm.

Trees: An Introduction

Trees are very flexible, versatile and powerful non-liner data structure that can be
used to represent data items possessing hierarchical relationship between the grand father
and his children and grand children as so on.


The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly above something is called its parent. For example, a is a child of f and f is the parent of a. Finally, elements with no children are called leaves.

Advantages of Trees

1. Trees can serve as a hierarchy 
2. Trees provide moderate access/search
3. Trees provide Moderate/insertion Deletion
4. Have no upper limit 

Main applications of trees include:

1. Manipulate hierarchical data.
2. Make information easy to search .
3. Manipulate sorted lists of data.
4. Router algorithms
5.  Form of a multi-stage decision-making.

A Tree Classification

---

Binary Tree

A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

It can be represented as:  

1. Data 
2. Left pointer or Child
3. Right pointer or Child

Properties of a Binary tree

1) The maximum number of nodes at level ‘l’ of a binary tree is 2^(L-1).

Here level is number of nodes on path from root to the node (including root and node). Level of root is 1. This can be proved by induction.For root, L = 1, number of nodes = 2^(L-1) = 1.Assume that maximum number of nodes on level l is 2^(L-1).Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2^(L-1)

2) Maximum number of nodes in a binary tree of height ‘h’ is 2^h – 1.

Here height of a tree is maximum number of nodes on root to leaf path. Height of a leaf node is considered as 1.

This result can be derived from point 2 above. A tree has maximum nodes if all levels have maximum nodes. So maximum number of nodes in a binary tree of height h is 1 + 2 + 4 + .. + 2^h-1. This is a simple geometric series with h terms and sum of this series is 2^h – 1.

3) In a Binary Tree with N nodes, minimum possible height or minimum number of levels is  ⌈Log(base2)(N+1)].

This can be directly derived from point 2 above. If we consider the convention where height of a leaf node is considered as 0, then above formula for minimum possible height becomes   

⌈ Log(base2)(N+1)⌉ – 1

4) A Binary Tree with L leaves has at least   ⌈ Log2L ⌉ + 1   levels

A Binary tree has maximum number of leaves when all levels are fully filled. Let all leaves be at level l, then below is true for number of leaves L.

   L   <=  2l-1  [From Point 1]

   Log2L <=  l-1

   l >=   ⌈ Log2L ⌉ + 1  

5) In Binary tree, number of leaf nodes is always one more than nodes with two children.

   L = T + 1

Where L = Number of leaf nodes

      T = Number of internal nodes with two children

Types of Binary trees:

1. Full Binary Tree ; A full binary tree is a binary tree which has exactly has either 2 children or  no children. (No. of leaf nodes=No, of internal nodes+1)
2. Complete Binary Tree: A complete Binary tree is a binary tree excepting the bottom which is filled from left to right.Its the best binary tree as it provides the best possible ration between the number of nodes and the height. O(log N) height h and nodes N. 2^(h+1)-1.
3. Strictly Binary tree: A strictly binary tree is a binary tree which has 2N -1 nodes i.e., no children or two children where N stands for degree.
4. Perfect Binary Tree:A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.They are ambiguously also known as complete or full binary tree.
5. Balanced binary Tree:A balanced binary tree has the minimum possible maximum height (a.k.a. depth) for the leaf nodes, because for any given number of leaf nodes the leaf nodes are placed at the greatest height possible.

Tree Traversal 

Unlike other linear data structures, trees can be traversed in different ways.The ways to traverse trees are : 

1. Depth First Search 
1. Inorder Traversal     (Lc R Rc) //Where Lc=Left Child Rc= Right Child R=Root
2. Preorder Traversal   (R Lc Rc) //                   "
3. Postorder Traversal (Lc Rc R) //                   " 
2. Breadth first Search

References

More tree explanations shall be done with programs.

If you are given two traversal sequences, can you construct the binary tree?
It depends on what traversals are given. If one of the traversal methods is Inorder then the tree can be constructed, otherwise not.

Therefore, following combination can uniquely identify a tree.

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

And following do not.
Postorder and Preorder.
Preorder and Level-order.
Postorder and Level-order.

For example, Preorder, Level-order and Postorder traversals are same for the trees given in above diagram.

Preorder Traversal = AB
Postorder Traversal = BA
Level-Order Traversal = AB

So, even if three of them (Pre, Post and Level) are given, the tree can not be constructed.

Queue

Queue is a linear data structure which follows a FIFO(First In First Out) order.Classic example of queue can be a line in front of a bank cashier to deposit or withdraw money.

The primary difference between a stack and queue is that Stack is (Last In First Out) piling of data. Whereas as Queue is  First In First Out.

Queue data structure has two pointers.One being the front and other pointing the rear.

Operations of Queue:

1. Enqueue
2. Dequeue

Queue can be implemented using :

1. Array 
2. Linked list

Both have their own advantages or disadvantages.

Applications of Queue:

1. CPU scheduling & Disk Scheduling
2. IO buffers or asynchronous transfer 

More Links to follow.

Geeksforgeeks,org

Circularly Linked List

Circularly linked list is a linked list where all nodes are connected to form a circle.There is no end or rear or null pointer.

Circularly Linked List

Circular linked list can be implemented in both singly linked list as well as doubly linked list.
The only difference between implementation of a circularly linked list and other linked list is that, Circularly linked list doesn't have a last element instead points to the head.Whereas other linked list points to null in place of the head.

To traverse through all the elements in the circularly linked list, we need to use two loops 

1. One which checks the condition that the head reference is not equal to null
2. Other loop which checks if the loop doesn't repeat. i.e temp variable doesn't equal to head.

Function to push an element into the Circularly linked list 

/* Function to insert a node at the begining of a Circular linked list */ void push(struct node **head_ref, int data) { struct node *ptr1 = (struct node *)malloc(sizeof(struct node)); struct node *temp = *head_ref; ptr1->data = data; ptr1->next = *head_ref; /* If linked list is not NULL then set the next of last node */ if (*head_ref != NULL) { while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; /*For the first node */ *head_ref = ptr1; }

1) Linked List is empty: a) since new_node is the only node in CLL, make a self loop. new_node->next = new_node; b) change the head pointer to point to new node. *head_ref = new_node; 2) New node is to be inserted just before the head node: (a) Find out the last node using a loop. while(current->next != *head_ref) current = current->next; (b) Change the next of last node. current->next = new_node; (c) Change next of new node to point to head. new_node->next = *head_ref; (d) change the head pointer to point to new node. *head_ref = new_node; 3) New node is to be inserted somewhere after the head: (a) Locate the node after which new node is to be inserted. while ( current->next!= *head_ref && current->next->data < new_node->data) { current = current->next; } (b) Make next of new_node as next of the located pointer new_node->next = current->next; (c) Change the next of the located pointer current->next = new_node;

Source: Geeksforgeeks
Also Refer to Tortoise-Hare Algorithm

Doubly Linked list

A doubly linked list contains an extra pointer which points to the previous element of a list and which does not exist in a singly linked list.This makes easy traversal of a linked list to the previous elements.

Algorithm for insertion 

of an element in a Doubly Linked List . Insertion can be classified into 3 different methods.

1. Insertion at the Head
2. Insertion at a given postion 
3. Insertion at the end of the Linked List 

Insertion at the head

1.Allocate a node 2. Put in the data 3.Make the next of the new node as head and previous as Null 4.Change the prev of head node to new Node. 5. Move prev of head to point to the new node

Insertion after a given position

1.Allocate a new Node 2.Put in the data 3.Make next of new node as next of prev node new_node->next=prev-node->next 4.Make the next of prev_node as new_node prev-node->next=new_node 5.Make prev-node as previous of new-node new_node->prev= prev_node 6.Change previous of new_node's next node

Insertion of a node towards the end

1.Allocate a node 2.Put in the data 3.This new node is going to be the last node, so make next of it as NULL new_node->next=NULL 4.Traverse the list to the end 5.Change the next of last node as new node 6.Make the last node as prev of new node

Algorithm for deletion of a node

1.If node to be deleted is the head node head=del_node->next 2.Check the next node only if the node to be deleted is not the last node. if(del->next != NULL) del->next->prev = del->prev; 3.Check the prev node only if the node to be deleted is not the first node. if(del->prev != NULL) del->prev->next = del->next; 4.Delete the memory

Algorithm for reversing a Doubly Linked List

/* Function to reverse a Doubly Linked List */ void reverse(struct node **head_ref) { struct node *temp = NULL; struct node *current = *head_ref; /* swap next and prev for all nodes of doubly linked list */ while (current != NULL) { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } /* Before changing head, check for the cases like empty list and list with only one node */ if(temp != NULL ) *head_ref = temp->prev; }
Source: GeeksforGeeks

Advantages over Singly Linked list

1. Can be traversed front and back from any location
2. Less ambiguity in deleting an element from the linked list.

Disadvantages over a Singly Linked list

1. Every Node takes in an extra pointer when a linked list could be created with a single pointer.
2. Extra maintenance.

Important Links to Follow
Doubly Linked List(Geeksforgeeks)
Code for doubly Linked List

Tortoise & Hare Algorithm

Tortoise & Hare algorithm is also known as Floyd's Cycle-Finding Algorithm.This is a technique for detecting infinite loops inside a linked list, symlinks, state machines etc.

To detect a loop inside a linked list
Source

• Make a pointer to start of the linked list and call it Hare 
• Make a pointer to the head of the linked list and call it Tortoise 
• advance the Hare by two and the tortoise by one for every interation.
• There's a loop if the Tortoise and Hare meet
• There's no loop if the Hare reaches the end.

Algorithm is intersting as it takes O(n) time and O(1) space.

Python code to understand Tortoise and Hare algorithms
Source

def floyd(f,x0): tortoise=f(x0) hare=f(f(x0)) while tortoise!=hare: tortoise=f(tortoise) hare=f(f(hare)) mu=0 tortoise=x0 while tortoise!=hare: tortoise=f(tortoise) hare=f(hare) mu+=1 lam=1 hare=f(tortoise) while(tortoise!=hare): hare=f(hare) lam+=1 return lam,mu


With this Algorithm we detect the loops and iterations in a circularly linked list as suggested by the name Floyd's Cycle-finding Algorithm.

More Reference: Coding Freak

Stack

Stack is a linear data structure which follows a particular order in which the operations are performed. Order is LIFO(Last In First Out) or FILO(First In Last Out)

Three main operations of a stack are :

1. Push
2. Pop
3. Peek or Top

Stack

Push

The Push Operation pushes an element into the stack.

Pop

Pop operation removes the top most element in the stack.

Peek

Peek or top operation returns the top most value of the stack.

To understand stack, you can assume a pile of books placed one over the other.To get the last book in the stack, one needs to take away all the books before the last book.

Applications of Stack

1. Recursion
2. Tower of Hanoi
3. Converting Infix to Postfix.

Stack can be implemented in two different ways: 

1. Stack Implementation using Arrays 
2. Stack Implementation using Linked list

The implemented codes are carried out into separate blogs in the above given links.

More stack related blogs

Stack Implementation Using Linked list

Implementation of a stack using linked list is dynamic and flexible. Yet the space consumed is high and adding or manipulating the linked list is complex.
Refer to the code for more details. The Code language is C++.

Code:

//Implementation of a stack using a Singly Linked List #include<iostream> using namespace std; class stack{ public: struct Node{ int data; struct Node* Link; }; struct Node* top=NULL;//initially my stack is empty void push(){ int x; struct Node* temp=new Node(); cout<<"\nEnter the data: "; cin>>x; temp->data=x; temp->Link=top; top=temp; } void pop(){ if(top==NULL){ cout<<"\nStack underflow"<<endl; }else{ top=top->Link; } } //function to peek into the stack void peek(){ cout<<"\nPeeping into the stack:"<<endl; cout<<top->data; } //function to check if the stack is empty void isEmpty(){ if(top==NULL){ cout<<"\nThe Stack is empty"<<endl; }else{ cout<<"\nThe stack is not empty"<<endl; } } //function to print the elements of the stack void print(){ Node* temp=new Node(); temp=top; cout<<"Printing Elements in a stack"<<endl; while(temp!=NULL){ cout<<temp->data<<endl; temp=temp->Link; } } void sizeofstack(){ Node* temp=new Node(); temp=top; int sizeoftemp; while(temp!=NULL){ temp=temp->Link; sizeoftemp+=sizeof(temp); } cout<<"\nSize of the stack"<<sizeoftemp<<endl; } //function to choose the stack operations void option(){ int x=1; int options; while(x!=0){ cout<<"\nStack operations:"<<endl; cout<<"1.Push"<<endl; cout<<"2.Pop"<<endl; cout<<"3.Peek"<<endl; cout<<"4.Is Empty?"<<endl; cout<<"5.Print Stack"<<endl; cout<<"6.Stack Size"<<endl; cout<<"7.Exit"<<endl; cout<<"Enter option"<<endl; cin>>options; switch(options){ case 1: push(); break; case 2: pop(); break; case 3: peek(); break; case 4: isEmpty(); break; case 5: print(); break; case 6: sizeofstack(); break; case 7: exit(0); break; } } } }; int main(){ stack k; k.option(); }

Output:

Stack Implementation Using Array

This blog will deal with implementation of stack using arrays.The implementation is simple yet we need to allocate a pre-defined size.The allocated size may or may not be utilized completely. This makes the array implementation non-flexible.

Using Array

#include<stdio.h> #include<stdlib.h> #define MAX_SIZE 101 int A[MAX_SIZE]; int top=-1; void Push(int x){ if(top==MAX_SIZE-1){ printf("Error;stack overflow\n"); } A[++top]=x; } void pop(){ if(top==MAX_SIZE-1){ printf("Error: No element to pop\n"); } top--; } int Top(){ return A[top]; } void print(){ int i; printf("Stack :"); for(i=0;i<=top;i++){ printf("\n%d",A[i]); } printf("\n"); } int main(){ Push(2); print(); Push(10); print(); pop(); Top(); Push(7); print(); pop(); }



Output

---

Linked List v/s Arrays

Linked list is a replacement to the arrays. Since arrays take in a block of memory so the flexibility is very less.It has a defined structure which uses a limited memory and uses only when the memory is required. Though adding more elements is a cumbersome task.

Each node in a list consists of at least two parts:

1. Data
2. Pointer to the next node

struct Node{ int data; Node* next; }

A tabular comparison of Arrays v/s Linked List:

S. No	Parameter		Arrays	Linked list
1	Cost		Constant time O(1)	O(n)
2	Memory usage		Fixed Size Contiguous Blocks of memory	No unused memory, Extra memory for pointer variables
3	Cost of inserting and Deleting elements	At the beginning	O(n) Shifting one index at a time to the right	Creating a new node and head pointer O(1)
		At the end	If Array not full O(1) else O(n)	Traversing a new node & End
		At the nth position	O(n)	O(n)
4	Ease of Use		Very Easy	Complicated especially in C/C++

Advantages over arrays

1. Dynamic size
2. Ease of insertion/deletion

Drawbacks:

1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2. Extra memory space for a pointer is required with each element of the list.

Linked List

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference  to the next node in the sequence.

                                   

Types of Linked List: 

Based on the working of a data structure, we list only a few important linked list models.

1. Singly Linked list
2. Doubly Linked list 
3. Circular Linked list

Others forms of linked lists include multiply linked list, sentinal nodes etc.

Advantages

• Linked lists are a dynamic data structure, allocating the needed memory while the program is running.
• Insertion and deletion node operations are easily implemented in a linked list.
• Linear data structures such as stacks and queues are easily executed with a linked list.
• They can reduce access time and may expand in real time without memory overhead.

Disadvantages

• They have a tendency to use more memory due to pointers requiring extra storage space.
• Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
• Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
• Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer.

Abstract Data Types(ADT)

An abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

ADT is a theoretical concept in computer science, used in the design and analysis of algorithms, data structures, and software systems, and do not correspond to specific features of any computer languages.

In ADTs,inferences are derived using a mathematical or a logical module.It is very much equivalent to writing a set of points understandable to a user.Lets assume a list with user input data which can be implemented in two ways:

1. Using Arrays
2. Using Linked Lists

Both have their own set of advantages and disadvantages,But it is made sure that advantages are used to make our understanding ends meet and the idea to implement looks concrete.

Each data structure has its limitations. One such data structure is a Linked list which is followed in the next chapter.