Welcome to the Introduction to Advanced Data Structures lesson!

In this lesson, we will explore various advanced data structures that are used to organize and manipulate data efficiently. These data structures are designed to solve complex problems and optimize performance.

Some of the advanced data structures we will cover include segment trees, skip lists, tries, B-trees, splay trees, red-black trees, AVL trees, heap data structure, Fenwick trees, and suffix arrays.

Understanding these data structures will enhance your knowledge of algorithms and enable you to solve challenging problems.

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

  cout << "Welcome to the Introduction to Advanced Data Structures lesson!" << endl;

​

  // Brief overview of advanced data structures on a theoretical level

  cout << "In this lesson, we will explore various advanced data structures that are used to organize and manipulate data efficiently. These data structures are designed to solve complex problems and optimize performance." << endl;

​

  cout << "Some of the advanced data structures we will cover include segment trees, skip lists, tries, B-trees, splay trees, red-black trees, AVL trees, heap data structure, Fenwick trees, and suffix arrays." << endl;

​

  cout << "Understanding these data structures will enhance your knowledge of algorithms and enable you to solve challenging problems." << endl;

​

  return 0;

}

Welcome to the segment trees section of the lesson!

Segment trees are a powerful data structure used to efficiently handle range-based queries on arrays. They enable us to perform various operations such as finding the sum, minimum, maximum, or applying updates to a range of elements in an array.

To build a segment tree, we divide the array into smaller segments and calculate the required metric (e.g., sum) for each segment. These metrics are then combined to form the final tree structure, where each node represents a segment of the array.

Here's an example of building a segment tree for an array [1, 2, 3, 4, 5]:

1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6// Function to build the segment tree
7void buildSegmentTree(vector<int>& tree, vector<int>& arr, int start, int end, int treeNode) {
8    if (start == end) {
9        tree[treeNode] = arr[start];
10        return;
11    }
12
13    int mid = (start + end) / 2;
14
15    buildSegmentTree(tree, arr, start, mid, 2 * treeNode);
16    buildSegmentTree(tree, arr, mid + 1, end, 2 * treeNode + 1);
17
18    tree[treeNode] = tree[2 * treeNode] + tree[2 * treeNode + 1];
19}
20
21int main() {
22    vector<int> arr = {1, 2, 3, 4, 5};
23    int n = arr.size();
24
25    // Height of the segment tree
26    int treeHeight = (int)(ceil(log2(n)));
27    int treeSize = 2 * (int)pow(2, treeHeight) - 1;
28
29    // Create an empty segment tree
30    vector<int> tree(treeSize);
31
32    // Build the segment tree
33    buildSegmentTree(tree, arr, 0, n - 1, 1);
34
35    // Print the segment tree
36    for (int i = 1; i < treeSize; i++) {
37        cout << tree[i] << " ";
38    }
39    cout << endl;
40
41    return 0;
42}

In the above example, we define a function buildSegmentTree that recursively builds the segment tree. The tree is built by dividing the array into smaller segments until we reach the base case where the segment represents a single element. The tree is then constructed by combining the metrics of the child segments.

Feel free to run the code to see the segment tree for the given array.

Segment trees have various applications, including finding the sum of elements in a given range, updating values in a range of elements, and finding the minimum or maximum element in a range. They are particularly useful in scenarios where range-based queries are frequently performed.

Now that you have an overview of segment trees, let's dive deeper into their implementation and explore more advanced operations and optimizations!

xxxxxxxxxx

}

#include <iostream>

#include <vector>

​

using namespace std;

​

// Function to build the segment tree

void buildSegmentTree(vector<int>& tree, vector<int>& arr, int start, int end, int treeNode) {

    if (start == end) {

        tree[treeNode] = arr[start];

        return;

    }

​

    int mid = (start + end) / 2;

​

    buildSegmentTree(tree, arr, start, mid, 2 * treeNode);

    buildSegmentTree(tree, arr, mid + 1, end, 2 * treeNode + 1);

​

    tree[treeNode] = tree[2 * treeNode] + tree[2 * treeNode + 1];

}

​

