First of all - Happy New Year of 2019 to all! ๐๐๐
To kick off the year with a big bang, let’s start with today’s post.
From my previous post little over ago or so, I discussed the importance of knowing data structures such as arrays, stacks, queues etc every good software developer/engineer must grasp. In this post, I will be covering topics on the other not-so-common data structures that we normally (or always, should I say) use when implementing our algorithms.
They are follows:
Trees
Graphs
Heaps
Trie
Data Structures
a) Trees
A binary tree is a tree whose elements have at most 2 children. Each element in a binary tree can have only 2 children thus we typically name them left and right nodes respectively. Typically a tree node has the following properties
Data
Left Pointer
Right Pointer
The top most node in the tree is called the root. Every node (except the root node) in a tree is connected by a directed edge from exactly one node to another. This node is called the parent node. Sometimes, a node can have more than 2 connected nodes to itself. Nodes with no children are called leaves or external nodes. Nodes which are not leaves are called internal nodes.
Next, we have a special kind of binary tree called the Binary Search Tree (BST). This tree is mainly used for storing repository that offers efficient ways of sorting, searching and retrieving data.
A BST is a binary tree where nodes are ordered in the following way:
each node contains a key (or data)
the keys in the left subtree are less than the key in its parent node.
the keys in the right subtree are greater than the key in its parent node.
duplicate keys are not allowed.
Finally, we have a binary tree traversal which is a process that visits all the nodes in the trees. When traversing trees, we consider a couple of traversal search approaches for doing such exercise.
Depth First Search
Breath First Search
Using depth first search approach, we have the following types of traversals to pick on:
Preorder traversal - visit parent first, then left and right children.
Inorder traversal - visit the left first, then parent and right child.
Postorder traversal - visit the left first, then right child and parent.
With breadth-first search, thereโs one type of traversal method which is level order traversal. This type of traversal visits nodes by levels from top to bottom and from left to right.
Binary Trees and Binary Search Trees .
Binary Tree Traversal.
All popular programming languages I know or aware of supports them - such as the following.
importjava.util.*;publicclassBinaryTree{Noderoot;publicvoidadd(intvalue){root=addRecursive(root,value);}privateNodeaddRecursive(Nodecurrent,intvalue){if(current==null){returnnewNode(value);}if(value<current.value){current.left=addRecursive(current.left,value);}elseif(value>current.value){current.right=addRecursive(current.right,value);}returncurrent;}publicbooleanisEmpty(){returnroot==null;}publicintgetSize(){returngetSizeRecursive(root);}privateintgetSizeRecursive(Nodecurrent){returncurrent==null?0:getSizeRecursive(current.left)+1+getSizeRecursive(current.right);}publicbooleancontainsNode(intvalue){returncontainsNodeRecursive(root,value);}privatebooleancontainsNodeRecursive(Nodecurrent,intvalue){if(current==null){returnfalse;}if(value==current.value){returntrue;}returnvalue<current.value?containsNodeRecursive(current.left,value):containsNodeRecursive(current.right,value);}publicvoiddelete(intvalue){root=deleteRecursive(root,value);}privateNodedeleteRecursive(Nodecurrent,intvalue){if(current==null){returnnull;}if(value==current.value){// Case 1: no childrenif(current.left==null&¤t.right==null){returnnull;}// Case 2: only 1 childif(current.right==null){returncurrent.left;}if(current.left==null){returncurrent.right;}// Case 3: 2 childrenintsmallestValue=findSmallestValue(current.right);current.value=smallestValue;current.right=deleteRecursive(current.right,smallestValue);returncurrent;}if(value<current.value){current.left=deleteRecursive(current.left,value);returncurrent;}current.right=deleteRecursive(current.right,value);returncurrent;}privateintfindSmallestValue(Noderoot){returnroot.left==null?root.value:findSmallestValue(root.left);}publicvoidtraverseInOrder(Nodenode){if(node!=null){traverseInOrder(node.left);System.out.print(" "+node.value);traverseInOrder(node.right);}}publicvoidtraversePreOrder(Nodenode){if(node!=null){System.out.print(" "+node.value);traversePreOrder(node.left);traversePreOrder(node.right);}}publicvoidtraversePostOrder(Nodenode){if(node!=null){traversePostOrder(node.left);traversePostOrder(node.right);System.out.print(" "+node.value);}}publicvoidtraverseLevelOrder(){if(root==null){return;}Queue<Node>nodes=newLinkedList<>();nodes.add(root);while(!nodes.isEmpty()){Nodenode=nodes.remove();System.out.print(" "+node.value);if(node.left!=null){nodes.add(node.left);}if(node.left!=null){nodes.add(node.right);}}}classNode{intvalue;Nodeleft;Noderight;Node(intvalue){this.value=value;right=null;left=null;}}}
#!/usr/bin/pythonclassNode:def__init__(self,info):self.info=infoself.left=Noneself.right=Noneself.level=Nonedef__str__(self):returnstr(self.info)classBinarySearchTree:def__init__(self):#constructor of classself.root=Nonedefcreate(self,val):#create binary search tree nodesifself.root==None:self.root=Node(val)else:current=self.rootwhile1:ifval<current.info:ifcurrent.left:current=current.leftelse:current.left=Node(val)break;elifval>current.info:ifcurrent.right:current=current.rightelse:current.right=Node(val)break;else:breakdefinorder(self,node):ifnodeisnotNone:self.inorder(node.left)printnode.infoself.inorder(node.right)defpreorder(self,node):ifnodeisnotNone:printnode.infoself.preorder(node.left)self.preorder(node.right)defpostorder(self,node):ifnodeisnotNone:self.postorder(node.left)self.postorder(node.right)printnode.info
Like trees, a graph is a non-linear data structure that consist of nodes and edges. The nodes are sometimes called vertices and edges are called lines or arcs for there may be more than two nodes connected to each other in the graph.
Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like LinkeIn, Facebook,
importjava.util.*;publicclassVertex{privateintlabel;Vertex(Stringlabel){this.label=label;}//equals and hashCode@Overridepublicbooleanequals(Objectobj){if(this==obj)returntrue;if(!(objinstanceofVertext))returnfalse;Vertex_obj=(Vertex)obj;return_obj.label=this.label;}@OverridepublicinthashCode(){returnlabel;}@OverridepublicintgetLabel(){returnlabel;}@OverridepublicvoidsetLabel(intnewValue){this.label=newValue;}}publicclassGraph{privateMap<Vertex,List<Vertex>>adjVertices;publicGraph(){adjVertices=newMap<>()}publicvoidaddVertex(intlabel){adjVertices.add(newVertex(label),newArrayList<>());}publicvoidremoveVertex(intlabel){Vertexv=newVertex(label);adjVertices.values().stream().map(e->e.remove(v)).collect(Collectors.toList());adjVertices.remove(newVertex(label));}publicvoidaddEdge(intlabel1,intlabel2){Vertexv1=newVertex(label1);Vertexv2=newVertex(label2);adjVertices.get(v1).add(v2);adjVertices.get(v2).add(v1);}publicvoidremoveEdge(intlabel1,intlabel2){Vertexv1=newVertex(label1);Vertexv2=newVertex(label2);List<Vertex>eV1=adjVertices.get(v1);List<Vertex>eV1=adjVertices.get(v1);if(eV1!=null)eV1.remove(v2);if(eV2!=null)eV2.remove(v1);}publicList<Vertex>getAdjVertices(intlabel){returnadjVertices.get(newVertex(label));}}
Another data structure that is commonly used. A heap is a special tree-based data structure in which the tree is a complete binary tree. Morever the tree can only be described as a complete as long as it satisfied the heap property condition such as the parent nodeโs key has an equal value of one of its children nodeโs key.
They are two main types of heaps here.
1) Max-Heap: In a max-heap, the key present at the root of the tree must be the greatest among the keys present at all of itโs children. The same property must be recursively true for all sub-trees in that same binary tree.
2) Min-Heap: In a min-heap, the key present at the root of the tree must be the lowest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that same binary tree.
Here are the programming languages’ respective heaps mplementations.
importjava.util.*;publicclassHeap{/** The number of children each node has **/privatestaticfinalintd=2;privateintheapSize;privateint[]heap;publicBinaryHeap(intcapacity){heapSize=0;heap=newint[capacity+1];Arrays.fill(heap,-1);}publicbooleanisEmpty(){returnheapSize==0;}publicbooleanisFull(){returnheapSize==heap.length;}publicintparent(inti){return(i-1)/d;}privateintkthChild(inti,intk){returnd*i+k;}publicvoidinsert(intx){if(isFull())thrownewNoSuchElementException("Overflow Exception");heap[heapSize++]=x;heapifyUp(heapSize-1);}publicintfindMin(){if(isEmpty())thrownewNoSuchElementException("Underflow Exception");returnheap[0]}publicintdeleteMin(){intkeyItem=heap[0];delete(0);returnkeyItem;}publicintdelete(intind){if(isEmpty())thrownewNoSuchElementException("Underflow Exception");intkeyItem=heap[ind];heap[ind]=heap[heapSize-1];heapSize--;heapifyDown(ind);returnkeyItem;}privatevoidheapifyUp(intchildInd){inttmp=heap[childInd];while(childInd>0&&tmp<heap[parent(childInd)]){heap[childInd]=heap[parent(childInd)];childInd=parent(childInd);}heap[childInd]=tmp;}privatevoidheapifyDown(intind){intchild;inttmp=heap[ind];while(kthChild(ind,1)<heapSize){child=minChild(ind);if(heap[child]<tmp)heap[ind]=heap[child];elsebreak;ind=child;}heap[ind]=tmp;}privateintminChild(intind){intbestChild=kthChild(ind,1);intk=2;intpos=kthChild(ind,k);while((k<=d)&&(pos<heapSize)){if(heap[pos]<heap[bestChild])bestChild=pos;pos=kthChild(ind,k++);}returnbestChild;}}
functionMinHeap(){this.data=[];}MinHeap.prototype.insert=function(val){this.data.push(val);this.bubbleUp(this.data.length-1);};MinHeap.prototype.bubbleUp=function(index){while(index>0){// get the parentvarparent=Math.floor((index+1)/2)-1;// if parent is greater than childif(this.data[parent]>this.data[index]){// swapvartemp=this.data[parent];this.data[parent]=this.data[index];this.data[index]=temp;}index=parent;}};MinHeap.prototype.extractMin=function(){varmin=this.data[0];// set first element to last elementthis.data[0]=this.data.pop();// call bubble downthis.bubbleDown(0);returnmin;};MinHeap.prototype.bubbleDown=function(index){while(true){varchild=(index+1)*2;varsibling=child-1;vartoSwap=null;// if current is greater than childif(this.data[index]>this.data[child]){toSwap=child;}// if sibling is smaller than child, but also smaller than currentif(this.data[index]>this.data[sibling]&&(this.data[child]==null||(this.data[child]!==null&&this.data[sibling]<this.data[child]))){toSwap=sibling;}// if we don't need to swap, then break.if(toSwap==null){break;}vartemp=this.data[toSwap];this.data[toSwap]=this.data[index];this.data[index]=temp;index=toSwap;}};
// A C++ program to demonstrate common Binary Heap Operations #include<iostream> #include<climits> usingnamespacestd;// Prototype of a utility function to swap two integers voidswap(int*x,int*y);// A class for Min Heap classMinHeap{int*harr;// pointer to array of elements in heap intcapacity;// maximum possible size of min heap intheap_size;// Current number of elements in min heap public:// Constructor MinHeap(intcapacity);// to heapify a subtree with the root at given index voidMinHeapify(int);intparent(inti){return(i-1)/2;}// to get index of left child of node at index i intleft(inti){return(2*i+1);}// to get index of right child of node at index i intright(inti){return(2*i+2);}// to extract the root which is the minimum element intextractMin();// Decreases key value of key at index i to new_val voiddecreaseKey(inti,intnew_val);// Returns the minimum key (key at root) from min heap intgetMin(){returnharr[0];}// Deletes a key stored at index i voiddeleteKey(inti);// Inserts a new key 'k' voidinsertKey(intk);};// Constructor: Builds a heap from a given array a[] of given size MinHeap::MinHeap(intcap){heap_size=0;capacity=cap;harr=newint[cap];}// Inserts a new key 'k' voidMinHeap::insertKey(intk){if(heap_size==capacity){cout<<"\nOverflow: Could not insertKey\n";return;}// First insert the new key at the end heap_size++;inti=heap_size-1;harr[i]=k;// Fix the min heap property if it is violated while(i!=0&&harr[parent(i)]>harr[i]){swap(&harr[i],&harr[parent(i)]);i=parent(i);}}// Decreases value of key at index 'i' to new_val. It is assumed that // new_val is smaller than harr[i]. voidMinHeap::decreaseKey(inti,intnew_val){harr[i]=new_val;while(i!=0&&harr[parent(i)]>harr[i]){swap(&harr[i],&harr[parent(i)]);i=parent(i);}}// Method to remove minimum element (or root) from min heap intMinHeap::extractMin(){if(heap_size<=0)returnINT_MAX;if(heap_size==1){heap_size--;returnharr[0];}// Store the minimum value, and remove it from heap introot=harr[0];harr[0]=harr[heap_size-1];heap_size--;MinHeapify(0);returnroot;}// This function deletes key at index i. It first reduced value to minus // infinite, then calls extractMin() voidMinHeap::deleteKey(inti){decreaseKey(i,INT_MIN);extractMin();}// A recursive method to heapify a subtree with the root at given index // This method assumes that the subtrees are already heapified voidMinHeap::MinHeapify(inti){intl=left(i);intr=right(i);intsmallest=i;if(l<heap_size&&harr[l]<harr[i])smallest=l;if(r<heap_size&&harr[r]<harr[smallest])smallest=r;if(smallest!=i){swap(&harr[i],&harr[smallest]);MinHeapify(smallest);}}// A utility function to swap two elements voidswap(int*x,int*y){inttemp=*x;*x=*y;*y=temp;}// Driver program to test above functions intmain(){MinHeaph(11);h.insertKey(3);h.insertKey(2);h.deleteKey(1);h.insertKey(15);h.insertKey(5);h.insertKey(4);h.insertKey(45);cout<<h.extractMin()<<" ";cout<<h.getMin()<<" ";h.decreaseKey(2,1);cout<<h.getMin();return0;}
<?phpclassBinaryHeap{protected$heap;publicfunction__construct(){$this->heap=array();}publicfunctionisEmpty(){returnempty($this->heap);}publicfunctioncount(){// returns the heapsizereturncount($this->heap)-1;}publicfunctionextract(){if($this->isEmpty()){thrownewRunTimeException('Heap is empty');}// extract the root item$root=array_shift($this->heap);if(!$this->isEmpty()){// move last item into the root so the heap is// no longer disjointed$last=array_pop($this->heap);array_unshift($this->heap,$last);// transform semiheap to heap$this->adjust(0);}return$root;}publicfunctioncompare($item1,$item2){if($item1===$item2){return0;}// reverse the comparison to change to a MinHeap!return($item1>$item2?1:-1);}protectedfunctionisLeaf($node){// there will always be 2n + 1 nodes in the// sub-heapreturn((2*$node)+1)>$this->count();}protectedfunctionadjust($root){// we've gone as far as we can down the tree if// root is a leafif(!$this->isLeaf($root)){$left=(2*$root)+1;// left child$right=(2*$root)+2;// right child// if root is less than either of its children$h=$this->heap;if((isset($h[$left])&&$this->compare($h[$root],$h[$left])<0)||(isset($h[$right])&&$this->compare($h[$root],$h[$right])<0)){// find the larger childif(isset($h[$left])&&isset($h[$right])){$j=($this->compare($h[$left],$h[$right])>=0)?$left:$right;}elseif(isset($h[$left])){$j=$left;// left child only}else{$j=$right;// right child only}// swap places with rootlist($this->heap[$root],$this->heap[$j])=array($this->heap[$j],$this->heap[$root]);// recursively adjust semiheap rooted at new// node j$this->adjust($j);}}}}
d) Trie
In computer science, a trie is an ordered search tree that is used to store a dynamic set or associative array where the keys are usually strings. Like an ordered search tree or graph, trie is designed to determine the most efficient way of traversing and retrieving of data by mainly relying on the string prefixes.
It consists of nodes and edges much like graphs and trees. Each node consists of max 26 children and edges connect each parent node to its children. These 26 pointers are nothing but pointers for each of the 26 letters of English alphabet. A separate edge is maintained for every edge.
String are stored in a top to bottom fashion manner on the basis of their prefix in a trie. All prefixes of length 1 are stored at until level 1, all prefixes of length of 2 are stored at until level 2 and so on.
Again, here are the languagesโ queue implementations.
#!/usr/bin/pythonfromtypingimportTupleclassTrieNode(object):""" Our trie node implementation. Very basic. but does the job """def__init__(self,char:str):self.char=charself.children=[]# Is it the last character of the word.`self.word_finished=False# How many times this character appeared in the addition processself.counter=1defadd(root,word:str):""" Adding a word in the trie structure """node=rootforcharinword:found_in_child=False# Search for the character in the children of the present `node`forchildinnode.children:ifchild.char==char:# We found it, increase the counter by 1 to keep track that another# word has it as wellchild.counter+=1# And point the node to the child that contains this charnode=childfound_in_child=Truebreak# We did not find it so add a new chlidifnotfound_in_child:new_node=TrieNode(char)node.children.append(new_node)# And then point node to the new childnode=new_node# Everything finished. Mark it as the end of a word.node.word_finished=Truedeffind_prefix(root,prefix:str)->Tuple[bool,int]:""" Check and return 1. If the prefix exsists in any of the words we added so far 2. If yes then how may words actually have the prefix """node=root# If the root node has no children, then return False.# Because it means we are trying to search in an empty trieifnotroot.children:returnFalse,0forcharinprefix:char_not_found=True# Search through all the children of the present `node`forchildinnode.children:ifchild.char==char:# We found the char existing in the child.char_not_found=False# Assign node as the child containing the char and breaknode=childbreak# Return False anyway when we did not find a char.ifchar_not_found:returnFalse,0# Well, we are here means we have found the prefix. Return true to indicate that# And also the counter of the last node. This indicates how many words have this# prefixreturnTrue,node.counterif__name__=="__main__":root=TrieNode('*')add(root,"hackathon")add(root,'hack')
#include <iostream>// define character size#define CHAR_SIZE 128// A Class representing a Trie nodeclassTrie{public:boolisLeaf;Trie*character[CHAR_SIZE];// ConstructorTrie(){this->isLeaf=false;for(inti=0;i<CHAR_SIZE;i++)this->character[i]=nullptr;}voidinsert(std::string);booldeletion(Trie*&,std::string);boolsearch(std::string);boolhaveChildren(Trieconst*);};// Iterative function to insert a key in the TrievoidTrie::insert(std::stringkey){// start from root nodeTrie*curr=this;for(inti=0;i<key.length();i++){// create a new node if path doesn't existsif(curr->character[key[i]]==nullptr)curr->character[key[i]]=newTrie();// go to next nodecurr=curr->character[key[i]];}// mark current node as leafcurr->isLeaf=true;}// Iterative function to search a key in Trie. It returns true// if the key is found in the Trie, else it returns falseboolTrie::search(std::stringkey){// return false if Trie is emptyif(this==nullptr)returnfalse;Trie*curr=this;for(inti=0;i<key.length();i++){// go to next nodecurr=curr->character[key[i]];// if string is invalid (reached end of path in Trie)if(curr==nullptr)returnfalse;}// if current node is a leaf and we have reached the// end of the string, return truereturncurr->isLeaf;}// returns true if given node has any childrenboolTrie::haveChildren(Trieconst*curr){for(inti=0;i<CHAR_SIZE;i++)if(curr->character[i])returntrue;// child foundreturnfalse;}// Recursive function to delete a key in the TrieboolTrie::deletion(Trie*&curr,std::stringkey){// return if Trie is emptyif(curr==nullptr)returnfalse;// if we have not reached the end of the keyif(key.length()){// recurse for the node corresponding to next character in the key// and if it returns true, delete current node (if it is non-leaf)if(curr!=nullptr&&curr->character[key[0]]!=nullptr&&deletion(curr->character[key[0]],key.substr(1))&&curr->isLeaf==false){if(!haveChildren(curr)){deletecurr;curr=nullptr;returntrue;}else{returnfalse;}}}// if we have reached the end of the keyif(key.length()==0&&curr->isLeaf){// if current node is a leaf node and don't have any childrenif(!haveChildren(curr)){// delete current nodedeletecurr;curr=nullptr;// delete non-leaf parent nodesreturntrue;}// if current node is a leaf node and have childrenelse{// mark current node as non-leaf node (DON'T DELETE IT)curr->isLeaf=false;// don't delete its parent nodesreturnfalse;}}returnfalse;}// C++ implementation of Trie Data Structureintmain(){Trie*head=newTrie();head->insert("hello");std::cout<<head->search("hello")<<" ";// print 1head->insert("helloworld");std::cout<<head->search("helloworld")<<" ";// print 1std::cout<<head->search("helll")<<" ";// print 0 (Not found)head->insert("hell");std::cout<<head->search("hell")<<" ";// print 1head->insert("h");std::cout<<head->search("h");// print 1std::cout<<std::endl;head->deletion(head,"hello");std::cout<<head->search("hello")<<" ";// print 0std::cout<<head->search("helloworld")<<" ";// print 1std::cout<<head->search("hell");// print 1std::cout<<std::endl;head->deletion(head,"h");std::cout<<head->search("h")<<" ";// print 0std::cout<<head->search("hell")<<" ";// print 1std::cout<<head->search("helloworld");// print 1std::cout<<std::endl;head->deletion(head,"helloworld");std::cout<<head->search("helloworld")<<" ";// print 0std::cout<<head->search("hell")<<" ";// print 1head->deletion(head,"hell");std::cout<<head->search("hell");// print 0std::cout<<std::endl;if(head==nullptr)std::cout<<"Trie empty!!\n";// Trie is empty nowstd::cout<<head->search("hell");// print 0return0;}
<?phpclassTrieNode{public$weight;private$children;function__construct($weight,$children){$this->weight=$weight;$this->children=$children;}/** map lower case english letters to 0-25 */staticfunctiongetAsciiValue($char){returnintval(ord($char))-intval(ord('a'));}functionaddChild($char,$node){if(!isset($this->children)){$this->children=[];}$this->children[self::getAsciiValue($char)]=$node;}functionisChild($char){returnisset($this->children[self::getAsciiValue($char)]);}functiongetChild($char){return$this->children[self::getAsciiValue($char)];}functionisLeaf(){returnempty($this->children);}}
Thatโs all for common linear-type data structures.
And thatโs the end of knowing-your-algorithms-and-data-structures series in my blog post.