×

Home Discussions Write at Opengenus IQ

×

data structure

Data Structure is one of the most important domains where the way data is structured enables us to solve problems efficiently irrespective the algorithms used. This forms the basis of developing large scale applications like Google Maps

Dynamic Array

Dynamic Array solves the problem of array where the size needs to fixed beforehand. On average, dynamic array achieves same performance as an array by using resize operation.

software engineering

Approaches for implementing Autocomplete Feature

The various approaches for Text Auto-completion are Linear Search (Brute Force), Binary Search Approach, TRIE Data Structure, Ternary Search Tree Approach, Fuzzy Search, Burkhard Keller Tree Approach and Machine Learning Approach.

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.

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

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.

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)].

software engineering

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.

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.

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.

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.

Persistent Segment Tree

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

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.

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).

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)

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.

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.

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

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.

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.

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)

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.

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

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

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.

Leftist Heap

A leftist heap is a modification priority queue implemneted with variant of binary heap. Regarding binary heap, it is always a complete binary tree. It has two main properites Mean Heap Property and Heavy on left side and supports common operations in O(log N) time complexity.

×

OpenGenus community button

Visit our discussion forum to ask any question and join our community

View Forum