CartesianTree

CartesianTree, also known as a Cartesian tree or treap, is a binary tree data structure that combines properties of both binary search trees and heaps. It was introduced by Jean-Loup Baer in 1975. The structure is defined such that for each node, the value of the node is greater than the values of its left child and less than the values of its right child, similar to a binary search tree. Additionally, the tree satisfies the heap property, where the value of each node is less than or equal to the values of its parent nodes, similar to a min-heap.

The Cartesian tree is constructed from a sequence of numbers by recursively selecting the minimum element and making it the root of the tree. The left subtree is constructed from the elements to the left of the minimum element, and the right subtree is constructed from the elements to the right. This construction ensures that the tree maintains both the binary search tree and heap properties.

Cartesian trees have applications in various fields, including computational geometry, where they are used to solve problems related to convex hulls and range searching. They are also used in data compression algorithms, such as the Burrows-Wheeler transform, and in the implementation of priority queues.

One of the key advantages of Cartesian trees is their simplicity and efficiency. The construction of a Cartesian tree from a sequence of n elements can be done in O(n) time, making it a practical choice for many applications. Additionally, the tree supports efficient insertion, deletion, and search operations, making it a versatile data structure for a wide range of problems.