Split the index range at its middle:For , the child sizes are and , differing by at most one. Induction gives the same property at every descendant, so the result is nearly balanced. Its inorder traversal is the initial subrange, then , then the final subrange, reproducing exactly with every occurrence retained.
def MakeTree(u: Array[Int], a: Int, b: Int): Tree = {
require(0 <= a && a <= b && b <= u.length)
if (a == b) null
else {
val middle = a + (b - a) / 2
new Tree(u(middle),
MakeTree(u, a, middle),
MakeTree(u, middle + 1, b))
}
}There is one nonempty recursive call per constructed node and one constant-time base call per empty child position. Therefore construction takes time for , or including the empty case, and allocates exactly nodes. The balanced recursion has logarithmic stack depth. The input array need not be sorted: the required property concerns subtree sizes and inorder order, not a search-tree ordering.
Articles by others on the same topic
There are currently no matching articles.