Cartesian Trees in C++

The Cartesian tree, also known as a treap, is a data structure that combines the properties of a binary search tree and a heap. It is a self-balancing tree that can be used to efficiently access, search, insert and delete data. In this article, we will discuss the structure of a Cartesian tree, its time complexity for the four operations mentioned above, its space complexity, and a few coding exercises for readers to test their understanding of the concepts.

What is a Cartesian Tree?

A Cartesian tree is a binary tree that satisfies two properties: a heap property and a search tree property. The heap property requires that each node in the tree must have a key, or value, and that the parent node’s key must be greater than or equal to the key of its children. The search tree property requires that the left subtree of any node must contain keys that are less than or equal to the key of the node, and the right subtree must contain keys that are greater than or equal to the node’s key.

The Cartesian tree structure is advantageous because it provides the same level of performance as a heap, while also providing the same searching capabilities as a binary search tree. This makes it an ideal data structure for applications that need to perform both operations.

Time Complexity

The time complexity for accessing, searching, inserting and deleting data in a Cartesian tree can be broken down into average and worst-case scenarios.

Accessing a node in a Cartesian tree has an average time complexity of O(log n), where n is the number of nodes in the tree. In the worst case, the time complexity is O(n).

Searching for a node in a Cartesian tree has an average time complexity of O(log n) and a worst-case time complexity of O(n).

Inserting a node into a Cartesian tree has an average time complexity of O(log n) and a worst-case time complexity of O(n).

Deleting a node from a Cartesian tree has an average time complexity of O(log n) and a worst-case time complexity of O(n).

Space Complexity

The space complexity of a Cartesian tree is O(n), where n is the number of nodes in the tree. This means that the tree will use up a constant amount of space in memory, regardless of the number of nodes.

C++ Code

Below is an example of a C++ program that implements a Cartesian tree. The program includes a Node class, which is used to represent a node in the tree. It also includes functions for searching, inserting, and deleting nodes from the tree.

#include <iostream>
 
class Node {
public:
    int data;
    Node* left;
    Node* right;
 
    Node(int data);
};
 
Node::Node(int data) {
    this->data = data;
    left = NULL;
    right = NULL;
}
 
class CartesianTree {
private:
    Node* root;
 
public:
    CartesianTree();
    Node* search(int data);
    Node* insert(int data);
    void deleteNode(int data);
};
 
CartesianTree::CartesianTree() {
    root = NULL;
}
 
