Solution: Random Binary Search Trees

Task

Here is the solution that implements an algorithm that constructs a Treap from a sorted array, a, of n elements. This method runs in $O(n)$ worst-case time and should construct a Treap that is indistinguishable from one in which the elements of a were added one at a time using the add(x) method.

Solution

The code widget shows the implementation of the addall() method and addallrecursive() method that constructs a Treap from a sorted array a of n elements.