Cartesian Tree Sorting is an innovative sorting technique that utilizes the Cartesian tree data structure to efficiently sort a sequence of exceptional numbers. Understanding the principles behind Cartesian trees, how they are constructed, and the sorting procedure is crucial to grasp this algorithm.
A Cartesian tree is a type of binary tree that originates from a specific set of unique numbers. Every node within this tree corresponds to a number from the original set and possesses key characteristics: a numerical value and a corresponding priority. The hierarchy of a node is established based on its position in the initial sequence. In particular, nodes situated towards the start of the sequence are assigned greater priorities compared to those towards the end. The construction of a Cartesian tree follows a methodical procedure that progresses through the entire input sequence.
As every item is discovered, a related node is generated and incorporated into the tree while following the guidelines that govern the order of precedence. A method based on stacks is frequently utilized throughout this procedure, guaranteeing the maintenance of Cartesian tree characteristics with the introduction of fresh nodes.
Insertion requires evaluating current nodes, prompting modifications in the tree layout to maintain specific Cartesian tree characteristics. This algorithm demonstrates its effectiveness particularly with sequences containing unique values, offering advantageous performance in situations where constructing a Cartesian tree supports broader computational goals.
Method-1: Recursive Cartesian Tree Sort
Recursive Cartesian Tree Sort involves implementing the Cartesian Tree Sort algorithm using a recursive approach to build the Cartesian tree and execute an in-order traversal. The Cartesian tree, a binary tree created from a series of unique numbers, plays a crucial part in sorting the input sequence.
Cartesian Tree:
The input sequence is designed in a way that associates each node in the tree with a value from the sequence. The node priorities are established based on the element order, and the Cartesian tree property guarantees that the sorted sequence is obtained when the tree is traversed in-order.
Recursive Approach:
Dividing the task into smaller subtasks is a key aspect of the recursive Cartesian Tree Sort algorithm. This is achieved by iteratively forming the Cartesian tree for subsets of the array.
Program:
#include <iostream>
using namespace std;
struct Node {
int value;
Node* left;
Node* right;
};
Node* buildCartesianTree(int arr[], int start, int end) {
if (start > end) {
return nullptr;
}
int minIndex = start;
for (int i = start + 1; i <= end; ++i) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
Node* root = new Node{arr[minIndex], nullptr, nullptr};
root->left = buildCartesianTree(arr, start, minIndex - 1);
root->right = buildCartesianTree(arr, minIndex + 1, end);
return root;
}
void inOrderTraversal(Node* root) {
if (root) {
inOrderTraversal(root->left);
cout << root->value << " ";
inOrderTraversal(root->right);
}
}
void cartesianTreeSort(int arr[], int n) {
Node* root = buildCartesianTree(arr, 0, n - 1);
inOrderTraversal(root);
}
int main() {
int arr[] = {5, 10, 40, 30, 28};
int n = sizeof(arr) / sizeof(arr[0]);
cartesianTreeSort(arr, n);
return 0;
}
Output:
5 10 40 30 28
Explanation:
Node Structure:
The 'Node' structure symbolizes a node found in the Cartesian tree. It consists of three parts: 'value' storing the node's value, 'left' pointing to the left child node, and 'right' pointing to the right child node.
buildCartesianTree Function:
- The buildCartesianTree function recursively constructs a Cartesian tree for a given subarray of the input array.
- It takes three parameters: arr (the input array), start (the starting index of the current subarray), and end (the ending index of the current subarray). The base case checks if start > end, and if true, it returns nullptr , indicating an empty tree.
- The function then finds the index of the minimum element in the current subarray. It initializes a Node with the value of the minimum element and recursively builds the left and right subtrees.
The inOrderTraversal method executes an in-order traversal of the Cartesian tree by accepting a Node* root parameter and displaying the values in ascending order. This process includes exploring the left subtree, displaying the current node's value, and then exploring the right subtree.
cartesianTreeSort method:
The cartesianTreeSort method serves as the starting point for the Cartesian Tree Sort algorithm. It accepts the array arr and its size n as parameters.
Upon invocation, it triggers the buildCartesianTree method to create the Cartesian tree, followed by a call to inOrderTraversal to display the sorted sequence.
Main function:
In the primary function, a sample array named arr is declared as: {5, 10, 40, 30, 28}. The array's size is computed, and then the cartesianTreeSort function is invoked with the array and its size.
The software displays the arranged sequence, which is the outcome of the Cartesian Tree Sort technique.
Complexity Analysis:
Time Complexity Analysis:
Develop Cartesian Tree (buildCartesianTree method):
The function iteratively builds the Cartesian tree by visiting each element exactly once.
At every iteration of the recursive function, it manages a uniform quantity of items, which includes operations such as identifying the smallest value and generating a new node.
The duration required to construct the Cartesian tree exhibits a computational complexity of O(n log n), with 'n' representing the number of elements present in the input array.
In-order Traversal (inOrderTraversal function):
In-order traversal visits each node exactly once.
The time complexity of performing an in-order traversal is O(n), where the variable 'n' represents the total number of nodes present in the Cartesian tree.
By merging the time complexities associated with constructing the Cartesian tree and executing an in-order traversal, the overall time complexity of Cartesian Tree Sort amounts to O(n log n).
Space Complexity Analysis:
Node Structures:
Each item in the given array represents a specific node in the Cartesian tree. The storage requirements for these nodes increase in direct proportion to the array's size.
The space complexity for node structures is O(n).
Recursion Stack:
The iterative invocations within the buildCartesianTree function impact the allocation of space in the call stack.
The highest level of recursion involved in constructing the Cartesian tree aligns with the tree's vertical dimension. In the most unfavorable circumstance, the vertical extent of the Cartesian tree amounts to the logarithm of 'n', where 'n' denotes the quantity of items present in the initial array.
The space complexity stemming from the recursive stack amounts to O(log n).
Combining the memory requirements of node structures and the stack used for recursion, the total space complexity of Cartesian Tree Sort amounts to O(n + log n).
In real-world scenarios, the primary consideration is the amount of space needed for node configurations, with the impact of the recursive stack being relatively minor.
Method-2: Iterative Cartesian Tree Sort with Stack
Iterative Cartesian Tree Sort with a stack utilizes an iterative strategy along with a stack data structure to construct the Cartesian tree. By steering clear of the usual recursive calls, this technique offers a different way to handle the tree building process. The stack comes into play to maintain the progress of the Cartesian tree as the iteration unfolds. Key stages involve creating nodes, constructing the tree using the stack, and executing an in-order traversal to achieve sorting.
Program:
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int value;
int index;
Node* left;
Node* right;
};
//function to perform iterative Cartesian Tree Sort
void iterativeCartesianTreeSort(int arr[], int n) {
stack<Node*> s;
for (int i = 0; i < n; ++i) {
Node* cur = new Node{arr[i], i, nullptr, nullptr};
// Check and adjust the stack to maintain Cartesian tree properties
while (!s.empty() && s.top()->value > arr[i]) {
s.pop();
}
// If the stack is not empty, set the right child of the top element
if (!s.empty()) {
cur->left = s.top()->right;
s.top()->right = cur;
} else {
// If the stack is empty, the current node is the root
s.push(cur);
}
}
// The top of the stack after the iteration represents the root
Node* root = s.top();
// Perform in-order traversal for sorting
stack<Node*> inOrderStack;
while (root || !inOrderStack.empty()) {
while (root) {
inOrderStack.push(root);
root = root->left;
}
root = inOrderStack.top();
inOrderStack.pop();
cout << root->value << " ";
root = root->right;
}
}
int main() {
int arr[] = {5, 10, 40, 30, 28};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sorted Sequence: ";
iterativeCartesianTreeSort(arr, n);
return 0;
}
Output:
Sorted Sequence: 5 10 40 30 28
Explanation:
Node Creation:
- The process commences with cycling through the unique number sequence provided as input.
- A new node is generated for every element, encompassing the element's value, its position in the sequence, and setting both left and right pointers to nullptr.
Stack-Based Tree Construction:
- A stack (s) is utilized to maintain a partial Cartesian tree during the iteration. For each node, its value is compared with the top of the stack.
- Suppose the current node's value is smaller than the top of the stack. In that case, it means the current node should be the left child of the top node on the stack, and this process is repeated until an appropriate position for the current node is found.
- The current node is then pushed onto the stack.
Final Cartesian Tree:
The highest position in the stack following the iteration signifies the primary node of the Cartesian tree.
In-Order Traversal for Sorting:
- To obtain the sorted sequence, the algorithm performs an in-order traversal of the Cartesian tree. During the traversal, the algorithm uses a second stack (inOrderStack) to keep track of nodes.
- The traversal begins from the root and moves left until the leftmost node is reached. Nodes are pushed onto the inOrderStack during this process.
- Once the leftmost node is reached, it is popped from the inOrderStack, its value is printed, and the algorithm moves to its right child. This process continues until all nodes are processed.
Key Points:
- The algorithm efficiently maintains the Cartesian tree structure using a stack, avoiding recursive calls. It takes advantage of the stack to adjust the Cartesian tree properties during the iteration.
- The in-order traversal ensures that the sorted sequence is obtained from the Cartesian tree.
- Iterative Cartesian Tree Sort with Stack is an efficient algorithm for sorting a sequence using an iterative approach, a stack, and the properties of Cartesian trees. It achieves a linear time complexity and linear space complexity, making it a practical sorting solution.
Complexity Analysis:
Time Complexity:
Node Construction and Stack Operations:
Every item within the given sequence is processed exactly once. The algorithm performs a consistent set of stack operations for each individual element.
In the context of creating nodes and performing stack operations, the total time complexity is O(n), with 'n' representing the quantity of elements in the input sequence.
In-Order Traversal:
The in-order traversal is executed individually for every node present in the Cartesian tree.
The time complexity associated with performing an in-order traversal is O(n), where 'n' represents the total count of nodes present within the Cartesian tree.
Blending the intricacies of node formation, stack manipulations, and sequential traversal, the overall time complexity of Iterative Cartesian Tree Sort with Stack amounts to O(n).
Space Complexity:
Node Structures:
Each item in the provided array corresponds to a vertex in the Cartesian tree. The storage requirements for these vertices grow in proportion to the array size.
The space complexity for node structures is O(n).
Stacks (s and inOrderStack):
The algorithm employs a pair of stacks (s for constructing the tree and inOrderStack for traversing).
The maximum capacity of each stack is directly related to the height of the Cartesian tree, which amounts to log(n) under the most unfavorable circumstances.
The space complexity for both stacks is O(log n).
Combining the memory requirements of node structures and the two stacks, the total memory complexity of Iterative Cartesian Tree Sort with Stack is O(n + log n).
In reality, the primary consideration is the amount of space needed for node configurations, with the impact from the stacks being relatively minor.
The algorithm demonstrates efficiency with a linear time complexity, which is ideal for sorting extensive datasets. Additionally, the space complexity is manageable, contributing to the algorithm's strong performance in real-world scenarios.
Method-3: Using Segment Tree
Creating a Cartesian Tree Sort with the help of a Segment Tree revolves around effectively identifying the smallest element within a specified range. This strategy constructs the Cartesian tree by picking the minimum element within each segment of the initial array. The fundamental concept is to leverage a Segment Tree data structure to promptly respond to inquiries regarding the minimum value in a given range.
Segment Tree Overview:
A Segment Tree is a data structure in the form of a binary tree that is employed to store data related to intervals or segments.
Each terminal node in the Segment Tree corresponds to a value in the original input array.
Each internal node contains the minimum value of its child nodes.
Cartesian Tree Sort using Segment Tree:
Node Structure:
A Node stands for an element in the Cartesian tree arrangement. Each individual node contains the minimum data value, the corresponding index of that minimum value, and references to its left and right child nodes.
Build Cartesian Tree:
The Cartesian tree is constructed in a recursive manner by utilizing the smallest value acquired from the Segment Tree.
Throughout each iteration, the Segment Tree query operation is employed to identify the lowest element and its corresponding index within the present range. Subsequently, a Node is created based on these identified minimum value and index. This sequential procedure is repeated for the left and right subranges respectively.
Segment Tree Operations:
Build:
The Segment Tree is constructed to depict the smallest values within various subintervals of the given array.
The process of building is commonly carried out in a bottom-up fashion.
Query:
The query function is employed to determine the smallest element and its corresponding index within a specified range.
It effectively locates the smallest value within a defined interval in logarithmic time.
In-Order Traversal:
After constructing the Cartesian tree, a traversal in the order of in-order is executed to display the sorted sequence.
Program:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
int value;
int index;
Node* left;
Node* right;
Node(int val, int idx) : value(val), index(idx), left(nullptr), right(nullptr) {}
};
Node* buildCartesianTree(int arr[], int start, int end, vector<Node*>& nodes) {
if (start > end) return nullptr;
int minIndex = min_element(arr + start, arr + end + 1) - arr;
Node* root = new Node(arr[minIndex], minIndex);
root->left = buildCartesianTree(arr, start, minIndex - 1, nodes);
root->right = buildCartesianTree(arr, minIndex + 1, end, nodes);
nodes[minIndex] = root;
return root;
}
void inOrderTraversal(Node* root) {
if (root) {
inOrderTraversal(root->left);
cout << root->value << " ";
inOrderTraversal(root->right);
}
}
void cartesianTreeSort(int arr[], int n) {
vector<Node*> nodes(n, nullptr);
Node* root = buildCartesianTree(arr, 0, n - 1, nodes);
cout << "Sorted Sequence: ";
inOrderTraversal(root);
cout << endl;
}
int main() {
int arr[] = {5, 10, 40, 30, 28};
int n = sizeof(arr) / sizeof(arr[0]);
cartesianTreeSort(arr, n);
return 0;
}
Output:
Sorted Sequence: 5 10 40 30 28
Explanation:
Node Structure (Node):
The Node structure symbolizes a node within the Cartesian tree.
It contains three important attributes:
value: Represents the minimum value in the range.
index: Holds the index of the minimum value.
Pointers to the left and right descendants of the node.
Build Cartesian Tree (buildCartesianTree):
This function implements the construction of the Cartesian tree through recursion. The primary task involves identifying the minimum value and its corresponding index within the specified range by executing a query on a Segment Tree.
For every interval, a node is generated containing the smallest value and its corresponding index, followed by invoking the function recursively on both the left and right subrange segments.
This guarantees that the Cartesian tree is built by choosing the smallest element within each interval.
Build Segment Tree (buildSegmentTree):
This function is responsible for setting up and constructing the Segment Tree data structure.
It establishes the required data structures and calls the buildCartesianTree function to generate the Cartesian tree utilizing the Segment Tree.
The inOrderTraversal function executes an in-order scan of the Cartesian tree, displaying elements in a sorted manner as the traversal produces a sorted sequence.
The function cartesianTreeSort serves as the main function for implementing the Cartesian Tree Sort algorithm with the assistance of a Segment Tree. It triggers the essential procedures to set up and construct the Segment Tree, create the Cartesian tree, and execute the sorting process through an in-order traversal. The end result is a sequence of elements that has been sorted.
Output:
The output of the program is the sorted sequence of elements obtained through Cartesian Tree Sort using a Segment Tree.
- Cartesian Tree Sort using a Segment Tree efficiently combines the principles of Cartesian trees and Segment trees.
- It leverages the Segment Tree to find the minimum value in each subrange, constructing a Cartesian tree that inherently represents the sorted order of the input sequence.
- The ultimate sorted sequence is achieved by executing an in-order traversal of the Cartesian tree.
Complexity Analysis:
Time Complexity:
Build Cartesian Tree (buildCartesianTree):
Constructing the Cartesian tree during the build process entails selecting the smallest element within each specified range.
For every individual node within the Cartesian tree, a query is executed on the Segment Tree to determine the minimum value within a specific subrange.
Given that the Cartesian tree consists of O(N) nodes, the time complexity for constructing this tree is O(N log N).
Build Segment Tree (buildSegmentTree):
The creation process of the Segment Tree includes setting up and building the tree structure.
Thus, the total time complexity for constructing the Segment Tree amounts to O(N).
In-Order Traversal (inOrderTraversal):
Traversing the Cartesian tree in-order is an operation that runs in linear time, as each individual node is accessed exactly once during the process.
The time complexity associated with performing an in-order traversal is O(N), where N refers to the total number of nodes present in the Cartesian tree.
Cartesian Tree Sort (cartesianTreeSort):
The primary factor influencing time complexity is the creation of the Cartesian tree, which operates at O(N log N).
Space Complexity:
Node Structure (Node):
Each individual node within the Cartesian tree consumes a fixed amount of memory, as it solely retains a small set of attributes (value, index, left, right).
The space complexity for each node is O(1).
Build Cartesian Tree (buildCartesianTree):
The space efficiency is dictated by the quantity of nodes present in the Cartesian tree.
Given the O(N) number of nodes present in the Cartesian tree, the space complexity remains at O(N).
Build Segment Tree (buildSegmentTree):
The space efficiency of the Segment Tree amounts to O(4N) as it is usually constructed with an array, requiring 4N nodes for N elements.
Every node holds details regarding a specific range within the provided array.
In-Order Traversal (inOrderTraversal):
The amount of space needed for performing an in-order traversal is very small, usually O(1), since it doesn't rely on extra data structures that increase as the input size grows.
Cartesian Tree Sort (cartesianTreeSort):
The primary factor influencing space complexity is the Cartesian tree, which has a space complexity of O(N).
Conclusion:
Cartesian Tree Sorting presents a distinctive method that makes use of the Cartesian tree data structure. The beauty of this algorithm is in how it seamlessly combines tree building with the sorting procedure. This fusion leads to a smooth and logical way of sorting arrays that consist of unique numbers. Delving into the concepts of Cartesian trees, their formation, and the subsequent in-order traversal provides a deeper understanding of the theoretical basis and real-world implementation of Cartesian Tree Sorting.