int main() {

    vector<int> arr = {1, 2, 3, 4, 5};

    int n = arr.size();

​

    // Height of the segment tree

    int treeHeight = (int)(ceil(log2(n)));

    int treeSize = 2 * (int)pow(2, treeHeight) - 1;

​

    // Create an empty segment tree

Skip Lists are a probabilistic data structure that can be used to efficiently search, insert, and delete elements in a sorted list. They are similar to linked lists, but with additional levels called lists that contain a subset of the elements.

The main advantage of skip lists is that they provide logarithmic time complexity for search, insertion, and deletion operations with a relatively simple implementation.

Skip lists consist of multiple levels. The bottom level contains all the elements in sorted order. Each higher level contains a subset of the elements from the level below it. Each element in a higher level has a pointer to the next element at the lower level.

To perform a search operation, we start from the top level and compare the target value with the next value in the current list. If the target value is greater, we move to the next element. If the target value is smaller, we move down to the lower level and continue the process until we find the target value or reach the bottom level.

Here's an example of a skip list:

1  10 -> 20 -> 30 -> 40
2        |                  
3        v                  
4  10 ->    -> 30 -> 40
5        |                  
6        v                  
7  10 ->             -> 40
8                      |   
9                      v   
10  10 ->                      

xxxxxxxxxx

}

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

​

class SkipListNode {

public:

    int value;

    SkipListNode* next;

    SkipListNode* down;

​

    SkipListNode(int val) {

        value = val;

        next = nullptr;

        down = nullptr;

    }

};

​

class SkipList {

private:

    SkipListNode* head;

    int maxLevel;

    float probability;

​

public:

    SkipList(){

        head = nullptr;

        maxLevel = 1;

        probability = 0.5;

Tries

Tries, also known as prefix trees, are an efficient data structure used for storing and retrieving strings.

A trie is a tree-like structure where each node represents a character from a word. The root node represents an empty string, and the children of each node represent successive characters of the word. The word is stored by following the path from the root to the leaf node.

Tries provide an efficient way to search for a given word in a large set of words. They have a time complexity of O(L), where L is the length of the word.

Here's an example of a Trie data structure for storing words like "apple", "banana", and "cherry":

1            ''
2          ↙   ↘
3        a       b
4       |       |
5       p       a
6       |       |
7       p       n
8       |   ↙   ↘
9       l e       a
10                 |
11                 n
12                 |
13                 a

In the above example, each path from the root to a leaf represents a complete word. The path from the root to the node 'l' represents the word "apple".

Tries are commonly used in tasks such as autocomplete, spell checkers, and word search puzzles.

Let's take a look at the implementation of a Trie data structure in C++:

1<<code>>

In the code snippet above, we define a TrieNode struct that represents a node in the trie. Each TrieNode contains a map of characters to their corresponding child TrieNode, representing the children of the current node. We also define a Trie class that consists of the root TrieNode and provides the insert and search operations.

Try running the code to see how the Trie data structure can be used to insert and search for words.

Use Cases

Tries are useful in scenarios where we need to efficiently search for strings or perform operations based on string prefixes. Some common use cases for tries include:

• Autocompletion: Tries are commonly used in autocomplete features to suggest words as the user types.
• Spell checkers: Tries can be used to efficiently check the spelling of words by searching for them in a dictionary.
• Word search puzzles: Tries can be used to solve word search puzzles by efficiently searching for words in a grid of characters.
• IP routing: Tries can be used to store IP addresses and perform fast lookups for routing packets in computer networks.

Tries are a powerful data structure for handling string-related operations efficiently.

xxxxxxxxxx

}

#include <iostream>

#include <unordered_map>

​

using namespace std;

​

// Trie node

struct TrieNode {

    unordered_map<char, TrieNode*> children;

    bool isEndOfWord;

};

​

// Trie class

class Trie {

private:

    TrieNode* root;

​

public:

    // Constructor

    Trie() {

        root = new TrieNode();

    }

​

    // Insert a word into the trie

