Data structures
Arrays:
Working: Arrays are a contiguous collection of elements stored in memory. Elements are accessed by their index.
Example: int[] arr = {1, 2, 3, 4, 5};
Use cases: Used when constant-time random access to elements is required.
Operations: Access (O(1)), Insertion/Deletion (O(n)), Search (O(n)).
Linked Lists:
Working: A collection of nodes where each node contains a data element and a reference/pointer to the next node.
Example: LinkedList
Use cases: Dynamic memory allocation, implementing stacks, queues, etc.
Operations: Access (O(n)), Insertion/Deletion (O(1)), Search (O(n)).
Stacks:
Working: Follows Last-In-First-Out (LIFO) principle. Elements are added and removed from the same end, called the top.
Example: Stack
Use cases: Expression evaluation, backtracking in algorithms, function call management.
Operations: Push (O(1)), Pop (O(1)), Peek (O(1)).
Queues:
Working: Follows First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front.
Example: Queue
Use cases: Process scheduling, breadth-first search, implementing buffers.
Operations: Enqueue (O(1)), Dequeue (O(1)), Peek (O(1)).
Trees:
Working: A hierarchical data structure composed of nodes. Each node has a value and zero or more child nodes.
Example: Binary Search Tree, AVL Tree, etc.
Use cases: Organizing data for quick search, hierarchical data representation.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Binary Trees:
Working: Each node has at most two children - left and right.
Example: Binary Search Tree (BST).
Use cases: Efficient searching, sorting, and accessing hierarchical data.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Heaps:
Working: A complete binary tree where every parent node has a value less/greater than its children.
Example: Min Heap, Max Heap.
Use cases: Priority queues, heap sort.
Operations: Insertion (O(log n)), Deletion (O(log n)), Peek (O(1)).
Hash Tables:
Working: Utilizes a hash function to map keys to buckets, enabling constant-time average lookup.
Example: HashMap in Java.
Use cases: Fast lookup, caching, symbol tables.
Operations: Insertion (O(1)), Deletion (O(1)), Search (O(1)) on average.
Graphs:
Working: A collection of nodes (vertices) and edges connecting them.
Example: Social networks, road networks.
Use cases: Pathfinding, network analysis, recommendation systems.
Operations: Traversal (O(V + E)), Search (O(V + E)), Insertion (O(1)).
Tries:
Working: A tree-like data structure used to store a dynamic set of strings.
Example: Dictionary, autocomplete.
Use cases: Fast string searching, dictionary implementations.
Operations: Search (O(m)), Insertion (O(m)), Deletion (O(m)), where m is the length of the key.
Binary Search Trees (BST):
Working: A binary tree where the left child node has a value less than the parent node, and the right child node has a value greater than the parent node.
Example: Used in database indexing, symbol tables.
Use cases: Efficient searching, range queries.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)) on average, but O(n) in worst-case scenarios when the tree becomes unbalanced.
AVL Trees:
Working: A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one.
Example: Database indexing, symbol tables.
Use cases: Fast searching, insertion, and deletion.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Red-Black Trees:
Working: A self-balancing binary search tree where each node is either red or black, and the properties ensure the tree remains balanced.
Example: Used in C++ STL’s set and map implementations.
Use cases: Similar to AVL trees but with a slightly less strict balancing criteria.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
B-Trees:
Working: A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
Example: Used in file systems and databases.
Use cases: Organizing and managing large amounts of data efficiently.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
B+ Trees:
Working: A variation of B-tree in which all keys are present in the leaf nodes, and only data pointers are present in non-leaf nodes.
Example: Used in databases and filesystems.
Use cases: Range queries, indexing, and searching in databases.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Skip Lists:
Working: A probabilistic data structure that allows fast search, insertion, and deletion operations.
Example: Used in Redis and LevelDB.
Use cases: Alternative to balanced trees when simplicity and performance are key.
Operations: Search (O(log n) on average), Insertion (O(log n) on average), Deletion (O(log n) on average).
Fenwick Trees (Binary Indexed Trees):
Working: A tree data structure used to efficiently update and query prefix sums of an array.
Example: Used in competitive programming for range queries and updates.
Use cases: Range queries, cumulative frequency queries.
Operations: Update (O(log n)), Query (O(log n)).
Segment Trees:
Working: A tree data structure used for storing information about intervals or segments.
Example: Used in competitive programming and geometric algorithms.
Use cases: Range queries, range updates.
Operations: Update (O(log n)), Query (O(log n)).
Interval Trees:
Working: A tree data structure used for searching and storing intervals of the form [start, end].
Example: Used in scheduling problems, computational geometry.
Use cases: Finding overlapping intervals, scheduling problems.
Operations: Search (O(log n + k)), Insertion (O(log n + k)), Deletion (O(log n + k)), where k is the number of intervals.
Splay Trees:
Working: A self-adjusting binary search tree where recently accessed elements are quick to access again.
Example: Used in caches, memory allocation.
Use cases: Applications where locality of reference is important.
Operations: Search (O(log n) amortized), Insertion (O(log n) amortized), Deletion (O(log n) amortized).
Rope:
Working: A data structure for efficiently storing and manipulating large strings.
Example: Text editors like Emacs and Visual Studio.
Use cases: Text editing, string manipulation.
Operations: Concatenation (O(log n)), Substring extraction (O(log n)).
Bloom Filters:
Working: A space-efficient probabilistic data structure used to test whether an element is a member of a set.
Example: Network routers, spell checkers.
Use cases: Membership testing, duplicate elimination.
Operations: Insertion (O(k)), Membership test (O(k)), where k is the number of hash functions.
Disjoint-set (Union-find):
Working: A data structure that keeps track of a set of elements partitioned into disjoint subsets.
Example: Used in Kruskal’s algorithm for finding minimum
spanning trees.
Use cases: Connected components in graphs, dynamic connectivity.
Operations: Union (O(α(n))), Find (O(α(n))), where α(n) is the inverse Ackermann function.
Circular Buffer:
Working: A data structure that uses a single, fixed-size buffer as if it were connected end-to-end.
Example: Audio and video streaming, communication systems.
Use cases: Data streaming, real-time processing.
Operations: Enqueue (O(1)), Dequeue (O(1)).
Doubly Linked Lists:
Working: A linked data structure that consists of a set of sequentially linked records called nodes.
Example: Used in browser history, undo functionality.
Use cases: Insertion and deletion at both ends efficiently.
Operations: Access (O(n)), Insertion/Deletion (O(1)), Search (O(n)).
Priority Queues:
Working: A queue data structure where each element has a priority associated with it.
Example: Task scheduling, Huffman coding.
Use cases: Job scheduling, event-driven simulation.
Operations: Enqueue (O(log n)), Dequeue (O(log n)), Peek (O(1)).
Radix Trees (Trie with radix encoding):
Working: A space-optimized trie data structure used for storing a set of strings.
Example: IP routing tables, dictionary lookups.
Use cases: Efficient string storage and retrieval.
Operations: Search (O(m)), Insertion (O(m)), Deletion (O(m)), where m is the length of the key.
Suffix Trees:
Working: A tree data structure that represents all the suffixes of a given string.
Example: Used in bioinformatics for string matching and analysis.
Use cases: Pattern matching, substring search.
Operations: Search (O(m)), where m is the length of the pattern.
Suffix Arrays:
Working: An array of integers that represents the lexicographic order of all suffixes of a given string.
Example: Used in bioinformatics and text processing.
Use cases: Pattern matching, substring search.
Operations: Search (O(m * log n)), where m is the length of the pattern and n is the length of the string.
Patricia Tries:
Working: A compressed trie data structure where any node that is an only child is merged with its parent.
Example: Used in IP routing and network protocols.
Use cases: Space-efficient storage of strings, prefix search.
Operations: Search (O(m)), Insertion (O(m)), Deletion (O(m)), where m is the length of the key.
Multidimensional Arrays:
Working: An array structure with multiple indices to represent data in more than one dimension.
Example: Matrices, spreadsheet data.
Use cases: Image processing, scientific computing.
Operations: Access (O(1)), Insertion/Deletion (O(n^d)), Search (O(n^d)), where n is the size of each dimension and d is the number of dimensions.
Multiway Trees:
Working: A tree structure where each node can have more than two children.
Example: B-trees, Tries.
Use cases: Database indexing, filesystems.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)), where n is the number of nodes.
Quad Trees:
Working: A tree data structure in which each internal node has exactly four children.
Example: Used in image compression, spatial indexing.
Use cases: Image representation, collision detection.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)), where n is the number of nodes.
Oct Trees:
Working: A tree data structure in which each internal node has exactly eight children.
Example: Used in three-dimensional space partitioning, 3D rendering.
Use cases: Spatial indexing, collision detection.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)), where n is the number of nodes.
R Trees:
Working: A tree data structure used for spatial indexing of multi-dimensional data.
Example: Used in geographic information systems (GIS), database systems.
Use cases: Efficient retrieval of spatial data, nearest neighbor queries.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)), where n is the number of nodes.
C Trees:
Working: A cache-conscious variant of B-trees designed for efficient use of CPU caches.
Example: Used in databases, filesystems.
Use cases: Disk-based data storage, file systems.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)), where n is the number of nodes.
Dancing Links (DLX):
Working: A technique for representing exact cover problems using doubly linked lists.
Example: Sudoku solving, exact cover problem.
Use cases: Solving combinatorial optimization problems.
Operations: Dancing Links algorithm (backtracking with efficient data structure manipulation).
Ternary Search Trees:
Working: A type of trie data structure with three children at each node.
Example: Used in spell checkers, IP routing tables.
Use cases: String storage and retrieval, prefix search.
Operations: Search (O(m)), Insertion (O(m)), Deletion (O(m)), where m is the length of the key.
Cartesian Trees:
Working: A binary tree derived from a sequence of numbers, uniquely defined by the Cartesian coordinates of the points representing the numbers.
Example: Used in range minimum/maximum queries.
Use cases: Range queries, segment trees.
Operations: Construction (O(n)), Range queries (O(log n)).
Fenwick Trees of Fenwick Trees:
Working: A data structure that combines multiple Fenwick trees to efficiently perform range updates and queries.
Example: Used in competitive programming for range queries and updates on two-dimensional arrays.
Use cases: Efficient handling of two-dimensional cumulative frequency queries.
Operations: Update (O(log^2 n)), Query (O(log^2 n)).
Persistent Data Structures:
Working: Data structures that preserve previous versions of themselves when modified, enabling access to previous states.
Example: Persistent trees, persistent arrays.
Use cases: Version control systems, functional programming.
Operations: Access (O(log n)), Insertion/Deletion (O(log n)).
Self-balancing Trees:
Working: Trees that automatically maintain their balance to ensure efficient performance.
Example: AVL trees, Red-Black trees.
Use cases: Database indexing, symbol tables.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Interval Trees:
Working: A tree data structure used for searching and storing intervals of the form [start, end].
Example: Used in scheduling problems, computational geometry.
Use cases: Finding overlapping intervals, scheduling problems.
Operations: Search (O(log n + k)), Insertion (O(log n + k)), Deletion (O(log n + k)), where k is the number of intervals.
Fibonacci Heap:
Working: A type of heap data structure that supports arbitrary deletion and efficient decrease-key operations.
Example: Used in algorithms like Dijkstra’s shortest path algorithm.
Use cases: Shortest path algorithms, network flow algorithms.
Operations: Insertion (O(1)), Extract-min (O(log n)), Decrease-key (O(1)).
Treaps:
Working: A randomized data structure that combines the properties of binary search trees and heaps.
Example: Used in wireless communication protocols, dynamic programming.
Use cases: Priority queues, sorting.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)) on average.
Van Emde Boas Trees:
Working: A data structure that supports dynamic sets with operations like insert, delete, find, and predecessor/successor in O(log log n) time.
Example: Used in cache-oblivious algorithms, computational geometry.
Use cases: Efficient handling of large datasets, successor/predecessor queries.
Operations: Insertion (O(log log n)), Deletion (O(log log n)), Search (O(log log n)), Predecessor/Successor (O(log log n)).
X-fast Tries:
Working: A data structure that supports dynamic sets with operations like insert, delete, and search in O(log w) time, where w is the word size.
Example: Used in IP routing, computational biology.
Use cases: Fast search and retrieval of large datasets.
Operations: Insertion (O(log w)), Deletion (O(log w)), Search (O(log w)).
Y-fast Tries:
Working: An extension of X-fast tries that supports predecessor/successor queries in addition to insert, delete, and search operations.
Example: Used in computational geometry, network routing.
Use cases: Efficient handling of dynamic sets with predecessor/successor queries.
Operations: Insertion (O(log w)), Deletion (O(log w)), Search (O(log w)), Predecessor/Successor (O(log w)).
Min-max Heap:
Working: A data structure that supports both min and max operations efficiently.
Example: Used in tournament scheduling, online median finding.
Use cases: Applications requiring both min and max operations.
Operations: Insertion (O(log n)), Extract-min (O(log n)), Extract-max (O(log n)).
Double-ended Priority Queue:
Working: A priority queue that allows insertion and extraction of elements from both ends efficiently.
Example: Used in operating systems for task scheduling.
Use cases: Applications requiring efficient insertion and extraction at both ends.
Operations: Insertion (O(log n)), Extraction (O(log n)).
Min Heap:
Working: A binary tree where the parent node is smaller than or equal to its children.
Example: Used in heap sort, priority queues.
Use cases: Finding minimum element, implementing priority queues.
Operations: Insertion (O(log n)), Extract-min (O(log n)), Peek (O(1)).
Max Heap:
Working: A binary tree where the parent node is greater than or equal to its children.
Example: Used in heap sort, priority queues.
Use cases: Finding maximum element, implementing priority queues.
Operations: Insertion (O(log n)), Extract-max (O(log n)), Peek (O(1)).
Pairing Heap:
Working: A type of heap data structure that supports merging and arbitrary deletion in amortized logarithmic time.
Example: Used in network optimization, shortest path algorithms.
Use cases: Priority queues, graph algorithms.
Operations: Insertion (O(1)), Extract-min (O(log n)), Merge (O(1)).
D-ary Heap:
Working: A generalization of the binary heap in which each node has up to d children.
Example: Used in Dijkstra’s algorithm, Prim’s algorithm.
Use cases: Finding minimum/maximum elements, priority queues.
Operations: Insertion (O(logd n)), Extract-min (O(logd n)), Peek (O(1)).
Binomial Heap:
Working: A collection of binomial trees that satisfy the binomial heap properties.
Example: Used in priority queues, Dijkstra’s algorithm.
Use cases: Merging heaps efficiently, priority queues.
Operations: Insertion (O(log n)), Extract-min (O(log n)), Merge (O(log n)).
Fibonacci Heap:
Working: A type of heap data structure that supports arbitrary deletion and efficient decrease-key operations.
Example: Used in algorithms like Dijkstra’s shortest path algorithm.
Use cases: Shortest path algorithms, network flow algorithms.
Operations: Insertion (O(1)), Extract-min (O(log n)), Decrease-key (O(1)).
Soft Heap:
Working: A data structure that supports approximate min-max queries in constant time.
Example: Used in approximation algorithms, randomized algorithms.
Use cases: Approximate computations, statistical analysis.
Operations: Min/Max queries (O(1)), Insertion (O(log n)).
Ternary Heap:
Working: A heap data structure where each node has up to three children.
Example: Used in network protocols, optimization algorithms.
Use cases: Priority queues, graph algorithms.
Operations: Insertion (O(log n)), Extract-min (O(log n)), Peek (O(1)).
Scapegoat Tree:
Working: A self-balancing binary search tree that ensures worst-case logarithmic time for insertion, deletion, and search operations.
Example: Used in databases, file systems.
Use cases: Efficient storage and retrieval of data.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Rope (data structure):
Working: A data structure for efficiently storing and manipulating large strings by breaking them into smaller chunks.
Example: Used in text editors, word processors.
Use cases: Text editing, string manipulation.
Operations: Concatenation (O(log n)), Substring extraction (O(log n)).
Hash Array Mapped Trie:
Working: A data structure that combines the properties of hash maps and trie data structures, providing efficient storage and retrieval of key-value pairs.
Example: Used in functional programming languages like Clojure.
Use cases: Persistent data structures, immutable collections.
Operations: Insertion (O(log n)), Deletion (O(log n)), Search (O(log n)), where n is the number of elements.
B-heap:
Working: A generalization of the binary heap where each node can have up to b children.
Example: Used in priority queues, Dijkstra’s algorithm.
Use cases: Finding minimum/maximum elements, priority queues.
Operations: Insertion (O(logb n)), Extract-min (O(logb n)), Peek (O(1)).
Extensible Hashing:
Working: A dynamic hashing technique that allows a hash table to grow and shrink dynamically as the number of stored elements changes.
Example: Used in database systems, file systems.
Use cases: Hash table implementations, dynamic resizing.
Operations: Insertion (O(1) amortized), Deletion (O(1) amortized), Search (O(1) average).
Ctrie:
Working: A concurrent data structure that provides efficient and scalable access to a shared, mutable hash map.
Example: Used in concurrent programming, multi-threaded applications.
Use cases: Concurrent data access, synchronization.
Operations: Insertion (O(log n)), Deletion (O(log n)), Search (O(log n)), where n is the number of elements.
Fusion tree:
Working: A data structure that combines the properties of B-trees and van Emde Boas trees to support efficient searching, insertion, deletion, and range queries.
Example: Used in database indexing, file systems.
Use cases: Handling large datasets, range queries.
Operations: Insertion (O(log n)), Deletion (O(log n)), Search (O(log n)), Range queries (O(log n + k)), where n is the number of elements and k is the size of the range.
Link/Cut Tree:
Working: A data structure that maintains a forest of dynamic trees and supports various operations like tree linking, tree cutting, and path queries efficiently.
Example: Used in dynamic graph algorithms, network flow algorithms.
Use cases: Dynamic connectivity, path queries.
Operations: Link (O(log n)), Cut (O(log n)), Path queries (O(log n)).
Treap:
Working: A probabilistic data structure that combines the properties of binary search trees and heaps, using random priorities to maintain balance.
Example: Used in randomized algorithms, interval trees.
Use cases: Priority queues, randomized data structures.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)) on average.
Top Trees:
Working: A data structure that maintains the top-k elements of a dynamic set under updates efficiently.
Example: Used in streaming algorithms, data stream processing.
Use cases: Monitoring systems, real-time analytics.
Operations: Insertion (O(log n)), Deletion (O(log n)), Query (O(log k)).
Deterministic Skip List:
Working: A variant of skip lists that ensures deterministic behavior by avoiding randomization in the structure.
Example: Used in implementations where determinism is critical, such as databases.
Use cases: Database indexing, search algorithms.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Symmetric binary B-trees:
Working: A variant of B-trees optimized for storage efficiency, where each node contains only two children.
Example: Used in file systems, database systems.
Use cases: Efficient storage and retrieval of data, file systems.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Exponential tree:
Working: A tree data structure where each node has an exponentially increasing number of children.
Example: Used in combinatorial algorithms, decision trees.
Use cases: Solving combinatorial problems, search algorithms.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
T-tree:
Working: A balanced tree data structure similar to B-trees but optimized for high concurrency and efficient access in multi-core systems.
Example: Used in database systems, transaction processing.
Use cases: Concurrent data access, transaction management.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
2–3 heap:
Working: A type of heap data structure where each node can have either two or three children.
Example: Used in priority queues, Dijkstra’s algorithm.
Use cases: Finding minimum/maximum elements, priority queues.
Operations: Insertion (O(log n)), Extract-min (O(log n)), Peek (O(1)).
Weight-balanced tree:
Working: A self-balancing tree data structure where the balance of nodes is maintained based on the weight of their subtrees.
Example: Used in file systems, database indexing.
Use cases: Efficient storage and retrieval of data, range queries.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Spaghetti stack:
Working: A data structure for efficiently implementing dynamic-sized stacks by avoiding pointer-chasing overhead.
Example: Used in compilers, runtime systems.
Use cases: Function call stack management, expression evaluation.
Operations: Push (O(1)), Pop (O(1)), Peek (O(1)).
Binomial heap:
Working: A collection of binomial trees that satisfy the binomial heap properties.
Example: Used in priority queues, Dijkstra’s algorithm.
Use cases: Merging heaps efficiently, priority queues.
Operations: Insertion (O(log n)), Extract-min (O(log n)), Merge (O(log n)).
Splay tree:
Working: A self-adjusting binary search tree where recently accessed elements are moved to the root to optimize future accesses.
Example: Used in caches, memory allocation.
Use cases: Applications where locality of reference is important.
Operations: Search (O(log n) amortized), Insertion (O(log n) amortized), Deletion (O(log n) amortized).
Double-ended priority queue:
Working: A priority queue that supports insertion and extraction of elements from both ends efficiently.
Example: Used in operating systems for task scheduling.
Use cases: Applications requiring efficient insertion and extraction at both ends.
Operations: Insertion (O(log n)), Extraction (O(log n)).
XOR linked list:
Working: A memory-efficient doubly linked list where each node contains a XOR of the addresses of its predecessor and successor.
Example: Used in low-level programming, memory allocation.
Use cases: Memory-efficient linked list implementation.
Operations: Access (O(n)), Insertion/Deletion (O(1)).
K-d tree:
Working: A space-partitioning data structure used for organizing points in a k-dimensional space.
Example: Used in computational geometry, nearest neighbor search.
Use cases: Efficient range search, nearest neighbor search.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
AVL tree:
Working: A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one.
Example: Used in database indexing, symbol tables.
Use cases: Fast searching, insertion, and deletion.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Tangle tree:
Working: A variant of the AVL tree that allows for more efficient insertion and deletion operations.
Example: Used in databases, file systems.
Use cases: Efficient storage and retrieval of data, indexing.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
2-3-4 tree:
Working: A balanced search tree where each node can have 2, 3, or 4 children, maintaining balance and efficient searching.
Example: Used in database systems, file systems.
Use cases: Efficient storage and retrieval of data, range queries.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
AA tree:
Working: A variant of AVL trees that simplifies the balancing criteria to improve performance.
Example: Used in memory allocation, symbol tables.
Use cases: Fast searching, insertion, and deletion.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Quadtree:
Working: A tree data structure used to partition a two-dimensional space by recursively subdividing it into four quadrants.
Example: Used in image compression, collision detection.
Use cases: Spatial indexing, collision detection.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Octree:
Working: A tree data structure used to partition a three-dimensional space by recursively subdividing it into eight octants.
Example: Used in 3D computer graphics, physics simulations.
Use cases: Spatial indexing, collision detection.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
R-tree:
Working: A tree data structure used for spatial indexing of multi-dimensional data, particularly in databases and GIS.
Example: Used in spatial databases, geographic information systems (GIS).
Use cases: Efficient retrieval of spatial data, nearest neighbor queries.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
UB-tree:
Working: A variant of B-trees optimized for storage efficiency and fast search operations.
Example: Used in database systems, file systems.
Use cases: Efficient storage and retrieval of data, indexing.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
BK-tree:
Working: A tree data structure used for indexing a set of objects based on their similarity to each other using a metric space.
Example: Used in spell checking, similarity search.
Use cases: Approximate string matching, similarity search.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Link/Cut Tree:
Working: A data structure that maintains a forest of dynamic trees and supports various operations like tree linking, tree cutting, and path queries efficiently.
Example: Used in dynamic graph algorithms, network flow algorithms.
Use cases: Dynamic connectivity, path queries.
Operations: Link (O(log n)), Cut (O(log n)), Path queries (O(log n)).
Link/Cut Tree:
Working: The Link/Cut Tree is a dynamic data structure that maintains a forest of rooted trees, where each tree represents a dynamic set of elements. It supports efficient operations for modifying the trees, such as linking two trees together and cutting edges in the trees.
Basic Operations:
Linking: The Link operation combines two trees into one by adding an edge between a node in one tree and the root of the other tree. This operation effectively merges the two trees into a single tree. Cutting: The Cut operation removes an edge from the tree, effectively splitting the tree into two separate trees. This operation can disconnect a subtree from its parent tree. Path Queries: The Link/Cut Tree supports efficient path queries, such as finding the root of a node’s tree or accessing the parent of a node.
Use cases:
Dynamic Connectivity: Link/Cut Trees are used to maintain dynamic connectivity information in graph algorithms where edges can be added or removed dynamically. Dynamic Graph Algorithms: They are used in algorithms like dynamic minimum spanning tree algorithms, dynamic shortest path algorithms, and network flow algorithms. Network Flow Algorithms: Link/Cut Trees can be used to efficiently update flow networks and find augmenting paths in network flow algorithms like the push-relabel algorithm. Complexity:
The Link/Cut Tree data structure typically achieves logarithmic time complexity for its operations. Link and Cut operations, as well as path queries, can be performed in O(log n) time, where n is the number of nodes in the tree. Implementation Details:
Link/Cut Trees are often implemented using a combination of tree rotations, path reversal techniques, and amortized analysis to achieve efficient operations. Each node in the tree may store additional information to support efficient path queries, such as references to parent nodes or auxiliary data structures like splay trees. Advantages:
The Link/Cut Tree data structure provides a flexible and efficient way to manage dynamic sets of elements and perform various operations on them. It allows for fast updates to the structure of the tree, making it suitable for dynamic graph algorithms and network flow problems. Limitations:
Implementing Link/Cut Trees can be complex, requiring careful attention to detail to ensure correctness and efficiency. While Link/Cut Trees offer efficient operations, they may not always outperform simpler data structures for certain applications, especially when the tree structure changes frequently. Overall, the Link/Cut Tree data structure is a powerful tool for managing dynamic sets of elements and supporting efficient operations like linking, cutting, and path queries in dynamic graph algorithms and network flow problems.
Treap:
Working: A Treap, or a randomized binary search tree, is a data structure that combines the properties of binary search trees and binary heaps. Each node has a key (comparable value) and a priority (randomly assigned value). The keys follow the binary search tree property, while the priorities follow the heap property.
Example: Used in network protocols, randomized algorithms.
Use cases: Priority queues, randomized data structures.
Operations: Search (O(log n) average), Insertion (O(log n) average), Deletion (O(log n) average).
Top Trees:
Working: Top Trees maintain the top-k elements of a dynamic set under updates efficiently.
Example: Used in streaming algorithms, data stream processing.
Use cases: Monitoring systems, real-time analytics.
Operations: Insertion (O(log n)), Deletion (O(log n)), Query (O(log k)).
Deterministic Skip List:
Working: A variant of skip lists that ensures deterministic behavior by avoiding randomization in the structure.
Example: Used in implementations where determinism is critical, such as databases.
Use cases: Database indexing, search algorithms.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Symmetric binary B-trees:
Working: A variant of B-trees optimized for storage efficiency, where each node contains only two children.
Example: Used in file systems, database systems.
Use cases: Efficient storage and retrieval of data, file systems.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Exponential tree:
Working: A tree data structure where each node has an exponentially increasing number of children.
Example: Used in combinatorial algorithms, decision trees.
Use cases: Solving combinatorial problems, search algorithms.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
T-tree:
Working: A balanced tree data structure similar to B-trees but optimized for high concurrency and efficient access in multi-core systems.
Example: Used in database systems, transaction processing.
Use cases: Concurrent data access, transaction management.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
2-3 heap:
Working: A type of heap data structure where each node can have either two or three children.
Example: Used in priority queues, Dijkstra’s algorithm.
Use cases: Finding minimum/maximum elements, priority queues.
Operations: Insertion (O(log n)), Extract-min (O(log n)), Peek (O(1)).
Weight-balanced tree:
Working: A self-balancing tree data structure where the balance of nodes is maintained based on the weight of their subtrees.
Example: Used in file systems, database indexing.
Use cases: Efficient storage and retrieval of data, range queries.
Operations: Search (O(log n)), Insertion (O(log n)), Deletion (O(log n)).
Spaghetti stack:
Working: A data structure for efficiently implementing dynamic-sized stacks by avoiding pointer-chasing overhead.
Example: Used in compilers, runtime systems.
Use cases: Function call stack management, expression evaluation.
Operations: Push (O(1)), Pop (O(1)), Peek (O(1)).
Binomial heap:
- Working: A collection of binomial trees that satisfy the binomial heap properties.
- Example: Used in priority queues, Dijkstra’s algorithm.
- Use cases: Merging heaps efficiently, priority queues.
- Operations: Insertion (O(log n)), Extract-min (O(log n)), Merge (O(log n)).
Array Based
- DNF - seggregate data into 2/3 portions
- 2 Pointers
- sliding window
String
To check if the substring K is present in String S
- Robin karp
- KMP
Tree
For traversal
- pre-order
- post-order
- in-order
- level order
Graph
For traversal:
- BFS
- DFS