Node* CartesianTree::search(int data) {
    Node* current = root;
 
    while (current != NULL) {
        if (current->data == data) {
            return current;
        } else if (current->data > data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
 
    return NULL;
}
 
Node* CartesianTree::insert(int data) {
    Node* newNode = new Node(data);
 
    if (root == NULL) {
        root = newNode;
        return root;
    }
 
    Node* current = root;
    Node* parent = NULL;
 
    while (current != NULL) {
        parent = current;
        if (current->data > data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
 
    if (parent->data > data) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }
 
    return newNode;
}
 
void CartesianTree::deleteNode(int data) {
    Node* current = root;
    Node* parent = NULL;
    Node* nodeToDelete = NULL;
 
    while (current != NULL) {
        if (current->data == data) {
            nodeToDelete = current;
            break;
        } else if (current->data > data) {
            parent = current;
            current = current->left;
        } else {
            parent = current;
            current = current->right;
        }
    }
 
    if (nodeToDelete == NULL) {
        return;
    }
 
    if (nodeToDelete->left == NULL && nodeToDelete->right == NULL) {
        if (nodeToDelete == root) {
            root = NULL;
        } else {
            if (parent->left == nodeToDelete) {
                parent->left = NULL;
            } else {
                parent->right = NULL;
            }
        }
    } else if (nodeToDelete->left != NULL && nodeToDelete->right != NULL) {
        Node* maxNode = nodeToDelete->left;
        Node* maxNodeParent = nodeToDelete;
 
        while (maxNode->right != NULL) {
            maxNodeParent = maxNode;
            maxNode = maxNode->right;
        }
 
        nodeToDelete->data = maxNode->data;
 
        if (maxNodeParent->left == maxNode) {
            maxNodeParent->left = maxNode->left;
        } else {
            maxNodeParent->right = maxNode->left;
        }
    } else {
        Node* childNode;
        if (nodeToDelete->left != NULL) {
            childNode = nodeToDelete->left;
        } else {
            childNode = nodeToDelete->right;
        }
 
        if (nodeToDelete == root) {
            root = childNode;
        } else {
            if (parent->left == nodeToDelete) {
                parent->left = childNode;
            } else {
                parent->right = childNode;
            }
        }
    }
 
    delete nodeToDelete;
}
 
int main() {
    CartesianTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(15);
    tree.insert(25);
    tree.deleteNode(20);
    Node* node = tree.search(15);
 
    std::cout << node->data << std::endl;
    return 0;
}

Conclusion

The Cartesian tree is a self-balancing binary tree that combines the properties of a heap and a binary search tree. It provides efficient access, search, insertion and deletion operations, with an average time complexity of O(log n) and a worst-case time complexity of O(n). It also has a space complexity of O(n).

Exercises

#include <iostream>
 
class Node {
public:
    int data;
    Node* left;
    Node* right;
 
    Node(int data);
};
 
Node::Node(int data) {
    this->data = data;
    left = NULL;
    right = NULL;
}
 
class CartesianTree {
private:
    Node* root;
 
public:
    CartesianTree();
    void traversePreOrder(Node* node);
};
 
CartesianTree::CartesianTree() {
    root = NULL;
}
 
void CartesianTree::traversePreOrder(Node* node) {
    if (node == NULL) {
        return;
    }
 
    std::cout << node->data << std::endl;
    traversePreOrder(node->left);
    traversePreOrder(node->right);
}
 
int main() {
    CartesianTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(15);
    tree.insert(25);
    tree.deleteNode(20);
    Node* node = tree.search(15);
    tree.traversePreOrder(node);
    return 0;
}

#include <iostream>
 
class Node {
public:
    int data;
    Node* left;
    Node* right;
 
    Node(int data);
};
 
Node::Node(int data) {
    this->data = data;
    left = NULL;
    right = NULL;
}
 
class CartesianTree {
private:
    Node* root;
 
public:
    CartesianTree();
    int getHeight(Node* node);
};
 
CartesianTree::CartesianTree() {
    root = NULL;
}
 
int CartesianTree::getHeight(Node* node) {
    if (node == NULL) {
        return 0;
    }
 
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
 
    return std::max(leftHeight, rightHeight) + 1;
}
 
int main() {
    CartesianTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(15);
    tree.insert(25);
    tree.deleteNode(20);
    Node* node = tree.search(15);
    int height = tree.getHeight(node);
    std::cout << height << std::endl;
    return 0;
}

#include <iostream>
 
class Node {
public:
    int data;
    Node* left;
    Node* right;
 
    Node(int data);
};
 
Node::Node(int data) {
    this->data = data;
    left = NULL;
    right = NULL;
}
 
class CartesianTree {
private:
    Node* root;
 
public:
    CartesianTree();
    void deleteTree(Node* node);
};
 
CartesianTree::CartesianTree() {
    root = NULL;
}
 
void CartesianTree::deleteTree(Node* node) {
    if (node == NULL) {
        return;
    }
 
    deleteTree(node->left);
    deleteTree(node->right);
 
    delete node;
}
 
int main() {
    CartesianTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(15);
    tree.insert(25);
    tree.deleteNode(20);
    Node* node = tree.search(15);
    tree.deleteTree(node);
    return 0;
}

#include <iostream>
 
class Node {
public:
    int data;
    Node* left;
    Node* right;
 
    Node(int data);
};
 
Node::Node(int data) {
    this->data = data;
    left = NULL;
    right = NULL;
}
 
class CartesianTree {
private:
    Node* root;
 
public:
    CartesianTree();
    bool isValid(Node* node);
};
 
CartesianTree::CartesianTree() {
    root = NULL;
}
 
bool CartesianTree::isValid(Node* node) {
    if (node == NULL) {
        return true;
    }
 
    if (node->left != NULL && node->data < node->left->data) {
        return false;
    }
 
    if (node->right != NULL && node->data > node->right->data) {
        return false;
    }
 
    return isValid(node->left) && isValid(node->right);
}
 
int main() {
    CartesianTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(15);
    tree.insert(25);
    tree.deleteNode(20);
    Node* node = tree.search(15);
    bool isValid = tree.isValid(node);
    std::cout << isValid << std::endl;
    return 0;
}

#include <iostream>
 
class Node {
public:
    int data;
    Node* left;
    Node* right;
 
    Node(int data);
};
 
Node::Node(int data) {
    this->data = data;
    left = NULL;
    right = NULL;
}
 
class CartesianTree {
private:
    Node* root;
 
public:
    CartesianTree();
    int findMin(Node* node);
};
 
CartesianTree::CartesianTree() {
    root = NULL;
}
 
int CartesianTree::findMin(Node* node) {
    if (node == NULL) {
        return -1;
    }
 
    int minValue = node->data;
 
    int leftMin = findMin(node->left);
    int rightMin = findMin(node->right);
 
    if (leftMin != -1 && leftMin < minValue) {
        minValue = leftMin;
    }
 
    if (rightMin != -1 && rightMin < minValue) {
        minValue = rightMin;
    }
 
    return minValue;
}
 
int main() {
    CartesianTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(15);
    tree.insert(25);
    tree.deleteNode(20);
    Node* node = tree.search(15);
    int minValue = tree.findMin(node);
    std::cout << minValue << std::endl;
    return 0;
}