Repository files navigation

1. DSA-1.1 Introduction to DSA
2. DSA-1.2 Data Structures
   • Arrays
     • 1.1 Array Operations
     • 1.2 Array Types
     • 1.3 Array Sequences
   • Linked List
     • 2.1 Linked List Characteristics
     • 2.2 Linked List Operations
     • 2.3 Linked List Types
   • Stack
     • 3.1 Stack Operations
   • Queue
     • 4.1 Queue Operations
     • 4.2 Queue Types
   • Heap
     • 5.1 Heap Operations
     • 5.2 Heap Types
   • Hash
     • 6.1 Hash Function Types
     • 6.2 Collision Resolution Techniques
   • Tree
     • 7.1 Traversal of Tree
     • 7.2 Trees Classification
     • 7.3 Tree Types
   • Graphs
     • 8.1 Traversal of Graph
3. DSA-1.3 Algorithms
   • Sort
     • 1.1 Bubble Sort
     • 1.2 Selection Sort
     • 1.3 Insertion Sort
     • 1.4 Quick Sort
     • 1.5 Merge Sort
   • Search
     • 2.1 Linear Search
     • 2.2 Binary Search
     • 2.3 Ternary Search
     • 2.4 Jump Search

Data Structure and Algorithm (DSA) is a fundamental concept in computer science that deals with the efficientstorage,retrieval, andmanipulation of data. It is a crucial aspect of software development, as it enables developers to write efficient, scalable, and maintainable code.

Data Structure is a particular way of storing and organizing data in the memory of the computer so that these data can easily be retrieved and efficiently utilized in the future when required.

Primitive Data Structures are basic data structures provided by programming languages to represent single values, such as integers, floating-point numbers, characters, and booleans.

Abstract Data Structures are higher-level data structures that are built using primitive data types and provide more complex and specialized operations. Some common examples of abstract data structures include arrays, linked lists, stacks, queues, trees, and graphs.

Array is a linear data structure that stores a collection of elements of the same data type. Elements are allocated contiguous memory, allowing for constant-time access. Each element has a unique index number.

• Traversal: Iterating through the elements of an array.

  arr= [2,4,6,8,10]forelementinarr:print(element)

• Insertion: Adding an element to the array at a specific index.

  arr= [2,4,6,8,10]index=4new_element=12arr.insert(index,new_element)print(arr)

• Deletion: Removing an element from the array at a specific index.

  arr= [2,4,6,8,10]index=2delarr[index]print(arr)

• Searching: Finding an element in the array by its value or index.

  arr= [2,4,6,8,10]# -> by valuevalue=6ifvalueinarr:index=arr.index(value)print(f'Element{value} found in index{index}.')else:print(f'Element{value} not found.')# -> by indexindex=2if0<=index<len(arr):print(f'Element value at index{index} is{arr[index]}')else:print('Index out of bound.')

• One-dimensional Array: A simple array with a single dimension.

  arr= [2,4,6,8,10]

• Multi-dimensional Array: An array with multiple dimensions, such as a matrix.

  arr= [[2,4,6,], [8,10,12], [14,16,18]]

Anarray sequence is a data structure that can hold multiple items of the same type.

Here are some common types of array sequence in python programming:

• List: A dynamic array that can hold items of different types, but is most commonly used to hold items of the same type.

  list_sample= [2,4,6,8,10]

• Tuple: An immutable array sequence, meaning its content cannot be changed after creation.

  tuple_sample= (2,4,6,8,10)

