Use pattern matching on the two data constructors, concatenating the left subtree's inorder traversal, the root label, and the right subtree's inorder traversal:
data Tree = Leaf | Fork Tree Int Tree

inorder :: Tree -> [Int]
inorder Leaf = []
inorder (Fork l x r) = inorder l ++ [x] ++ inorder r
Here Leaf represents the empty binary tree, rather than a labelled leaf. The printed declaration uses type; an executable Haskell algebraic data type requires data, as above. By structural induction, the two equations return precisely the prescribed inorder traversal:
(1)
An Oberon pointer refers to a record containing an integer label and two subtree references:
TYPE
  Tree = POINTER TO Node;
  Node = RECORD
    left, right: Tree;
    label: INTEGER
  END;
Use NIL for the empty binary tree, including either absent child. The representation invariant requires a finite, acyclic binary tree with disjoint left and right subtrees. In particular, shared nodes would represent a different structure and invalidate destructive traversal arguments.
(1)
Give the visiting procedure a procedure type:
TYPE Visit = PROCEDURE(x: INTEGER);

PROCEDURE Inorder(t: Tree; p: Visit);
BEGIN
  IF t # NIL THEN
    Inorder(t.left, p);
    p(t.label);
    Inorder(t.right, p)
  END
END Inorder;
Structural induction establishes algorithm correctness: an empty binary tree makes no calls; otherwise the first recursive call visits precisely the left subtree, then the root is visited once, then the second recursive call visits precisely the right subtree. Assume p does not modify the binary tree. With constant-cost p, there is constant work per node and empty child occurrence:
(1)
where is the height of a binary tree and storage is the call stack.
Split the half-open array segment at its midpoint, using one entry for the root:
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;
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.
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,
(1)
For positive this is proportional to ; the empty case takes constant time. The call stack has depth.
The VAR marker passes a reference parameter, so every recursive call accesses the same array without copying it. Read-only access does not make copying necessary. Under the examination's value parameter convention, omitting VAR copies the whole actual array, not merely the selected segment .
If its length is , the calls therefore cost for . For a whole-input construction, :
(1)
Copying only the shrinking segments would instead lead to , but that is a different parameter passing model from passing the same actual array on every call.
Use destructive inorder traversal by right rotations. A right tree rotation preserves inorder traversal but moves the first unvisited node closer to the root:
PROCEDURE InorderDestructive(t: Tree; p: Visit);
VAR q: Tree;
BEGIN
  WHILE t # NIL DO
    WHILE t.left # NIL DO
      q := t.left;
      t.left := q.right;
      q.right := t;
      t := q
    END;
    p(t.label);
    t := t.right
  END
END InorderDestructive;
The outer loop invariant states that the labels already passed to p, followed by the inorder traversal of t, equal the original inorder traversal. The remaining nodes form a binary tree disjoint from the nodes already visited. The inner loop invariant preserves the remaining inorder traversal: if the old root is , its left child is , and the three unchanged subtrees are , then both shapes have order .
Figure 1.
A right tree rotation preserves inorder traversal and exposes the next node
. Details.
At inner-loop exit, t.left = NIL, so the root is the first remaining node. Visiting it and replacing t by t.right preserves the outer loop invariant. The procedure changes child pointers and makes the old root reference unusable as the original binary tree. Assume p neither changes the binary tree nor depends on its old shape.
(1)
Let be the number of nodes and let the left-size potential of a binary tree be
(1)
Equivalently counts nodes outside the right spine, so ; for a nonempty binary tree of nodes, .
For the right tree rotation in part (f), write the old shape as . Before and after,
(2)
Thus each inner iteration decreases by exactly one, making an inner loop variant. Removing a root with empty left subtree leaves unchanged and decreases by one. Therefore decreases on every rotation or visit, while decreases on every completed outer iteration. These are bounds used for proof; the program never computes them.
There are exactly visits and exactly rotations, since the final empty binary tree has potential zero. Counting constant-cost p,
(3)
The nested loops therefore have linear total running time, despite one outer iteration potentially making many rotations.

Ancestors (10)

  1. Imperative programming (resit)
  2. 2015
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version