Data Structure topics

Prefix sum array

Prefix Sum array is a data structure design which helps us to answer several queries such as sum in a given range in constant time which would otherwise take linear time. It requires a linear time preprocessing and is widely used due to its simplicity and effectiveness.

Data Structures

2D Fenwick Tree / 2D Binary Indexed Tree

Fenwick Tree is used to answer range or interval queries in an array in logarithmic time. Fenwick tree can be generalized to multiple dimensions. 2D Fenwick tree is one such implementation used to answer sub-matrix queries, i.e. queries in 2 dimensions. It requires the operation to be invertible.

Data Structures

2D Segment Tree

Segment Tree is used to answer range queries in an array. The data structure can be extended to 2 dimensions to answer sub-matrix queries in logarithmic time. Some examples of these queries are Maximum element in sub-matrix It can be seen as a segment tree of segment trees. We give an example for it

Data Structures

Fenwick Tree (Binary Indexed Tree)

Fenwick Tree / Binary indexed tree (BIT) is a data structure used to process interval/range based queries. Compared to segment tree data structure, Fenwick tree uses less space and is simpler to implement. One disadvantage is that it can be only used with an operation that is invertible.

Data Structures

Segment Tree

A segment tree is a divide and conquer based data structure used to store information about intervals of some linear data structure. It is a height-balanced binary tree where every node corresponds to an interval of the array. It allows processing interval or range queries in logarithmic time

Data Structures

Trie data structure

A trie (digital tree, radix tree, prefix tree) is a kind of an ordered search tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Worst case search time complexity is Θ(key_length) and trie is widely used in real life applications

Data Structures

B+ Tree : Search, Insert and Delete operations

A B+ tree is an N-ary tree with a variable often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children. It can be viewed as a B-tree in which each node contains only keys with an additional level

Data Structures

B-Tree Deletion

A B-tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. Deletion in a B Tree is similar to insertion. At first the node from which a value is to be deleted is searched. If found out, then the value is deleted.

Data Structures

B-Tree : Searching and Insertion

A B-tree is a self-balanced search tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. Unlike self-balancing binary search trees, it is optimized for systems that read and write large blocks of data like database and file systems

Data Structures

Ternary Search Trees

Ternary Search Tree is a special type of trie data structure and is widely used as an low memory alternative to trie in a vast range of applications like spell check and near neighbor searching. The average case time complexity is O(log N) for look-up, insertion and deletion operation.

Data Structures

How many labeled and unlabeled binary tree can be there with N nodes?

In this article, we see how many labeled and unlabeled binary trees we can have with N nodes. This is related to the Catalan Numbers. Binary Tree : A tree whose elements have 0 or 1 or 2 children is called a binary tree.

Algorithms

Maximize sum of consecutive differences in a circular array

Given an array A with values a1, a2, a3, a4, an Now, arrange all elements of array A such that sum of absolute differences of consecutive elements is maximum, i.e consider after an arrangement the array is b1, b2, b3, b4,..., bn then maximize |b1-b2| + |b2-b3| + |b3-b4| + .. + |bn-1-bn| + |bn-b1|

git

How Git uses Tree data structure concepts?

We have explored how Git version control system rely on Tree data structure concepts for its internal working. We have given an overview of the various important concepts in Git such as object store, index, blobs, tree, commit, tags and others.

Graph Algorithms

Graph Representation: Adjacency Matrix and Adjacency List

A Graph is represented in two major data structures namely Adjacency Matrix and Adjacency List. This forms the basis of every graph algorithm. In this article, we have explored the two graph data structures in depth and explain when to use one of them

linked list

Flattening a Linked List

In this article, we explored an algorithm to flatten a linked list where each node has two pointers with one to another linked list. Our approach explored a novel application of the merge component of merge sort to solve this problem.

linked list

Find the middle element of a singly Linked List

In this article, we will explore two approaches to find the middle element of a singly linked list. In one approach, we will use one traversal to count the number of elements and the other to find the middle element. The second approach is to use one traversal and concept of fast and slow pointers.

red black tree

Red Black Tree: Deletion

We will explore the deletion operation on a Red Black tree in the session. Deleting a value in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.

red black tree

Red Black Tree: Insertion

We will explore the insertion operation on a Red Black tree in the session. Inserting a value in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.

red black tree

Red Black Tree: Search

We will explore the search operation on a Red Black tree in the session. Searching in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.

Problems on Binary Tree

Properties of a Binary Tree

properties of Binary Tree are as follows: The maximum number of nodes at level ‘L’ of a binary tree is 2L-1, Maximum number of nodes in a binary tree of height ‘H’ is 2H – 1, In a Binary Tree with N nodes, minimum possible height or minimum number of levels is ⌈ Log2(N+1) ⌉

linked list

Sort a Linked List which is already sorted on absolute values

Algorithm Example Complexity Implementations Questions Reading time: 15 minutes | Coding time: 5 minutes The problem at hand is to sort a singly Linked List which is already sorted on absolute value. Sorting always

linked list

Merge Sort a singly Linked List

Algorithm Complexity Implementations Questions Merge sort is a fast comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Merge Sort is preferred for sorting a linked list.

linked list

Insert element in a sorted Linked List

Pseudocode Implementations Complexity Can binary search be used to improve performance? Reading time: 15 minutes | Coding time: 20 minutes In this session, we will explore how to insert an element in a sorted

linked list

Deletion operation in a Linked List

How to delete a node? Delete first node Delete last node Pseudocode Implementations Complexity Reading time: 15 minutes | Coding time: 20 minutes Linked List is an efficient data structure to store data. You

linked list

Insertion operation in a Linked List

How to insert a node at front? Insert a node at a particular location How to insert a node at end? Implementations Complexity Reading time: 15 minutes | Coding time: 20 minutes Linked List