    void insert(string word) {

        TrieNode* curr = root;

        for (char c : word) {

            if (curr->children.find(c) == curr->children.end()) {

                curr->children[c] = new TrieNode();

            }

B-Trees

B-Trees are a type of self-balancing search tree that are commonly used in database systems. They are designed to efficiently store and retrieve large amounts of data.

A B-tree is similar to a binary search tree, but with some additional properties. Unlike a binary search tree, a B-tree can have more than two children per node. This allows for better balance and reduces the height of the tree.

The main advantage of B-trees is that they have a high degree of branching, which reduces the number of disk accesses required to search for an element. The branching factor of a B-tree determines the number of children each node can have.

B-trees are particularly useful in scenarios where the data is too large to fit in memory and is stored on disk. By minimizing disk access, B-trees can efficiently handle operations such as inserting, deleting, and searching for data.

Here's an example of a B-tree with a branching factor of 3:

1                   [E]
2           /         |        \
3       [B]       [H]     [M]
4    /    |     /   |    /  |  \
5 [A] [C] [D] [F] [J] [L] [O] [P]

In the above example, each node in the B-tree contains sorted keys. The child nodes between two keys contain values within the range defined by those keys.

The height of a B-tree represents the number of levels in the tree. By maintaining a balanced height, B-trees ensure efficient search operations.

Benefits of B-Trees

B-trees offer several benefits in database systems:

• Efficient disk access: The high degree of branching reduces the number of disk accesses required to search for data.
• Balanced height: B-trees maintain a balanced height, ensuring efficient search operations.
• Range queries: B-trees support range queries, allowing efficient retrieval of data within a specified range.
• Dynamic resizing: B-trees can dynamically resize to accommodate new data without requiring expensive rebalancing operations.

The implementation of a B-tree involves various operations such as searching for a key, inserting a key, and deleting a key. These operations require careful handling of node splits and merges to maintain the balanced property of the tree.

Try implementing a B-tree in C++ to gain a deeper understanding of its structure and operations!

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

  // B-tree implementation goes here

}

Splay Trees

Splay trees are a type of self-balancing binary search tree that prioritize recently accessed elements. Whenever an element is accessed or inserted, it is moved to the root of the tree, making it easier to access it again in the future.

Splay trees have a unique property called splay operation, which is used to move elements to the root. During a splay operation, the targeted element is rotated to the root, bringing it closer to the root for faster access.

The splay operation consists of three basic types of rotations:

• Zig: When the target node is the left child or right child of the root, a single rotation is performed to bring it to the root.
• Zig-Zig: When the target node and its parent are both left children or both right children, two rotations are performed to bring both of them to the root.
• Zig-Zag: When the target node and its parent are different children, two rotations are performed to bring the target node to the root.

The splay operation helps maintain a balance in the splay tree and ensures quick access to frequently accessed elements. It is a form of data reshuffling that adapts the tree's structure to the access pattern.

Splay trees are commonly used in scenarios where elements that have been recently accessed are more likely to be accessed again. Examples include caches, garbage collectors, and network protocols.

Here's an example of a splay tree:

1    50              40
2   /  \           / \
3  30   100   =>  30  50
4      /  \           /  \
5    40   200       100  200

In the above example, the element with key 40 is accessed, and it is moved to the root of the tree using the zig rotation.

Benefits of Splay Trees

Splay trees offer several benefits:

• Adaptive: Splay trees adapt their structure based on the access pattern, improving the performance of frequently accessed elements.
• Simple operations: The basic operations of accessing and inserting elements are simple and efficient, as elements are always moved to the root during these operations.
• No additional space: Splay trees do not require any additional space beyond the memory required to store the elements.

Splay trees are a powerful data structure that combines the benefits of a binary search tree with efficient access to frequently accessed elements. They are a great tool to have in your arsenal when dealing with applications that involve caching or frequent element access.

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Splay Tree node

struct Node {

  int key;

  Node* left;

  Node* right;

};

​

// Helper function to create a new node

Node* newNode(int key) {

  Node* node = new Node();

  node->key = key;

  node->left = node->right = NULL;

  return node;

}

​

int main() {

  // Create a new splay tree

  Node* root = newNode(100);

  root->left = newNode(50);

  root->right = newNode(200);

  root->left->left = newNode(40);

  root->left->left->left = newNode(30);

​

  // Perform operations on the splay tree

  // ...

​

Red-Black Trees

Red-Black Trees are a type of self-balancing binary search tree that maintain an extra attribute called "color" for each node. The color can be either red or black, and it is used to balance the tree during insertions and deletions.

Red-Black Trees follow several key properties:

1. Every node is either red or black.
2. The root of the tree is always black.
3. All leaves (NIL or nullptr) are black.
4. If a node is red, both its children are black.
5. Every path from a node to its descendant NIL nodes contains the same number of black nodes.

These properties ensure that the Red-Black Tree remains balanced, with an upper bound on the height of the tree. The balancing is achieved through color adjustments and tree rotations.

Red-Black Trees have a close relationship with B-trees. B-trees are a type of self-balancing search tree that is commonly used in database systems. Red-Black Trees are often used to analyze the theoretical performance of B-trees due to their similar balancing properties.

The C++ code snippet below demonstrates the structure of a Red-Black Tree and its properties:

1#include <iostream>
2using namespace std;
3
4// Function to explain Red-Black Trees
5void explainRedBlackTrees() {
6  cout << "Red-Black Trees are a type of self-balancing binary search tree." << endl;
7  cout << "They have an extra attribute, the color, which can be either red or black." << endl;
8  cout << "The color of a node is used to balance the tree during insertions and deletions." << endl;
9  cout << "The key properties of Red-Black Trees are:" << endl;
10  cout << "1. Every node is either red or black." << endl;
11  cout << "2. The root of the tree is always black." << endl;
12  cout << "3. All leaves (NIL or nullptr) are black." << endl;
13  cout << "4. If a node is red, both its children are black." << endl;
14  cout << "5. Every path from a node to its descendant NIL nodes contains the same number of black nodes." << endl;
15}
16
17int main() {
18  explainRedBlackTrees();
19  return 0;
20}

xxxxxxxxxx

#include <iostream>

using namespace std;

​

// Function to explain Red-Black Trees

void explainRedBlackTrees() {

  cout << "Red-Black Trees are a type of self-balancing binary search tree." << endl;

  cout << "They have an extra attribute, the color, which can be either red or black." << endl;

  cout << "The color of a node is used to balance the tree during insertions and deletions." << endl;

  cout << "The key properties of Red-Black Trees are:" << endl;

  cout << "1. Every node is either red or black." << endl;

  cout << "2. The root of the tree is always black." << endl;

  cout << "3. All leaves (NIL or nullptr) are black." << endl;

  cout << "4. If a node is red, both its children are black." << endl;

  cout << "5. Every path from a node to its descendant NIL nodes contains the same number of black nodes." << endl;

}

​

int main() {

  explainRedBlackTrees();

  return 0;

}

AVL Trees

AVL Trees are a type of self-balancing binary search tree that maintain the balance factor property. The balance factor of a node is the height of its left subtree minus the height of its right subtree. AVL Trees ensure that the balance factor of every node is either -1, 0, or 1. If the balance factor of a node is not in the range of -1 to 1, rotations are performed to restore balance.

These rotations maintain the height of the tree at O(log n), ensuring efficient search and insertion operations.

AVL Trees are similar to other self-balancing binary search trees like Red-Black Trees but with stricter balance conditions. While Red-Black Trees require a balance factor between -2 and 2, AVL Trees maintain a strict balance factor range of -1, 0, or 1.

The C++ code snippet below demonstrates the structure of an AVL Tree and explains the balance factor concept:

1// Function to explain AVL Trees
2void explainAVLTrees() {
3  cout << "AVL Trees are a type of self-balancing binary search tree that maintain the balance factor property." << endl;
4  cout << "The balance factor of a node is the height of its left subtree minus the height of its right subtree." << endl;
5  cout << "AVL Trees ensure that the balance factor of every node is either -1, 0, or 1." << endl;
6  cout << "If the balance factor of a node is not in the range of -1 to 1, rotations are performed to restore balance." << endl;
7  cout << "These rotations maintain the height of the tree at O(log n), ensuring efficient search and insertion operations." << endl;
8}
9
10int main() {
11  explainAVLTrees();
12  return 0;
13}

xxxxxxxxxx

#include <iostream>

using namespace std;

​

// Function to explain AVL Trees

void explainAVLTrees() {

  cout << "AVL Trees are a type of self-balancing binary search tree that maintain the balance factor property." << endl;

  cout << "The balance factor of a node is the height of its left subtree minus the height of its right subtree." << endl;

  cout << "AVL Trees ensure that the balance factor of every node is either -1, 0, or 1." << endl;

  cout << "If the balance factor of a node is not in the range of -1 to 1, rotations are performed to restore balance." << endl;

  cout << "These rotations maintain the height of the tree at O(log n), ensuring efficient search and insertion operations." << endl;

}

​

int main() {

  explainAVLTrees();

  return 0;

}

Heap Data Structure

The Heap data structure is a complete binary tree that satisfies the heap property. The heap property states that the key of each parent node is either greater than or equal to its child nodes (for a max heap), or smaller than or equal to its child nodes (for a min heap).

The heap data structure is commonly used to implement priority queues, which allow quick retrieval of the minimum or maximum element from a collection of elements.

Max Heapify

The Max Heapify operation is used to maintain the heap property in a max heap. It compares the key of a parent node with its two child nodes and swaps the parent node with the child that has the maximum key value, ensuring that the largest element is always at the root of the heap.

Here is an example of the Max Heapify operation in C++:

1#include <iostream>
2using namespace std;
3
4// Function to perform max heapify operation
5void maxHeapify(int arr[], int n, int i) {
6  int largest = i;
7  int l = 2 * i + 1;
8  int r = 2 * i + 2;
9
10  // If left child is larger than root
11  if (l < n && arr[l] > arr[largest])
12    largest = l;
13
14  // If right child is larger than largest so far
15  if (r < n && arr[r] > arr[largest])
16    largest = r;
17
18  // If largest is not root
19  if (largest != i) {
20    swap(arr[i], arr[largest]);
21
22    // Recursively heapify the affected sub-tree
23    maxHeapify(arr, n, largest);
24  }
25}
26
27int main() {
28  int arr[] = {12, 11, 13, 5, 6, 7};
29  int n = sizeof(arr) / sizeof(arr[0]);
30
31  maxHeapify(arr, n, 0);
32
33  cout << "Max Heapified array:\n";
34  for (int i = 0; i < n; i++)
35    cout << arr[i] << " ";
36
37  return 0;
38}

The output of the above code would be:

1Max Heapified array:
213 11 12 5 6 7

Build Max Heap

The Build Max Heap operation is used to convert an array into a max heap. It iterates over the array from the last non-leaf node to the first element and applies the Max Heapify operation to each node. This operation ensures that the entire array satisfies the heap property.

Here is an example of the Build Max Heap operation in C++:

1#include <iostream>
2using namespace std;
3
4// Function to perform max heapify operation
5void maxHeapify(int arr[], int n, int i) {
6  // max heapify logic here
7}
8
9// Function to convert an array into a max heap
10void buildMaxHeap(int arr[], int n) {
11  // Find the index of the last non-leaf node
12  int startIdx = (n / 2) - 1;
13
14  // Perform reverse level order traversal from the last non-leaf node
15  // and heapify each node
16  for (int i = startIdx; i >= 0; i--) {
17    maxHeapify(arr, n, i);
18  }
19}
20
21int main() {
22  int arr[] = {12, 11, 13, 5, 6, 7};
23  int n = sizeof(arr) / sizeof(arr[0]);
24
25  buildMaxHeap(arr, n);
26
27  cout << "Max Heapified array:\n";
28  for (int i = 0; i < n; i++)
29    cout << arr[i] << " ";
30
31  return 0;
32}

The output of the above code would be:

1Max Heapified array:
213 11 12 5 6 7

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Function to perform max heapify operation

void maxHeapify(int arr[], int n, int i) {

  int largest = i; 

  int l = 2 * i + 1; 

  int r = 2 * i + 2; 

​

  // If left child is larger than root

  if (l < n && arr[l] > arr[largest])

    largest = l;

​

  // If right child is larger than largest so far

  if (r < n && arr[r] > arr[largest])

    largest = r;

​

  // If largest is not root

  if (largest != i) {

    swap(arr[i], arr[largest]);

​

    // Recursively heapify the affected sub-tree

    maxHeapify(arr, n, largest);

  }

}

​

// Function to convert an array into a max heap

void buildMaxHeap(int arr[], int n) {

  // Index of last non-leaf node

Fenwick Trees

Fenwick trees, also known as Binary Indexed Trees (BIT), are a data structure that efficiently supports range sum queries and updates in an array of numbers.

Fenwick trees are particularly useful when dealing with problems that involve updating array elements frequently and performing range sum queries.

The main idea behind Fenwick trees is to use the binary representation of the array indexes to store partial sums. Each index of the Fenwick tree corresponds to a range of indexes in the original array.

Here's the basic interface of a Fenwick tree implemented in C++:

1#include <iostream>
2#include <vector>
3using namespace std;
4
5class FenwickTree {
6private:
7  vector<int> tree;
8
9public:
10  FenwickTree(int n) {
11    tree.resize(n + 1, 0);
12  }
13
14  void update(int index, int value) {
15    while (index < tree.size()) {
16      tree[index] += value;
17      index += index & (-index);
18    }
19  }
20
21  int getPrefixSum(int index) {
22    int sum = 0;
23    while (index > 0) {
24      sum += tree[index];
25      index -= index & (-index);
26    }
27    return sum;
28  }
29
30  int getRangeSum(int start, int end) {
31    return getPrefixSum(end) - getPrefixSum(start - 1);
32  }
33};
34
35int main() {
36  vector<int> arr = {3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3};
37  int n = arr.size();
38
39  FenwickTree ft(n);
40
41  // Build Fenwick tree
42  for (int i = 0; i < n; i++) {
43    ft.update(i + 1, arr[i]);
44  }
45
46  // Get range sum from index 2 to index 8
47  int rangeSum = ft.getRangeSum(2, 8);
48  cout << "Range Sum: " << rangeSum << endl;
49
50  return 0;
51}

The output of the above code would be:

1Range Sum: 17

xxxxxxxxxx

#include <iostream>

#include <vector>

using namespace std;

​

// Fenwick Tree implementation

Suffix Arrays

Suffix arrays are data structures that store all the suffixes of a given string in a sorted order. A suffix is a substring that starts from a specific index in the original string.

Suffix arrays are commonly used in string algorithms, especially for problems like pattern matching, substring queries, and sorting.

The main advantage of using a suffix array is its space efficiency compared to other data structures like suffix trees. Suffix arrays can be constructed efficiently in O(n log n) time complexity, where n is the length of the input string.

To build a suffix array for a string, we can start by creating a list of pairs, where each pair consists of a suffix and its corresponding starting index. We then sort the list of pairs based on the suffixes, and finally, extract the sorted starting indexes to form the suffix array.

Here's an example of building a suffix array in C++:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7vector<int> buildSuffixArray(string str) {
8  int n = str.size();
9  vector<int> suffixArray(n, 0);
10
11  vector<pair<string, int>> suffixes(n);
12  for (int i = 0; i < n; i++) {
13    suffixes[i] = {str.substr(i, n - i), i};
14  }
15
16  sort(suffixes.begin(), suffixes.end());
17
18  for (int i = 0; i < n; i++) {
19    suffixArray[i] = suffixes[i].second;
20  }
21
22  return suffixArray;
23}
24
25int main() {
26  string str = "banana";
27
28  vector<int> suffixArray = buildSuffixArray(str);
29
30  cout << "Suffix Array: ";
31  for (int index : suffixArray) {
32    cout << index << " ";
33  }
34  cout << endl;
35
36  return 0;
37}

The output of the above code would be:

1Suffix Array: 5 3 1 0 4 2

xxxxxxxxxx

}

#include <iostream>

#include <vector>

#include <algorithm>

​

using namespace std;

​

vector<int> buildSuffixArray(string str) {

  int n = str.size();

  vector<int> suffixArray(n, 0);

​

  vector<pair<string, int>> suffixes(n);

  for (int i = 0; i < n; i++) {

    suffixes[i] = {str.substr(i, n - i), i};

  }

​

  sort(suffixes.begin(), suffixes.end());

​

  for (int i = 0; i < n; i++) {

    suffixArray[i] = suffixes[i].second;

  }

​

  return suffixArray;

}

​

int main() {

  string str = "banana";

​

  vector<int> suffixArray = buildSuffixArray(str);

​