Advance DS | Notion

Adjacency List:
- An adjacency list represents a graph using an array of linked lists.
- Each index in the array corresponds to a vertex, and the linked list at that index contains the other vertices connected to the current vertex.
- Pros:
  - Efficient storage for sparse graphs (millions of vertices and edges).
  - Easy to find adjacent vertices.
- Cons:
  - Slower for finding adjacent vertices compared to an adjacency matrix.
- Structure:
  
  struct node { int vertex; struct node* next; }; struct Graph { int numVertices; struct node** adjLists; };
Adjacency Matrix:
- Represents a graph as a boolean matrix (0’s and 1’s).
- The value at matrix[i][j] indicates whether there is a direct edge between vertices i and j.
- Pros:
  - Efficient for basic operations (adding/removing edges, checking connectivity).
  - Useful for dense graphs.
  - GPU-friendly for matrix operations.
- Cons:
  - High memory usage (VxV space).
  - Inefficient for sparse graphs.
- Applications:
  - Creating routing tables in networks.
  - Navigation tasks.
BK-Tree:
- Used for efficient word searching based on Levenshtein distance (edit distance).
- Tree-like structure where each node represents a word, and children represent words with a specific edit distance.
Segment Tree:
- Stores information about a range of elements in its nodes.
- Supports range queries and updates efficiently.
- Operations (e.g., addition, maximum, minimum) must be binary and associative.
- Works on the divide-and-conquer principle.
- Generally represented using an array.
Segment Trees:

Applications:
- Interval Scheduling: Segment trees efficiently schedule non-overlapping intervals, such as appointments or resource allocation.
- Range-based Statistics: Compute statistics (e.g., variance, standard deviation, percentiles) for a range of elements.
- Image Processing: Divide an image into segments based on color, texture, or other attributes.
Advantages:
- Efficient querying for aggregate values (min, max, sum) within a range.
- Efficient updates (incrementing, decrementing) for a range of elements.
- Versatility in solving various range query problems.
Disadvantages:
- Complexity in implementation and maintenance, especially for large arrays or high dimensions.
- Higher time complexity (O(log N)) compared to some other data structures like Fenwick trees.
- Relatively high space complexity (O(4N)).

Palindromic Tree:

Purpose: Designed for efficient string processing tasks (pattern matching, string searching, spell-checking).
Characteristics:
- Efficiently handles palindromic substrings.
- Tree-based structure optimized for palindromic strings.
Structure:
- Combined structure merging two trees with common nodes.
- Edges:
  - Insertion edges (weighted) form new nodes by adding characters at palindrome ends.
  - Maximum Palindromic Suffix edges (unweighted) point to the largest palindromic suffix node.

Ternary Search Tree:

A special trie where child nodes are ordered as a binary search tree.
Each node has three pointers:
1. Left: Node with value less than current node.
2. Equal: Node with equal value.
3. Right: Node with value greater than current node.
Additional fields for data (e.g., character) and marking end of a string.
Applications:
1. Near-neighbor lookups (finding next word in a dictionary).
2. Spell checks (parallel search for correct spelling).

Trie:

Derived from “retrieval.”