Data Structures
Binary Search Tree
A Binary Search Tree (BST) is a data structure in which each node has at most two children and maintains the property that for every node, the values in its left subtree are less than the node’s value, and the values in its right subtree are greater.
Linked List
A data structure where each element contains a value and a reference to the next node, supporting efficient insertion and deletion operations.
- Time complexity for access and search is Linear, i.e. O(n)
- Time complexity for insertion and deletion is Constant, i.e. O(1)
- Space complexity is Linear
Minimum Heap
The Minimum Heap is a specialized binary tree that is based on the Heap data structure. It is also known as a Priority Queue.
N-Gram
The n-gram data structure is a simple container. It is used as a probabilistic model typically used in Natural Language Processing (NLP) to predict sequences of elements such as words or characters. It represents a sequence of \(n\) items from a given dataset, often applied for tasks like language modeling, auto-completion, and text prediction.
Queue
A linear collection following the First-In-First-Out (FIFO) principle, supporting operations like enqueue and dequeue, useful in task scheduling.
- Time complexity for access and search is Linear, i.e. O(n)
- Time complexity for insertion and deletion is Constant, i.e. O(n)
- Space complexity is Linear
Stack
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Elements are added and removed from the same end, called the top. Common operations include push (add an element), pop (remove the top element), and peek (view the top element without removing it). Stacks are used in various applications like function call management, expression evaluation, and backtracking.
Suffix Array
The suffix array algorithm constructs a sorted array of all suffixes of a given string, enabling efficient substring searches, pattern matching, and text analysis. It uses sorting and optional auxiliary structures like the LCP array for additional optimizations.
Ternary Search Trie
A Ternary Search Trie (TST) is a data structure used to store and retrieve strings efficiently, combining features of binary search trees and tries. It organizes data in a tree where each node contains three children (low, equal, high) corresponding to characters less than, equal to, or greater than the node’s character, enabling balanced search operations while conserving memory compared to standard tries.
Trie Symbol Table
The Trie Symbol Table is a data structure designed to efficiently store and retrieve key-value pairs where the keys are strings. It organizes data into a tree-like structure, where each node represents a character, and paths from the root to nodes represent strings.