Today I read about cartesian tree(treap) from e-maxx's page, since it is in russian I decided to translate some parts.
Also here are some related links:
http://infoarena.ro/treapuri (a different implementation)
I would appreciate if someone could post problems that can be solved it, there are some at infoarena.
Cartesian tree (Treap):
A data structure that stores a pair (X,Y) in the form of a binary search tree with respect to X and a heap with respect to Y.
Assuming that al X and Y are different, for an element (X0,Y0):
- All the elements in the left subtree are such that X < X0
- All the elements in the right substree are such that X > X0
- All the elements in the left or right subtrees are such that Y < Y0
X's are the keys.
Y's are the priorites (choosed at random)
If we didn't use priorities, then it would be a normal binary search tree, and the given set of X's could meet a lot of trees, some of which are degenerate
(for example in form of a chain), so operations would be done really slowly.
Priorities can uniquely identidy a tree that will be built. On average using priorites provides us the asymptotics O(log n).
- Insert(X,Y), Avg Complexity O(log N) : Inserts a new item, we could also not pass Y as a parameter, instead we can choose it a random inside
- Search(X), Avg Complexity O(log N) : Searches for the element with the specified key value X
- Erase(X), Avg Complexity O(log N) : Searches for the element X and erases it
- Build(X1,...,XN), Avg Complexity O(N log N) : Builds a tree of a list of values
- Union(T1,T2), Avg Complexity O(M log N/M) : Combines two trees, assuming that the elements are different
- Intersect(T1,T2), Avg Complexity O(M log N/M) : Finds the common elements of two trees
Description of the implementation:
- Each element (X,Y) contains pointers to the left (L) an the right (R) sons.
- To implement other operations we require two commplementary operations: Split and Merge
- Split(T,X) : divides the tree T into two trees L and R so that L contains all elements that are smaller than X, and R contains all elements that area are equal or larger than X.
This operation is performed in O(log N)
- Merge(T1,T2) : combines two subtrees T1 and T2, and returns a new tree. This operation is also implemented in O(log N). It works on the assumption that T1 and T2 have the
appropiate order (all X values in the first are less than values at the second)
Implicit Cartesian Tree:
It is a simple modification of the usual Cartesian tree. It can be thought of as array on which you can implement the following procedures (complexity O(log N) online):
- Insert an element in the array at any position
- Removal of any element
- Sum, minimum, maximum of an arbitrary interval
- The addition, paint on the interval
- Reverse of an interval
The key idea is to use the indices of elements in the array as the key. However, these values are explicitely stored key.
The key of a node is the number number of nodes in its left subtree, and also, in the left subtree of its ancestors.