Compressed segment trees and merging sets in O(N*logN)
Compressed trees are a data structure that allows efficient queries and updates on a tree. The basic idea is to replace each subtree with a single node that represents the entire subtree. This reduces the size of the tree and makes it easier to perform operations on it.
Example:
Input: arr[] = {1, 2, 3, 5, 6, 8, 9 10}
Output: [1 3] [5 6] [8 10]
To implement a compressed tree, you can follow these general steps:
- Create a node structure that will hold the start and end values of a range, as well as pointers to the left and right child nodes. You can also include any additional data that you need for your specific use case.
- Create a function that will create a compressed tree from a set of values. To do this, you can convert the set to a vector and sort it. Then, iterate through the sorted vector and create nodes for each range of consecutive values. If a new value is consecutive with the current range, extend the range by updating the end value of the current node. Otherwise, create a new node for the current value and add it as a child of the appropriate parent node.
- Create any additional functions that you need for your use case, such as a function to traverse the compressed tree and perform some operation on each node.
Below is the implementation of the code:
C++
// C++ Implementation #include <iostream> #include <set> #include <vector> using namespace std; // Structure for a compressed tree node struct Node { int start; int end; Node* left; Node* right; Node( int s, int e) : start(s), end(e), left(nullptr), right(nullptr) { } }; // Helper function to create a compressed // tree from a set of integers Node* createTree(set< int >& s) { vector< int > values(s.begin(), s.end()); int n = values.size(); if (n == 0) return nullptr; Node* root = new Node(values[0], values[0]); Node* curr = root; for ( int i = 1; i < n; i++) { if (values[i] == curr->end + 1) { curr->end = values[i]; } else { Node* node = new Node(values[i], values[i]); if (values[i] < curr->start) { node->right = curr; curr = node; } else { Node* parent = curr; while (parent->right != nullptr && values[i] > parent->right->start) { parent = parent->right; } node->left = parent->right; parent->right = node; } curr = node; } } return root; } // Helper function to traverse a compressed // tree and print its nodes void traverseTree(Node* node) { if (node == nullptr) return ; traverseTree(node->left); cout << "[" << node->start << ", " << node->end << "] " ; traverseTree(node->right); } // Driver code int main() { // Create a set of integers and a // compressed tree from it set< int > s = { 1, 2, 3, 5, 6, 8, 9, 10 }; Node* root = createTree(s); // Traverse the compressed tree // and print its nodes cout << "This is the node of Compressed Segment Tree" << endl; traverseTree(root); return 0; } |
Java
import java.util.*; // Structure for a compressed tree node class Node { int start; int end; Node left; Node right; Node( int s, int e) { start = s; end = e; } } public class CompressedSegmentTree { // Helper function to create a compressed // tree from a set of integers public static Node createTree(Set<Integer> s) { List<Integer> values = new ArrayList<>(s); int n = values.size(); if (n == 0 ) return null ; Node root = new Node(values.get( 0 ), values.get( 0 )); Node curr = root; for ( int i = 1 ; i < n; i++) { if (values.get(i) == curr.end + 1 ) { curr.end = values.get(i); } else { Node node = new Node(values.get(i), values.get(i)); if (values.get(i) < curr.start) { node.right = curr; curr = node; } else { Node parent = curr; while (parent.right != null && values.get(i) > parent.right.start) { parent = parent.right; } node.left = parent.right; parent.right = node; } curr = node; } } return root; } // Helper function to traverse a compressed // tree and print its nodes public static void traverseTree(Node node) { if (node == null ) return ; traverseTree(node.left); System.out.print( "[" + node.start + ", " + node.end + "] " ); traverseTree(node.right); } // Driver code public static void main(String[] args) { // Create a set of integers and a // compressed tree from it Set<Integer> s = new HashSet<>( Arrays.asList( 1 , 2 , 3 , 5 , 6 , 8 , 9 , 10 )); Node root = createTree(s); // Traverse the compressed tree // and print its nodes System.out.println( "This is the node of Compressed Segment Tree" ); traverseTree(root); } } |
Python3
# Python Implementation # Structure for a compressed tree node class Node: def __init__( self , s, e): self .start = s self .end = e self .left = None self .right = None # Helper function to create a compressed # tree from a set of integers def createTree(s): values = sorted ( list (s)) n = len (values) if n = = 0 : return None root = Node(values[ 0 ], values[ 0 ]) curr = root for i in range ( 1 , n): if values[i] = = curr.end + 1 : curr.end = values[i] else : node = Node(values[i], values[i]) if values[i] < curr.start: node.right = curr curr = node else : parent = curr while (parent.right ! = None and values[i] > parent.right.start): parent = parent.right node.left = parent.right parent.right = node curr = node return root # Helper function to traverse a compressed # tree and print its nodes def traverseTree(node): if node = = None : return traverseTree(node.left) print ( "[{}, {}]" . format (node.start, node.end), end = " " ) traverseTree(node.right) # Driver code # Create a set of integers and a # compressed tree from it s = { 1 , 2 , 3 , 5 , 6 , 8 , 9 , 10 } root = createTree(s) # Traverse the compressed tree # and print its nodes print ( "This is the node of Compressed Segment Tree" ) traverseTree(root) |
C#
using System; using System.Collections.Generic; using System.Linq; // Structure for a compressed tree node public class Node { public int start; public int end; public Node left; public Node right; public Node( int s, int e) { start = s; end = e; left = null ; right = null ; } } public class Program { // Helper function to create a compressed tree from a // set of integers static Node createTree(SortedSet< int > s) { List< int > values = s.ToList(); int n = values.Count; if (n == 0) return null ; Node root = new Node(values[0], values[0]); Node curr = root; for ( int i = 1; i < n; i++) { if (values[i] == curr.end + 1) { curr.end = values[i]; } else { Node node = new Node(values[i], values[i]); if (values[i] < curr.start) { node.right = curr; curr = node; } else { Node parent = curr; while (parent.right != null && values[i] > parent.right.start) { parent = parent.right; } node.left = parent.right; parent.right = node; } curr = node; } } return root; } // Helper function to traverse a compressed tree and // print its nodes static void traverseTree(Node node) { if (node == null ) return ; traverseTree(node.left); Console.Write( "[{0}, {1}] " , node.start, node.end); traverseTree(node.right); } // Driver code static void Main() { // Create a set of integers and a compressed tree // from it SortedSet< int > s = new SortedSet< int >{ 1, 2, 3, 5, 6, 8, 9, 10 }; Node root = createTree(s); // Traverse the compressed tree and print its nodes Console.WriteLine( "This is the node of Compressed Segment Tree" ); traverseTree(root); } } // This code is contributed by Gaurav_Arora |
Javascript
// Structure for a compressed tree node class Node { constructor(s, e) { this .start = s; this .end = e; this .left = null ; this .right = null ; } } // Helper function to create a compressed // tree from a set of integers function createTree(s) { const values = [...s]; const n = values.length; if (n === 0) return null ; const root = new Node(values[0], values[0]); let curr = root; for (let i = 1; i < n; i++) { if (values[i] === curr.end + 1) { curr.end = values[i]; } else { const node = new Node(values[i], values[i]); if (values[i] < curr.start) { node.right = curr; curr = node; } else { let parent = curr; while (parent.right !== null && values[i] > parent.right.start) { parent = parent.right; } node.left = parent.right; parent.right = node; } curr = node; } } return root; } // Helper function to traverse a compressed // tree and print its nodes function traverseTree(node) { if (node === null ) return ; traverseTree(node.left); console.log(`[${node.start}, ${node.end}]`); traverseTree(node.right); } // Driver code const s = new Set([1, 2, 3, 5, 6, 8, 9, 10]); const root = createTree(s); // Traverse the compressed tree and print its nodes console.log( "This is the node of Compressed Segment Tree" ); traverseTree(root); |
This is the node of Compressed Segment Tree [1, 3] [5, 6] [8, 10]
Overall, this implementation is O(NlogN) because the createTree function takes O(N*logN) time to create the compressed tree, where N is the number of integers in the input set. In this implementation, createTree takes a set of integers and returns a compressed tree constructed from the values in the set. The traverseTree function recursively traverses the compressed tree and prints the start and end values of each node in the tree.
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Example:
Input: s1 = {1, 2, 3, 5, 6, 8, 9, 10}, s2 = {4, 7, 11, 12}
Output: s2 = {1, 2, 3, 4, 5, 6, 7, 8, 9 10, 11, 12}
To merge two sets of integers into a single set using compressed segment trees, we can follow these steps:
- Create two compressed segment trees, one for each set.
- Traverse the first compressed segment tree, and for each node, insert the range of integers represented by that node into the new set.
- Traverse the second compressed segment tree, and for each node, insert the range of integers represented by that node into the new set.
- The new set now contains all the integers from both original sets, sorted in ascending order.
Here is the C++ code to implement this algorithm:
C++
// C++ Implementation #include <iostream> #include <set> #include <vector> using namespace std; // Structure for a compressed tree node struct Node { int start; int end; Node* left; Node* right; Node( int s, int e) : start(s), end(e), left(nullptr), right(nullptr) { } }; // Helper function to create a compressed // tree from a set of integers Node* createTree(set< int >& s) { vector< int > values(s.begin(), s.end()); int n = values.size(); if (n == 0) return nullptr; Node* root = new Node(values[0], values[0]); Node* curr = root; for ( int i = 1; i < n; i++) { if (values[i] == curr->end + 1) { curr->end = values[i]; } else { Node* node = new Node(values[i], values[i]); if (values[i] < curr->start) { node->right = curr; curr = node; } else { Node* parent = curr; while (parent->right != nullptr && values[i] > parent->right->start) { parent = parent->right; } node->left = parent->right; parent->right = node; } curr = node; } } return root; } // Helper function to traverse a compressed // tree and insert its nodes into a set void traverseTreeAndInsert(Node* node, set< int >& s) { if (node == nullptr) return ; traverseTreeAndInsert(node->left, s); for ( int i = node->start; i <= node->end; i++) { s.insert(i); } traverseTreeAndInsert(node->right, s); } // Function to merge two sets using // compressed segment trees set< int > mergeSets(set< int >& s1, set< int >& s2) { // Create compressed segment // trees for both sets Node* root1 = createTree(s1); Node* root2 = createTree(s2); // Traverse both compressed trees and // insert their nodes into a new set set< int > result; traverseTreeAndInsert(root1, result); traverseTreeAndInsert(root2, result); // Clean up memory delete root1; delete root2; return result; } // Driver code int main() { // Create two sets of integers // and merge them set< int > s1 = { 1, 2, 3, 5, 6, 8, 9, 10 }; set< int > s2 = { 4, 7, 11, 12 }; set< int > result = mergeSets(s1, s2); // Print the merged set cout << "The set after merging is:" << endl; for ( int x : result) { cout << x << " " ; } return 0; } |
Java
// Java Implementation import java.util.*; // Structure for a compressed tree node class Node { int start; int end; Node left; Node right; public Node( int s, int e) { start = s; end = e; left = null ; right = null ; } } public class GFG { // Helper function to create a compressed // tree from a set of integers public static Node createTree(Set<Integer> s) { List<Integer> values = new ArrayList<>(s); int n = values.size(); if (n == 0 ) return null ; Node root = new Node(values.get( 0 ), values.get( 0 )); Node curr = root; for ( int i = 1 ; i < n; i++) { if (values.get(i) == curr.end + 1 ) { curr.end = values.get(i); } else { Node node = new Node(values.get(i), values.get(i)); if (values.get(i) < curr.start) { node.right = curr; curr = node; } else { Node parent = curr; while (parent.right != null && values.get(i) > parent.right.start) { parent = parent.right; } node.left = parent.right; parent.right = node; } curr = node; } } return root; } // Helper function to traverse a compressed tree // and insert its nodes into a set public static void traverseTreeAndInsert(Node node, Set<Integer> s) { if (node == null ) return ; traverseTreeAndInsert(node.left, s); for ( int i = node.start; i <= node.end; i++) { s.add(i); } traverseTreeAndInsert(node.right, s); } // Function to merge two sets using // compressed segment trees public static Set<Integer> mergeSets(Set<Integer> s1, Set<Integer> s2) { // Create compressed segment // trees for both sets Node root1 = createTree(s1); Node root2 = createTree(s2); // Traverse both compressed trees and // insert their nodes into a new set Set<Integer> result = new TreeSet<>(); traverseTreeAndInsert(root1, result); traverseTreeAndInsert(root2, result); // Clean up memory root1 = null ; root2 = null ; return result; } // Driver code public static void main(String[] args) { // Create two sets of integers // and merge them Set<Integer> s1 = new TreeSet<>(Arrays.asList( 1 , 2 , 3 , 5 , 6 , 8 , 9 , 10 )); Set<Integer> s2 = new TreeSet<>(Arrays.asList( 4 , 7 , 11 , 12 )); Set<Integer> result = mergeSets(s1, s2); // Print the merged set System.out.println( "The set after merging is:" ); for ( int x : result) { System.out.print(x + " " ); } } } // This code is contributed by Vaibhav Nandan |
Python3
# Python Implementation # Structure for a compressed tree node class Node: def __init__( self , start, end): self .start = start self .end = end self .left = None self .right = None # Helper function to create a compressed # tree from a set of integers def createTree(s): values = sorted ( list (s)) n = len (values) if n = = 0 : return None root = Node(values[ 0 ], values[ 0 ]) curr = root for i in range ( 1 , n): if values[i] = = curr.end + 1 : curr.end = values[i] else : node = Node(values[i], values[i]) if values[i] < curr.start: node.right = curr curr = node else : parent = curr while parent.right and values[i] > parent.right.start: parent = parent.right node.left = parent.right parent.right = node curr = node return root # Helper function to traverse a compressed # tree and insert its nodes into a set def traverseTreeAndInsert(node, s): if not node: return traverseTreeAndInsert(node.left, s) for i in range (node.start, node.end + 1 ): s.add(i) traverseTreeAndInsert(node.right, s) # Function to merge two sets using # compressed segment trees def mergeSets(s1, s2): # Create compressed segment # trees for both sets root1 = createTree(s1) root2 = createTree(s2) # Traverse both compressed trees and # insert their nodes into a new set result = set () traverseTreeAndInsert(root1, result) traverseTreeAndInsert(root2, result) # Clean up memory del root1 del root2 return result # Driver code if __name__ = = '__main__' : # Create two sets of integers # and merge them s1 = { 1 , 2 , 3 , 5 , 6 , 8 , 9 , 10 } s2 = { 4 , 7 , 11 , 12 } result = mergeSets(s1, s2) # Print the merged set print ( "The set after merging is:" ) for x in sorted (result): print (x, end = " " ) |
C#
using System; using System.Collections.Generic; public class Node { public int Start; public int End; public Node Left; public Node Right; public Node( int s, int e) { Start = s; End = e; Left = null ; Right = null ; } } public class Program { // Helper function to create a compressed tree from a set of integers public static Node CreateTree(HashSet< int > s) { List< int > values = new List< int >(s); int n = values.Count; if (n == 0) return null ; Node root = new Node(values[0], values[0]); Node curr = root; for ( int i = 1; i < n; i++) { if (values[i] == curr.End + 1) { curr.End = values[i]; } else { Node node = new Node(values[i], values[i]); if (values[i] < curr.Start) { node.Right = curr; curr = node; } else { Node parent = curr; while (parent.Right != null && values[i] > parent.Right.Start) { parent = parent.Right; } node.Left = parent.Right; parent.Right = node; } curr = node; } } return root; } // Helper function to traverse a compressed tree and insert its nodes into a set public static void TraverseTreeAndInsert(Node node, HashSet< int > s) { if (node == null ) return ; TraverseTreeAndInsert(node.Left, s); for ( int i = node.Start; i <= node.End; i++) { s.Add(i); } TraverseTreeAndInsert(node.Right, s); } // Function to merge two sets using compressed segment trees public static HashSet< int > MergeSets(HashSet< int > s1, HashSet< int > s2) { // Create compressed segment trees for both sets Node root1 = CreateTree(s1); Node root2 = CreateTree(s2); // Traverse both compressed trees and insert their nodes into a new set HashSet< int > result = new HashSet< int >(); TraverseTreeAndInsert(root1, result); TraverseTreeAndInsert(root2, result); // Clean up memory DeleteNode(root1); DeleteNode(root2); return result; } // Helper function to recursively delete nodes in the tree public static void DeleteNode(Node node) { if (node == null ) return ; DeleteNode(node.Left); DeleteNode(node.Right); node.Left = null ; node.Right = null ; } // Driver code public static void Main( string [] args) { // Create two sets of integers and merge them HashSet< int > s1 = new HashSet< int > { 1, 2, 3, 5, 6, 8, 9, 10 }; HashSet< int > s2 = new HashSet< int > { 4, 7, 11, 12 }; HashSet< int > result = MergeSets(s1, s2); // Print the merged set Console.WriteLine( "The set after merging is:" ); foreach ( int x in result) { Console.Write(x + " " ); } } } |
Javascript
// Structure for a compressed tree node class Node { constructor(s, e) { this .start = s; this .end = e; this .left = null ; this .right = null ; } } // Helper function to create a compressed // tree from a set of integers function createTree(s) { const values = [...s]; const n = values.length; if (n === 0) return null ; const root = new Node(values[0], values[0]); let curr = root; for (let i = 1; i < n; i++) { if (values[i] === curr.end + 1) { curr.end = values[i]; } else { const node = new Node(values[i], values[i]); if (values[i] < curr.start) { node.right = curr; curr = node; } else { let parent = curr; while (parent.right !== null && values[i] > parent.right.start) { parent = parent.right; } node.left = parent.right; parent.right = node; } curr = node; } } return root; } // Helper function to traverse a compressed tree // and insert its nodes into a set function traverseTreeAndInsert(node, s) { if (node === null ) return ; traverseTreeAndInsert(node.left, s); for (let i = node.start; i <= node.end; i++) { s.add(i); } traverseTreeAndInsert(node.right, s); } // Function to merge two sets using // compressed segment trees function mergeSets(s1, s2) { // Create compressed segment // trees for both sets let root1 = createTree(s1); let root2 = createTree(s2); // Traverse both compressed trees and // insert their nodes into a new set const result = new Set(); traverseTreeAndInsert(root1, result); traverseTreeAndInsert(root2, result); // Clean up memory root1 = null ; root2 = null ; return result; } function compare(a,b){ return a-b; } // Create two sets of integers and merge them const s1 = new Set([1, 2, 3, 5, 6, 8, 9, 10]); const s2 = new Set([4, 7, 11, 12]); let result = mergeSets(s1, s2); result=Array.from(result) result.sort(compare) // Print the merged set console.log( "The set after merging is:" ); for (const x of result) { console.log(x); } |
The set after merging is: 1 2 3 4 5 6 7 8 9 10 11 12
Time Complexity: O(N*logN)
Auxiliary Space: O(N)