Module grove::trees::treap [−][src]
Expand description
Implementation of treaps
It is a balanced tree algorithm that supports reversals, splitting and concatenation.
Its operations take O(log n) expected time, probabilistically.
Each operation may take up to linear time, but the probability of any operation
taking more than O(log n) time is extremely low.
The tree rebalances by assigning random priorities to nodes, and ensuring They are in the correct structure mandated byy thos priorities.
The tree’s structure is completely independent of the actions that were performed on it.
Structs
Functions
Computes the union of two splay trees, ordered by keys.
We order the resulting tree based on the D::Value : Keyed instance, assuming that
the values in the existing trees are also in the correct order.
This is different from concatenate, because concatenate puts first all elements of the first tree,
and then all of the elements of the second tree.