Split the half-open array segment at its midpoint, using one entry for the root:The precondition is . Set . For the child sizes are and , differing by at most one. The same construction in both subtrees proves subtree-size balance at every node. Structural induction also gives the inorder traversal , followed by , followed by , hence precisely ; no sortedness assumption is needed.
PROCEDURE MakeTree(VAR u: ARRAY OF INTEGER;
a, b: INTEGER): Tree;
VAR m: INTEGER; t: Tree;
BEGIN
IF a = b THEN RETURN NIL END;
m := a + (b-a) DIV 2;
NEW(t);
t.label := u[m];
t.left := MakeTree(u, a, m);
t.right := MakeTree(u, m+1, b);
RETURN t
END MakeTree;Exactly records are allocated. Each nonempty recursive call makes two child calls, so there are calls including empty segments. Under constant-cost allocation and reference parameter passing,For positive this is proportional to ; the empty case takes constant time. The call stack has depth.
Articles by others on the same topic
There are currently no matching articles.