• String: An immutable sequence of characters used to represent text. Strings are enclosed in either single quotes ('), double quotes ("), or triple quotes (''' or """) for multi-line strings.

  string_sample1='I Love Data Structure and Algorithm'string_sample2="I Love Data Structure and Algorithm"string_sample3='''I Love Data Structure and Algorithm'''

ALinked List is a linear data structure that stores data in nodes, which are connected by pointers. Unlike arrays, linked lists are not stored in contiguous memory locations.

• Dynamic: Linked lists can be easily resized by adding or removing nodes.
• Non-contiguous: Nodes are stored in random memory locations and connected by pointers.
• Sequential access: Nodes can only be accessed sequentially, starting from the head of the list.

Initialize Linked List:

classLinkedList:def__init__(self,data):self.data=dataself.next_node=None

• Creation: Creating a new linked list or adding a new node to an existing list.

  # -> new  nodesnode1=Node(28)node2=Node(32)node3=Node(46)# -> linking nodesnode1.next=node2node2.next=node3

• Traversal: Iterating through the list and accessing each node.

  current_node=node1whilecurrent_node:print(current_node.data)current_node=current_node.next

• Insertion: Adding a new node at a specific position in the list.

  # -> at the beginningnew_node=Node(54)new_node.next=node1node1=new_node# -> at the endnew_node=Node(54)current_node=node1whilecurrent_node.next:current_node=current_node.nextcurrent_node.next=new_node# -> specific positionnew_node=Node(54)insert_pos=2current_node=node1count_init=0whilecount_init<insert_pos-1:current_node=current_node.nextcount_init+=1new_node.next=current_node.nextcurrent_node.next=new_node

• Deletion: Removing a node from the list.

  remove_value=32current_node=node1ifcurrent_node.data==remove_value:node1=current_node.nextelse:whilecurrent_node.nextandcurrent_node.next.data!=remove_value:current_node=current_node.nextifcurrent_node.next:current_node.next=current_node.next.next

• Search: Finding a node with a specific value in the list.

  search_value=46current_node=node1value_found=Falsewhilecurrent_node:ifcurrent_node.data==search_value:value_found=Truebreakcurrent_node=current_node.nextifvalue_found:print('Value found in the list.')else:print('Value not found.')

• Singly Linked List: Each node points to the next node in the list.

  classNode:def__init__(self,data):self.data=dataself.next_node=None# -> new nodesnode1=Node(28)node2=Node(32)node3=Node(46)# -> linking nodesnode1.next_node=node2node2.next_node=node3# -> traversing listcurrent_node=node1whilecurrent_node:print(current_node.data,end=' --> ')current_node=current_node.next_nodeprint('End')

• Doubly Linked List: Each node points to both the next and previous nodes in the list.

  classNode:def__init__(self,data):self.data=dataself.next_node=Noneself.prev_node=None# -> new nodesnode1=Node(28)node2=Node(32)node3=Node(46)# -> linking nodesnode1.next_node=node2node2.prev_node=node1node2.next_node=node3node3.prev_node=node2# -> traversing list# -> forwardcurrent_node=node1whilecurrent_node:print(current_node.data,end=' <--> ')current_node=current_node.next_nodeprint('End')# -> backwardcurrent_node=node3whilecurrent_node:print(current_node.data,end=' <--> ')current_node=current_node.prev_nodeprint('End')

• Circular Linked List: The last node points back to the first node, forming a circular loop.

  classNode:def__init__(self,data):self.data=dataself.next_node=None# -> new nodesnode1=Node(28)node2=Node(32)node3=Node(46)# -> linking nodesnode1.next_node=node2node2.next_node=node3node3.next_node=node1# -> traversing listcurrent_node=node1count_init=0limit_count=10whilecount_init<limit_count:print(current_node.data,end=' --> ')current_node=current_node.next_nodecount_init+=1print('Head')

Stack is a linear data structure that follows a particular order in which the operations are performed. The order may beLIFO(Last In First Out) orFILO(First In Last Out).LIFO implies that the element that is inserted last, comes out first andFILO implies that the element that is inserted first, comes out last.

Initialize Stack:

classStack:def__init__(self):self.stack= []

• Push: Adds an element to the top of the stack.

  defpush(self,element):self.stack.append(element)

• Pop: Removes and returns the element at the top of the stack.

  defpop(self):ifnotself.is_empty():returnself.stack.pop()else:return'Stack is empty.'

• Peek: Returns the element at the top of the stack without removing it.

  defpeek(self):ifnotself.is_empty():returnself.stack[-1]else:return'Stack is empty.'

• Size: Returns the number of elements in the stack.

  defsize(self):returnlen(self.stack)

• IsEmpty: Checks if the stack is empty.

  defis_empty(self):returnlen(self.stack)==0

AQueue Data Structure is a fundamental concept in computer science used for storing and managing data in a specific order. It follows the principle of “First in, First out” (FIFO), where the first element added to the queue is the first one to be removed.

Initialize Queue:

classQueue:def__init__(self,queue_size):self.queue= []self.max_size=queue_size

• Enqueue: Adds an element to the rear of the queue.

  defenqueue(self,item):ifself.is_full():return'Queue is full cannot enqueue.'else:self.queue.append(item)returnf'Enqueued:{item}'

• Dequeue: Removes an element from the front of the queue.

  defdequeue(self):ifself.is_empty():return'Queue is empty cannot dequeue.'else:item=self.queue.pop(0)returnf'dequeued:{item}'

• Peek: Retrieves the front element without removing it.

  defpeek(self):ifself.is_empty():return'Queue is full nothing to peek.'else:returnf'Front element:{self.queue[0]}'

• IsEmpty: Checks if the queue is empty.

  defis_empty(self):returnlen(self.queue)==0

• IsFull: Checks if the queue is full.

  defis_full(self):returnlen(self.queue)==self.max_size

• Circular Queue: Last element connects to the first element.

  classCircularQueue:def__init__(self,queue_size):self.queue= [None]*queue_sizeself.max_size=queue_sizeself.front_pos=self.back_pos=-1defenqueue(self,item):if (self.back_pos+1)%self.max_size==self.front_pos:# -> if queue is fullreturn'Queue is full cannot enqueue.'elifself.front_pos==-1:# -> if queue is empty start from front positionself.front_pos=self.back_pos=0self.queue[self.back_pos]=itemelse:# -> move back position to the next position in circular mannerself.back_pos= (self.back_pos+1)%self.max_sizeself.queue[self.back_pos]=itemreturnf'Enqueue item:{item}'defdequeue(self):ifself.front_pos==-1:# -> if queue is emptyreturn'Queue is empty cannot dequeue.'elifself.front_pos==self.back_pos:# -> if there is one element reset pointerstemp=self.queue[self.front_pos]self.front_pos=back_pos=-1returntempelse:# -> move front position to the next position in circular mannertemp=self.queue[self.front_pos]self.front_pos= (self.front_pos+1)%self.max_sizereturntempdefshow(self):ifself.front_pos==-1:# -> if queue is emptyreturn'Queue is empty.'elifself.back_pos>=self.front_pos:# -> if back is not wrapped arroundreturnself.queue[self.front_pos:self.back_pos+1]else:# -> if back is wrapped arroundreturnself.queue[self.front_pos:]+self.queue[:self.back_pos+1]# -> new queue in size of 7cq=CircularQueue(7)print(cq.enqueue(23))print(cq.enqueue(29))print(cq.enqueue(32))print(cq.enqueue(36))print(cq.enqueue(48))print(cq.enqueue(52))print(cq.enqueue(64))print(f'Queue:{cq.show()}')print(f'Removed item:{cq.dequeue()}')print(f'Updated Queue:{cq.show()}')

• Double-Ended Queue (Deque): Operations can be performed from both ends.

  classDoubleEndedQueue:def__init__(self):self.deque= []defadd_front(self,item):self.deque.insert(0,item)defadd_back(self,item):self.deque.append(item)defremove_front(self):ifself.is_empty():return'Deque is empty.'returnself.deque.pop(0)defremove_back(self):ifself.is_empty():return'Deque is empty.'returnself.deque.pop()defis_empty(self):returnlen(self.deque)==0defshow(self):returnself.deque# -> new double ended queuedq=DoubleEndedQueue()dq.add_front(27)dq.add_back(89)dq.add_front(32)print(f'Deque:{dq.show()}')print(f'Remove front:{dq.remove_front()}')print(f'Remove back:{dq.remove_back()}')print(f'Dequeue is empty:{dq.is_empty()}')print(f'Deque:{dq.show()}')

• Priority Queue: Elements are arranged based on priority.

  classPriorityQueue:def__init__(self):self.queue= []definsert(self,item,priority):self.queue.append((item,priority))self.queue.sort(key=lambdax :x[1],reverse=True)defdelete(self):ifself.is_empty():return'Queue is empty.'returnself.queue.pop(0)[0]defis_empty(self):returnlen(self.queue)==0defshow(self):return [item[0]foriteminself.queue]# -> new priority queuepq=PriorityQueue()pq.insert('Bath',3)pq.insert('Eat',2)pq.insert('Sleep',1)pq.insert('Work',4)print(f'Priority Queue:{pq.show()}')print(f'Remove item:{pq.delete()}')print(f'Updated Priority Queue:{pq.show()}')

AHeap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value. Heaps are usually used to implementpriority queues, where the smallest (or largest) element is always at the root of the tree.

Initialize Heap:

classHeap:def__init__(self):self.heap= []

• Insert: Adds a new element to the heap while maintaining heap properties.

  definsert(self,item):self.heap.append(item)self._heap_insertion_min(len(self.heap-2))def_heap_insertion_min(self,index):head= (index-1)//2ifindex>0andself.heap[index]<self.heap[head]:self.heap[index],self.heap[head]=self.heap[head],self.head[index]self._heap_insertion_min(head)def_heap_insertion_max(self,index):head= (index-1)//2ifindex>0andself.heap[index]>self.heap[head]:self.heap[index],self.heap[head]=self.heap[head],self.head[index]self._heap_insertion_max(head)

• Extract-Max/Extract-Min: Removes the root element and restructures the heap.

  Extract Min:

  defextract_min(self):ifnotself.heap:return'Heap is empty.'min_value=self.heap[0]self.heap[0]=self.heap.pop()self._heap_extraction(0)returnmin_valuedef_heap_extraction(self,index):smallest_num=indexleft_index=2*index+1right_index=2*index+2ifleft_index<len(self.heap)andself.heap[left_index]<self.heap[smallest_num]:smallest_num=left_indexifright_index<len(self.heap)andself.heap[right_index]<self.heap[smallest_num]:smallest_num=right_indexifsmallest_num!=index:self.heap[index],self.heap[smallest_num]=self.heap[smallest_num],self.heap[index]self._heap_extraction(smallest_num)

  Extract Max:

  defextract_max(self):ifnotself.heap:return'Heap is empty.'max_value=self.heap[0]self.heap[0]=self.heap.pop()self._heap_extraction(0)returnmax_valuedef_heap_extraction(self,index):largest_num=indexleft_index=2*index+1right_index=2*index+2ifleft_index<len(self.heap)andself.heap[left_index]>self.heap[largest_num]:largest_num=left_indexifright_index<len(self.heap)andself.heap[right_index]>self.heap[largest_num]:largest_num=right_indexiflargest_num!=index:self.heap[index],self.heap[largest_num]=self.heap[largest_num],self.heap[index]self._heap_extraction(largest_num)

• Increase/Decrease Key: Updates the value of a node and restructures the heap.

  Increase key:

  defincrease_key(self,index,new_item):ifindex>=len(self.heap):raiseIndexError('Index out of bound')self.heap[index]=new_itemself._heap_insertion_max(index)

  Decrease key:

  defdecrease_key(self,index,new_item):ifindex>=len(self.heap):raiseIndexError('Index out of bound')self.heap[index]=new_itemself._heap_insertion_min(index)

• Max-Heap: Root node has the maximum value among its children.

  classMaxHeap:def__init__(self):self.heap= []def__str__(self):returnstr(self.heap)definsert(self,item):self.heap.append(item)self._heap_insertion(len(self.heap)-1)defextract_max(self):ifnotself.heap:return'Heap is empty.'iflen(self.heap)==1:returnself.heap.pop()max_value=self.heap[0]self.heap[0]=self.heap.pop()self._heap_extraction(0)returnmax_valuedefincrease_key(self,index,new_item):ifindex>=len(self.heap):raiseIndexError('Index out of bound')self.heap[index]=new_itemself._heap_insertion(index)def_heap_insertion(self,index):head= (index-1)//2ifindex>0andself.heap[index]>self.heap[head]:self.heap[index],self.heap[head]=self.heap[head],self.heap[index]self._heap_insertion(head)def_heap_extraction(self,index):largest_num=indexleft_index=2*index+1right_index=2*index+2ifleft_index<len(self.heap)andself.heap[left_index]>self.heap[largest_num]:largest_num=left_indexifright_index<len(self.heap)andself.heap[right_index]>self.heap[largest_num]:largest_num=right_indexiflargest_num!=index:self.heap[index],self.heap[largest_num]=self.heap[largest_num],self.heap[index]self._heap_extraction(largest_num)heap=MaxHeap()heap.insert(27)heap.insert(63)heap.insert(46)heap.insert(18)print(f'Heap:{heap}')print(f'Extract:{heap.extract_max()}')print(f'Extract:{heap.extract_max()}')heap.increase_key(1,84)print(f'Heap:{heap}')

• Min-Heap: Root node has the minimum value among its children.

  classMinHeap:def__init__(self):self.heap= []def__str__(self):returnstr(self.heap)definsert(self,item):self.heap.append(item)self._heap_insertion(len(self.heap)-1)defextract_min(self):ifnotself.heap:return'Heap is empty.'iflen(self.heap)==1:returnself.heap.pop()min_value=self.heap[0]self.heap[0]=self.heap.pop()self._heap_extraction(0)returnmin_valuedefdecrease_key(self,index,new_item):ifindex>=len(self.heap):raiseIndexError('Index out of bound')self.heap[index]=new_itemself._heap_insertion(index)def_heap_insertion(self,index):head= (index-1)//2ifindex>0andself.heap[index]<self.heap[head]:self.heap[index],self.heap[head]=self.heap[head],self.heap[index]self._heap_insertion(head)def_heap_extraction(self,index):smallest_num=indexleft_index=2*index+1right_index=2*index+2ifleft_index<len(self.heap)andself.heap[left_index]<self.heap[smallest_num]:smallest_num=left_indexifright_index<len(self.heap)andself.heap[right_index]<self.heap[smallest_num]:smallest_num=right_indexifsmallest_num!=index:self.heap[index],self.heap[smallest_num]=self.heap[smallest_num],self.heap[index]self._heap_extraction(smallest_num)heap=MinHeap()heap.insert(27)heap.insert(63)heap.insert(46)heap.insert(18)print(f'Heap:{heap}')print(f'Extract:{heap.extract_min()}')print(f'Extract:{heap.extract_min()}')heap.decrease_key(1,12)print(f'Heap:{heap}')

Hashing is a technique that generates a fixed-size output(hash value) from an input of variable size using mathematical formulas called hash functions. Hashing is used to determine an index or location for storing an item in a data structure, allowing for efficient retrieval and insertion.

Key Concepts:

• Hash Function: A mathematical function that maps an input to a hash value.

  defhash_function(key):returnhash(key)

• Hash Table: A data structure that stores key-value pairs, where the key is a hash value and the value is the actual data.

  classHashTable:def__init__(self,slot_size):self.slot_size=slot_sizeself.table= [None]*slot_sizedefhash_function(self,key):returnhash(key)%self.slot_sizedefinsert(self,key_item,value_item):index=self.hash_function(key_item)self.table[index]=value_itemdefretrieve(self,key_item):index=self.hash_function(key_item)returnself.table[index]ht=HashTable(20)ht.insert('python','programming language')ht.insert('stacks','data structure')ht.insert('windows','operating system')print(f'Retrieved value for python:{ht.retrieve("python")}')print(f'Retrieved value for stacks:{ht.retrieve("stacks")}')print(f'Retrieved value for windows:{ht.retrieve("windows")}')

• Collision: occurs when two different keys hash to the same index. A common way to handle collisions is chaining, where each table entry points to a linked list of values that hash to the same index.

  classHashTableChaining:def__init__(self,slot_size):self.slot_size=slot_sizeself.table= [[]forninrange(slot_size)]defhash_function(self,key):returnhash(key)%self.slot_sizedefinsert(self,key_item,value_item):index=self.hash_function(key_item)self.table[index].append((key_item,value_item))defretrieve(self,key_item):index=self.hash_function(key_item)for (key,value)inself.table[index]:ifkey==key_item:returnvaluereturnNonehtc=HashTableChaining(20)htc.insert('python','programming language')htc.insert('stacks','data structure')htc.insert('windows','operating system')print(f'Retrieved value for python:{htc.retrieve("python")}')print(f'Retrieved value for stacks:{htc.retrieve("stacks")}')print(f'Retrieved value for windows:{htc.retrieve("windows")}')

• Division Method: Divides the input by a constant and uses the remainder as the hash value.

  defdivision_hash(key_item,slot_size):returnhash(key_item)%slot_sizekey_item='Computer Science'slot_size=100print(f'Division hash value for `{key_item}` is{division_hash(key_item,slot_size)}')

• Mid Square Method: Squares the input and takes the middle digits as the hash value.

  defmidsquare_hash(key_item,slot_size):hashed_key=hash(key_item)squared_key=hashed_key*hashed_keystr_key=str(squared_key)mid_index=len(str_key)//2mid_digit=str_key[mid_index-1:mid_index+2]returnint(mid_digit)%slot_sizekey_item='Computer Science'slot_size=100print(f'Mid Square hash value for{key_item} is{midsquare_hash(key_item,slot_size)}')

• Folding Method: Divides the input into equal-sized blocks and adds them together to get the hash value.

  deffolding_hash(key_item,slot_size):hashed_key=hash(key_item)str_key=str(hashed_key)block_size=2total=0forninrange(0,len(str_key),block_size):blocks=int(str_key[n:n+block_size])total+=blocksreturntotal%slot_sizekey_item='Computer Science'slot_size=100print(f'Folding hash value for{key_item} is{folding_hash(key_item,slot_size)}')

• Multiplication Method: Multiplies the input by a constant and takes the fractional part as the hash value.

• Separate Chaining (Open Hashing): Stores colliding elements in a linked list at the corresponding hash value.

  classNode:def__init__(self,key_item,value_item):self.key=key_itemself.value=value_itemself.next=NoneclassOpenHashing:def__init__(self,slot_size):self.slot_size=slot_sizeself.table= [None]*slot_sizedefhash_function(self,key_item):returnhash(key_item)%self.slot_sizedefinsert(self,key_item,value_item):index=self.hash_function(key_item)new_node=Node(key_item,value_item)ifself.table[index]isNone:self.table[index]=new_nodeelse:current_item=self.table[index]whilecurrent_item.next:ifcurrent_item.key==key_item:current_item.value=value_itemreturncurrent_item=current_item.nextcurrent_item.next=new_nodedefretrieve(self,key_item):index=self.hash_function(key_item)current_item=self.table[index]whilecurrent_item:ifcurrent_item.key==key_item:returncurrent_item.valuecurrent_item=current_item.nextreturnNoneoh=OpenHashing(20)oh.insert('python','web development')oh.insert('java','app development')print(f'Retrieved value for python is{oh.retrieve("python")}')print(f'Retrieved value for java is{oh.retrieve("java")}')

• Open Addressing (Close Hashing): Uses various strategies to find an alternative location for colliding elements within the hash table.

  Linear Probing

  classLinearProbing:def__init__(self,slot_size):self.slot_size=slot_sizeself.table= [None]*slot_sizedefhash_function(self,key_item):returnhash(key_item)%self.slot_sizedefinsert(self,key_item,value_item):index=self.hash_function(key_item)whileself.table[index]isnotNoneandself.table[index][0]!=key_item:index= (index+1)%self.slot_sizeself.table[index]= (key_item,value_item)defretrieve(self,key_item):index=self.hash_function(key_item)start_index=indexwhileself.table[index]isnotNone:ifself.table[index][0]==key_item:returnself.table[index][1]index= (index+1)%self.slot_sizeifindex==start_index:breakreturnNonelp=LinearProbing(20)lp.insert('python','web development')lp.insert('java','app development')print(f'Retrieved value for python is{lp.retrieve("python")}')print(f'Retrieved value for java is{lp.retrieve("java")}')

  Quadratic Probing

  classQuadraticProbing:def__init__(self,slot_size):self.slot_size=slot_sizeself.table= [None]*slot_sizedefhash_function(self,key_item):returnhash(key_item)%self.slot_sizedefinsert(self,key_item,value_item):index=self.hash_function(key_item)n=1whileself.table[index]isnotNoneandself.table[index][0]!=key_item:index= (index+n*n)%self.slot_sizen+=1self.table[index]= (key_item,value_item)defretrieve(self,key_item):index=self.hash_function(key_item)start_index=indexn=1whileself.table[index]isnotNone:ifself.table[index][0]==key_item:returnself.table[index][1]index= (index+n*n)%self.slot_sizen+=1ifindex==start_index:breakreturnNoneqp=QuadraticProbing(20)qp.insert('python','web development')qp.insert('java','app development')print(f'Retrieved value for python is{qp.retrieve("python")}')print(f'Retrieved value for java is{qp.retrieve("java")}')

  Double Hashing

  classDoubleHashing:def__init__(self,slot_size):self.slot_size=slot_sizeself.table= [None]*slot_sizedeffirst_hash(self,key_item):returnhash(key_item)%self.slot_sizedefsecond_hash(self,key_item):return1+ (hash(key_item)% (self.slot_size-1))definsert(self,key_item,value_item):index=self.first_hash(key_item)step=self.second_hash(key_item)whileself.table[index]isnotNoneandself.table[index][0]!=key_item:index= (index+step)%self.slot_sizeself.table[index]= (key_item,value_item)defretrieve(self,key_item):index=self.first_hash(key_item)step=self.second_hash(key_item)start_index=indexwhileself.table[index]isnotNone:ifself.table[index][0]==key_item:returnself.table[index][1]index= (index+step)%self.slot_sizen+=1ifindex==start_index:breakreturnNonedh=DoubleHashing(20)dh.insert('python','web development')dh.insert('java','app development')print(f'Retrieved value for python is{dh.retrieve("python")}')print(f'Retrieved value for java is{dh.retrieve("java")}')

Atree is a non-linear hierarchical data structure consisting of nodes connected by edges, with a top node called the root and nodes having child nodes. It is used in computer science for organizing data efficiently.

Initialize Tree node:

classTreeNode:def__init__(self,value):self.value=valueself.left_node=Noneself.right_node=None

Tree traversal methods are used to visit and process nodes in a tree data structure. The three common traversal methods are:

• In-Order: Visit left subtree, current node, then right subtree.

  defin_order_traversal(root_node):ifroot_node:in_order_traversal(root_node.left_node)print(root_node.value,end=' ')in_order_traversal(root_node.right_node)# -> example tree usageroot=TreeNode(10)root.left_node=TreeNode(27)root.right_node=TreeNode(32)root.left_node.left_node=TreeNode(48)root.left_node.right_node=TreeNode(53)in_order_traversal(root)

• Pre-Order: Visit current node, left subtree, then right subtree.

  defpre_order_traversal(root_node):ifroot_node:print(root_node.value,end=' ')pre_order_traversal(root_node.left_node)pre_order_traversal(root_node.right_node)pre_order_traversal(root)

• Post-Order: Visit left subtree, right subtree, then current node.

  defpost_order_traversal(root_node):ifroot_node:post_order_traversal(root_node.left_node)post_order_traversal(root_node.right_node)print(root_node.value,end=' ')post_order_traversal(root)

Classifications ofTrees refer to grouping trees based on certain characteristics or criteria. This can involve categorizing trees based on their balance factor, degree of nodes, ordering properties, etc. Below are some important classification of Tree.

• A Binary Tree Data Structure is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.

  classBinaryTree:def__init__(self,value):self.value=valueself.left_node=Noneself.right_node=Nonedefin_order_traversal(root_node):ifroot_node:in_order_traversal(root_node.left_node)print(root_node.value,end=' ')in_order_traversal(root_node.right_node)# -> root noderoot=BinaryTree(27)# -> left and right children of noderoot.left_node=BinaryTree(34)root.right_node=BinaryTree(48)# -> children of left child noderoot.left_node.left_node=BinaryTree(52)root.left_node.right_node=BinaryTree(63)# -> children of right noderoot.right_node.left_node=BinaryTree(74)root.right_node.right_node=BinaryTree(81)in_order_traversal(root)

• A Ternary Tree is a special type of tree data structure. Unlike a regular binary tree where each node can have up to two child nodes.

  classTernaryTree:def__init__(self,value):self.value=valueself.left_node=Noneself.middle_node=Noneself.right_node=Nonedefpre_order_traversal(root_node):ifroot_node:print(root_node.value,end=' ')pre_order_traversal(root_node.left_node)pre_order_traversal(root_node.middle_node)pre_order_traversal(root_node.right_node)# -> root noderoot=TernaryTree(27)# -> left, middle and right children of noderoot.left_node=TernaryTree(34)root.middle_node=TernaryTree(48)root.right_node=TernaryTree(52)# -> children of left child noderoot.left_node.left_node=TernaryTree(63)root.left_node.middle_node=TernaryTree(75)root.left_node.right_node=TernaryTree(82)pre_order_traversal(root)

• Generic tree or an N-ary tree is a versatile data structure used to organize data hierarchically. Unlike binary trees that have at most two children per node, generic trees can have any number of child nodes.

  classN_aryTree:def__init__(self,value):self.value=valueself.n_child= []defadd_child(self,child_node):self.n_child.append(child_node)defpre_order_traversal(root_node):ifroot_node:print(root_node.value,end=' ')forchildinroot_node.n_child:pre_order_traversal(child)root=N_aryTree(12)# -> new children of root noderoot.add_child(N_aryTree(24))root.add_child(N_aryTree(26))root.add_child(N_aryTree(28))# -> new children of first child noderoot.n_child[0].add_child(N_aryTree(34))root.n_child[0].add_child(N_aryTree(47))# -> new children of second child noderoot.n_child[1].add_child(N_aryTree(57))# -> new children of third child noderoot.n_child[2].add_child(N_aryTree(60))root.n_child[2].add_child(N_aryTree(77))pre_order_traversal(root)

• A Binary Search Tree is a data structure used in computer science for organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node.

  classNode:def__init__(self,value):self.value=valueself.left_node=Noneself.right_node=NoneclassBinarySearchTree:def__init__(self):self.root_node=Nonedefinsert(self,value):ifself.root_nodeisNone:self.root_node=Node(value)else:self.insert_node(self.root_node,value)definsert_node(self,root_node,value):ifvalue<root_node.value:ifroot_node.left_nodeisNone:root_node.left_node=Node(value)else:self.insert_node(root_node.left_node,value)else:ifroot_node.right_nodeisNone:root_node.right_node=Node(value)else:self.insert_node(root_node.right_node,value)defsearch(self,value):returnself.search_node(self.root_node,value)defsearch_node(self,root_node,value):ifroot_nodeisNoneorroot_node.value==value:returnroot_nodeifvalue<root_node.value:returnself.search_node(root_node.left_node,value)returnself.search_node(root_node.right_node,value)defin_order_traversal(self,root_node):ifroot_node:self.in_order_traversal(root_node.left_node)print(root_node.value,end=' ')self.in_order_traversal(root_node.right_node)# -> new elements for bstelements= [11,67,89,23,65,74,43]bst=BinarySearchTree()forninelements:bst.insert(n)# -> tree traversalbst.in_order_traversal(bst.root_node)search_element=bst.search(89)ifsearch_element:print(f'Element{search_element.value} found.')else:print(f'Element{search_element}')

• A Heap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value.

  Max/Min Heap

• A tree is considered balanced if the heights of the left and right subtrees of any node differ by at most one. In a more general sense, a balanced tree ensures that no path from the root to a leaf is significantly longer than any other such path.

  classNode:def__init__(self,value):self.height=1self.value=valueself.left_node=Noneself.right_node=NoneclassAVLTree:def__init__(self):self.root_node=Nonedefrotate_left(self,N):x=N.right_nodey=x.left_nodex.left_node=NN.right_node=yN.height=1+max(self.tree_height(N.left_node),self.tree_height(N.right_node))x.height=1+max(self.tree_height(x.left_node),self.tree_height(x.right_node))returnxdefrotate_right(self,N):x=N.left_nodey=x.right_nodex.right_node=NN.left_node=yN.height=1+max(self.tree_height(N.left_node),self.tree_height(N.right_node))x.height=1+max(self.tree_height(x.left_node),self.tree_height(x.right_node))returnxdefinsert(self,value):self.root_node=self.insert_node(self.root_node,value)definsert_node(self,root_node,value):ifnotroot_node:returnNode(value)ifvalue<root_node.value:root_node.left_node=self.insert_node(root_node.left_node,value)else:root_node.right_node=self.insert_node(root_node.right_node,value)root_node.height=1+max(self.tree_height(root_node.left_node),self.tree_height(root_node.right_node))balance=self.balance_tree(root_node)ifbalance>1andvalue<root_node.left_node.value:returnself.rotate_right(root_node)ifbalance<-1andvalue>root_node.right_node.value:returnself.rotate_left(root_node)ifbalance>1andvalue>root_node.left_node.value:root_node.left_node=self.rotate_left(root_node.left_node)returnself.rotate_right(root_node)ifbalance<-1andvalue<root_node.right_node.value:root_node.right_node=self.rotate_right(root_node.right_node)returnself.rotate_left(root_node)returnroot_nodedeftree_height(self,N):ifNisNone:return0returnN.heightdefbalance_tree(self,N):ifNisNone:return0returnself.tree_height(N.left_node)-self.tree_height(N.right_node)defin_order_traversal(self,root_node):ifroot_node:self.in_order_traversal(root_node.left_node)print(root_node.value,end=' ')self.in_order_traversal(root_node.right_node)# -> new elements for AVLelements= [78,21,56,32,11,43]avl=AVLTree()forninelements:avl.insert(n)# -> traversing tree elementsavl.in_order_traversal(avl.root_node)

• An unbalanced tree does not maintain any constraints on the balance of the subtrees. This can result in a tree where some branches are significantly deeper than others, leading to skewed structures.

  classNode:def__init__(self,value):self.value=valueself.left_node=Noneself.right_node=NoneclassBinarySearchTree:def__init__(self):self.root_node=Nonedefinsert(self,value):ifself.root_nodeisNone:self.root_node=Node(value)else:self.insert_node(self.root_node,value)definsert_node(self,root_node,value):ifvalue<root_node.value:ifroot_node.left_nodeisNone:root_node.left_node=Node(value)else:self.insert_node(root_node.left_node,value)else:ifroot_node.right_nodeisNone:root_node.right_node=Node(value)else:self.insert_node(root_node.right_node,value)defin_order_traversal(self,root_node):ifroot_node:self.in_order_traversal(root_node.left_node)print(root_node.value,end=' ')self.in_order_traversal(root_node.right_node)# -> new elements for bstelements= [11,67,89,23,65,74,43]bst=BinarySearchTree()forninelements:bst.insert(n)# -> tree traversalbst.in_order_traversal(bst.root_node)

AGraph is a non-linear data structure consisting of a finite set of vertices(or nodes) and a set of edges that connect a pair of nodes.

Graph representation:

classGraph:def__init__(self):self.graph= {}defadd_edge(self,key,value):ifkeynotinself.graph:self.graph[key]= []ifvaluenotinself.graph:self.graph[value]= []self.graph[key].append(value)self.graph[value].append(key)

• Breadth-First Search: Visits nodes level by level.

  defbreadth_first_search(graph,start_point):root_visited=set()queue= [start_point]root_visited.add(start_point)whilequeue:node=queue.pop(0)print(node,end=' ')forneighbor_nodeingraph[node]:ifneighbor_nodenotinroot_visited:root_visited.add(neighbor_node)queue.append(neighbor_node)# -> new graph bfsg=Graph()g.add_edge(1,4)g.add_edge(1,2)g.add_edge(2,8)g.add_edge(2,1)g.add_edge(3,2)g.add_edge(3,7)breadth_first_search(g.graph,1)

• Depth-First Search: Visits nodes recursively, exploring one branch at a time.

  defdepth_first_search(graph,node,root_visited=None):ifroot_visitedisNone:root_visited=set()root_visited.add(node)print(node,end=' ')forneighbor_nodeingraph[node]:ifneighbor_nodenotinroot_visited:depth_first_search(graph,neighbor_node,root_visited)# -> new graph dfsg=Graph()g.add_edge(1,4)g.add_edge(1,2)g.add_edge(2,3)g.add_edge(2,6)g.add_edge(3,7)g.add_edge(3,2)depth_first_search(g.graph,1)

AnAlgorithm is a step-by-step procedure or formula for solving a specific problem or performing a task. It defines a clear sequence of operations to be executed in order to achieve a desired outcome, such as sorting data, searching for information, or performing calculations.

Sorting algorithms are used to arranging the elements of a list in a specific order, such as numerical or alphabetical. It organizes the items in a systematic way, making it easier to search for and access specific elements.

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

# -> recursivedefbubble_sort(arr,N=None):ifNisNone:N=len(arr)ifN==1:returnforxinrange(N-1):ifarr[x]>arr[x+1]:arr[x],arr[x+1]=arr[x+1],arr[x]bubble_sort(arr,N-1)# -> sample usagesample_arr= [89,45,67,18,91,52]bubble_sort(sample_arr)print(sample_arr)

Selection Sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.

# -> recursivedefselection_sort(arr,select=0):n=len(arr)ifselect>=n-1:returnmin_num=selectforxinrange(select+1,n):ifarr[x]<arr[min_num]:min_num=xarr[select],arr[min_num]=arr[min_num],arr[select]selection_sort(arr,select+1)# -> sample usagesample_arr= [89,45,67,18,91,52]selection_sort(sample_arr)print(sample_arr)

Insertion Sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is a stable sorting algorithm, meaning that elements with equal values maintain their relative order in the sorted output.

# -> index baseddefinsertion_sort(arr):n=len(arr)forxinrange(1,n):key_index=arr[x]position=xwhileposition>0andarr[position-1]>key_index:position-=1arr.pop(x)arr.insert(position,key_index)# -> sample usagesample_arr= [89,45,67,18,91,52]insertion_sort(sample_arr)print(sample_arr)

QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.

defquick_sort(arr):n=len(arr)ifn<=1:returnarrkey_element=arr[len(arr)//2]minimum= [xforxinarrifx<key_element]equal= [xforxinarrifx==key_element]maximum= [xforxinarrifx>key_element]returnquick_sort(minimum)+equal+quick_sort(maximum)# -> sample usagesample_arr= [89,45,67,18,91,52]print(quick_sort(sample_arr))

Merge Sort is a sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the input array into smaller subarrays and sorting those subarrays then merging them back together to obtain the sorted array.

defmerge_sort(arr):n=len(arr)ifn<=1:returnarrmid=n//2left,right=merge_sort(arr[:mid]),merge_sort(arr[mid:])result,X,y= [],0,0whileX<len(left)andy<len(right):ifleft[X]<=right[y]:result.append(left[X])X+=1else:result.append(right[y])y+=1result.extend(left[X:])result.extend(right[y:])returnresult# -> sample usagesample_arr= [89,45,67,18,91,52]print(merge_sort(sample_arr))

Searching algorithms are used to locate specific data within a larger set of data. It helps find the presence of a target value within the data. There are various types of searching algorithms, each with its own approach and efficiency.

• The linear search algorithm is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found; otherwise, the search continues till the end of the dataset.

  deflinear_search(arr,target_element):forindex,elementinenumerate(arr):ifelement==target_element:returnindexreturn-1# -> sample usagesample_arr= [89,45,67,18,91,52]target_element=67output=linear_search(sample_arr,target_element)ifoutput!=-1:print(f'Element{target_element} found at index{output}')else:print(f'Element{target_element} not found.')

• Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N).

  defbinary_search(arr,target_element):left,right=0,len(arr)-1whileleft<=right:mid_element= (left+right)//2ifarr[mid_element]==target_element:returnmid_elementelifarr[mid_element]<target_element:left=mid_element+1else:right=mid_element-1return-1# -> sample usagesample_arr= [89,45,67,18,91,52]target_element=67output=binary_search(sample_arr,target_element)ifoutput!=-1:print(f'Element{target_element} found at index{output}')else:print(f'Element{target_element} not found.')

• Ternary search is a search algorithm that is used to find the position of a target value within a sorted array. It operates on the principle of dividing the array into three parts instead of two, as in binary search.

  defternary_search(arr,target_element):defsearch_element(left,right,target_element):ifleft>right:return-1divide= (right-left)//3mid_element1=left+dividemid_element2=right-divideifarr[mid_element1]==target_element:returnmid_element1ifarr[mid_element2]==target_element:returnmid_element2iftarget_element<arr[mid_element1]:returnsearch_element(left,mid_element1-1,target_element)eliftarget_element>arr[mid_element2]:returnsearch_element(mid_element2+1,right,target_element)else:returnsearch_element(mid_element1+1,mid_element2-1,target_element)returnsearch_element(0,len(arr)-1,target_element)# -> sample usagesample_arr= [89,45,67,18,91,52]target_element=67output=ternary_search(sample_arr,target_element)ifoutput!=-1:print(f'Element{target_element} found at index{output}')else:print(f'Element{target_element} not found.')

• Like Binary Search, Jump Search is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

  importmathdefjump_search(arr,target_element):n=len(arr)steps=int(math.sqrt(n))previous_step=0whilearr[min(steps,n-1)]<target_element:previous_step=stepssteps+=int(math.sqrt(n))ifprevious_step>=n:return-1forxinrange(previous_step,min(steps,n)):ifarr[x]==target_element:returnxreturn-1# -> sample usagesample_arr= [89,45,67,18,91,52]sample_arr.sort()target_element=67output=ternary_search(sample_arr,target_element)ifoutput!=-1:print(f'Element{target_element} found at index{output}')else:print(f'Element{target_element} not found.')

Top

• Description:GeeksforGeeks
• Code Example:Author