Cartesian tree

A Cartesian tree is a binary tree in the nodes of which are stored:

links to the right and left subtree;
reference to the parent node (optional);
the keys x and y , which are the binary search tree for the key x and the binary heap for the key y ; namely, for any node of the tree n :
- the keys x of the nodes of the right (left) subtree are larger (smaller) or equal to the key x of the node n ;
- the keys y of the nodes of the right and left children are greater than or equal to the key y of the node n .

A reference to the parent node is optional, it is desirable only for a linear tree-building algorithm.

A Cartesian tree is not self-balancing in the usual sense, and is used for the following reasons:

It is easier to implement, in comparison, for example, with real self-balancing trees like red-black .
It behaves "on average" if the keys y are distributed randomly.
Typical for a sorting tree, the operation "partition by key x into" less than x ₀ "and" not less than x ₀ "" works for O ( h ), where h is the height of the tree. On red-black trees will have to restore the balance and color of the nodes.

The disadvantages of the Cartesian tree:

Large storage overhead: two or three pointers and a random key y are stored with each element.
Access speed O ( n ) in the worst, albeit unlikely, case. Therefore, the Cartesian tree is unacceptable, for example, in the kernels of the OS .

Content

1 Terminology
2 The simplest algorithm for constructing a Cartesian tree
3 Structure uniqueness property
4 Linear tree building algorithm
5 notes
6 References
7 Literature

Terminology

In English literature, a Cartesian tree built for an array of given keys and random weights assigned to it during construction is called the treap wallet word , since it combines the properties of a sorting heap tree and a random binary tree ( tree ) with a logarithmic expectation of height. In Russian, the words ducha ^[1] ( tree + heap ), deramide ( tree + pyramid ), and smoke ( heap + tree ) were proposed similar to the word treap .

Simplest Cartesian Tree Algorithm

The simplest to understand algorithm for constructing a Cartesian tree from the data set of pairs (x, y) is as follows. We order all the pairs by the key x and number the resulting sequence of keys y:

y (1), y (2), y (3), ..., y (n).

Find the minimum key y. Let it be y (k). He will be the root of the tree. Key y (k) divides the sequence of keys y into two:

y (1), ..., y (k − 1); y (k + 1), ..., y (n).

In each of them we find the minimum y - these will be the children of the node y (k) - left and right. With the resulting 4 pieces (possibly less), we will do the same. The proposed algorithm for constructing a Cartesian tree is based on recursion: we find the minimum y in the sequence and assign it to the root. found y breaks the sequence into two parts, for each of the parts we start the algorithm for constructing the Cartesian tree.

Schematically, this can be written as follows:

  T (y (1), ..., y (n)) = root: y (k)   
                            left_tree: T (y (1), ..., y (k − 1))   
                            right_tree: T (y (k + 1), ..., y (n)))
                         where y (k) = min (y (1), ..., y (n))

Structure Uniqueness Property

From this algorithm it follows that the set of pairs (x, y) uniquely determines the structure of the Cartesian tree. For comparison, we note that the many keys that are stored in the binary search tree do not uniquely determine the structure of the tree. The same applies to the binary heap - what the structure of the binary heap will be (how the keys are distributed among the nodes) depends not only on the set of keys, but also on the sequence of their addition. There is no such ambiguity in the Cartesian tree.

Linear Tree Algorithm

Another tree-building algorithm is also based on recursion. Only now will we sequentially add y elements and rebuild the tree. The tree T (y (1), ..., y (k + 1)) will be constructed from the tree T (y (1), ..., y (k)) and the next element y (k + 1).

  T (y (1), ..., y (k + 1)) = F (T (y (1), ..., y (k)), y (k + 1))

At each step, we will remember the link to the last added node. He will be the most right. Indeed, we ordered the keys y by the key x attached to them. Since the Cartesian tree is a search tree, after projection onto a horizontal line, the keys x must increase from left to right. The rightmost node always has the maximum possible value of the key x.

A function F that maps the Cartesian tree T (y (1), ..., y (k)) of the previous step and the next y (k + 1) to the new tree T (y (1), ..., y (k + 1)) , as follows. The vertical for the node y (k + 1) is defined. We need to determine its horizontal. First, we check whether the new node y (k + 1) can be made the right child of the node y (k) - this should be done if y (k + 1)> y (k). Otherwise, we take a step along the slope from the node y (k) up and look at the value of y that is stored there. We climb up the slope until we find a node in which the value of y is less than y (k + 1), after which we make y (k + 1) his right child, and we make his previous right child the left child of the node y (k + one).

This algorithm depreciation (in total for all steps) works in a linear (by the number of added nodes) time. Indeed, as soon as we “crossed” a node, climbing up the slope, we will never meet it when adding the following nodes. Thus, the total number of steps up the slope cannot be greater than the total number of nodes.

Notes

↑ Donald Knut . The Art of Programming, Volume 3. Sorting and Search = The Art of Computer Programming, vol. 3. Sorting and Searching. - 2nd ed. - M .: "Williams" , 2007. - ISBN 0-201-89685-0 .

Links

Literature

Raimund Seidel, Cecilia R. Aragon (1996). "Randomized Search Trees". ALGORITHMICA : 540-545.

[1] Donald Knut . The Art of Programming, Volume 3. Sorting and Search = The Art of Computer Programming, vol. 3. Sorting and Searching. - 2nd ed. - M .: "Williams" , 2007. - ISBN 0-201-89685-0 .