Data Structures

Data Structures

Burkhard Keller Tree (BK Tree)

Burkhard Keller Tree (BK-Tree) is a Tree Data Structure that is used to find the near-matches to a String Query. It is used in several applications like spell correction and autocompletion.

Data Structures

Must read research papers on Data Structures

We presented research papers on Data Structures that are a must read for everyone. These come from authors like Raimund Seidel, Knuth, Rubinchik and others

Data Structures

Autocomplete Feature using Ternary Search Tree

Autocomplete Feature can be implemented using Ternary Search Tree as well which is a memory optimized version of trie and performs equally well.

Algorithms

Autocomplete feature using TRIE Data Structure

Autocomplete is a feature of suggesting possible extensions to a partially written text and is widely used in search engine, code IDEs and much more. Trie data structure is a perfect fit to implement this feature efficient in terms of memory and time [O(length of string)].

Algorithms

Implement Least Recently Used (LRU) Cache

In this article, we have implemented Least Recently Used cache using 2 data structures: Doubly Linked Lists and Hash Map and compared LRU with FIFO cache.

Data Structures

Gap Buffer

Gap buffer is a data structure used to edit array of text in an efficient manner which is currently being edited. It is used in text editors.

Data Structures

Interval Trees: One step beyond BST

Interval tree is a variant of BST and is able to handle intervals in logarithmic time for search, insert and delete operations and is used in geometry.

Data Structures

Sparse Table

Sparse table is a data structure which pre-process the information to answer static Range Queries in constant time O(1) with O(N log N) preprocessing.

Problems on Binary Tree

Largest Independent Set in Binary Tree

In this article, we solve the Largest Independent Set in Binary Tree problem using Dynamic Programming and use an augmented binary tree to achieve this.

Data Structures

Persistent Segment Tree

Our aim is to introduce persistency in segment trees but also ensure that the space and time complexity is not affected.

Data Structures

Rope: the Data Structure used by text editors to handle large strings

Rope data structure is widely used by software such as text editors like Sublime, email systems like Gmail and text buffers to handle large strings efficiently.

Problems on Binary Tree

Algorithm to convert Binary Search Tree into Balanced Binary Search Tree

In this article, we will explore an algorithm to convert a Binary Search Tree (BST) into a Balanced Binary Search Tree in linear time O(N).

Problems on Binary Tree

Copy a binary tree where each node has a random pointer

We explored an algorithm to copy a binary tree with an additional pointer which points to any random node in the tree. We explored two techniques Naive solution using 2 traversals and Efficient solution using hashing.

Algorithms

Converting Postfix to Infix using Stack

We have explored an algorithm to convert a Postfix expression to Infix expression using Stack. This takes linear time O(N)

Data Structures

Count inversions in an array using Fenwick Tree

Fenwick tree is usually used for range query problems but it can be used to solve the problem of finding the number of inversions in an array efficiently.

Data Structures

Understanding Fenwick tree (Binary Indexed Tree) with Range product

Fenwick tree is a tree based data structure that is widely used to solve range query problems in logarithmic time O(log N) which would otherwise have taken linear time O(N). In this article, we have explained it in depth using the range product query problem.

Problems on Binary Tree

Learn how to traverse a Binary Tree (Inorder , Preorder , Postorder)

In this article we will learn three Depth first traversals namely inorder, preorder and postorder and their use. These three types of traversals generally used in different types of binary tree. In summary, Inorder: left, root, right; Preorder: root, left, right and Postorder: left, right, root

Data Structures

Optimizing a Segment Tree with Lazy Propagation

Lazy propagation is an optimization technique for segment tree to delay some of the update queries so that a set of update queries can be performed more efficiently together and thus, reducing the number of operations performed. The time complexity remain the same.

Problems on Binary Tree

Understand everything about Binary Search Tree

Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers in a tree data structure. It can be used to search for the presence of a number in O(log(n)) time and a simple traversal gives the numbers in sorted order.

Problems on Binary Tree

Algorithm for finding the minimum number of swaps required to convert a binary tree to binary search tree

We developed an algorithm for finding the minimum number of swaps required to convert a binary tree to binary search tree. The Idea is do the inorder traversal of binary tree and store it in an array.Then find the minimum number of swaps require to sort an array which is the output we want.

Data Structures

Fibonacci Heap

A Fibonacci heap is a heap data structure similar to the binomial heap. It uses Fibonacci numbers and also used to implement the priority queue element in Dijkstra’s shortest path algorithm which reduces the time complexity from O(m log n) to O(m + n log n)

Data Structures

Understanding Bit mask/ Bit map in depth

A bit mask is a data structure, usually an integer or array of bits, that represent a bit pattern which signifies a particular state in a particular computational problem. It takes advantage of bitwise operations.

Problems on Binary Tree

Binary Tree

A binary tree is a tree data structure in which each node has upto two children (that is a maximum of two children nodes), which are referred to as the left child and the right child. Implementation and applications of binary tree

Data Structures

Max Heap and Min Heap

A min heap is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes. The most important property of a min heap is that the node with the smallest, or minimum value, will always be the root node. Max heap is similar

Data Structures

Pairing Heap

Pairing heaps are a type of heap data structures which have fast running time for their operations. They are modificaton of Binomial Heap. Basically it is a type of self adjusting Binomial Heap which adjusts or rearrange themselves during the operations, due to which they remain balanced.