TAOCP 2.3.3 Exercise 3

Section 2.3.3: Other Representations of Trees

Exercise 3. [24] Modify Algorithm 2.3.2D so that it follows the ideas of Algorithm F, placing the derivatives it computes as intermediate results on a stack, instead of recording their locations in an anomalous fashion as is done in step D3. (See exercise 2.3.2-21.) The stack may be maintained by using the RLINK field in the root of each derivative.

Verified: yes
Solve time: 1m26s

Solution

Algorithm 2.3.2D traverses an expression tree in postorder and computes, for each node, a derivative tree. Step D3 stores the locations of previously computed derivatives in an anomalous manner. Exercise 2.3.2-21 shows that this information can instead be maintained on a stack. Algorithm F suggests the proper organization: when a node is reached in postorder, the derivatives of all of its children are already available on the top of a stack.

Assume that the expression tree is represented in postorder with degrees, as in representation (9). Let P point to the current node. The stack will contain roots of derivative trees. The RLINK field of the root of each derivative tree is used to chain stack entries together; thus the stack itself requires no additional storage.

The invariant is the same as in Algorithm F: when step G2 below is entered for a node of degree $d$, the top $d$ items of the stack are the derivatives of the subexpressions represented by its children, appearing in reverse left-to-right order.

Algorithm G (Differentiation with a stack)

G1. [Initialize.] Set the stack empty, and let P point to the first node of the expression tree in postorder.

G2. [Determine degree.] Set d ← DEGREE(P).

G3. [Form derivative.] Construct the derivative corresponding to NODE(P).

If d=0, NODE(P) is an operand. Construct the derivative prescribed by step D2 of Algorithm 2.3.2D.

If d=1, let U' be the derivative tree at the top of the stack. Construct the derivative prescribed by the unary-operator case of step D4, using U'.

If d=2, let V' and U' be the top two derivative trees on the stack, where V' is on top and U' is immediately below it. Construct the derivative prescribed by the binary-operator case of step D4, using U' and V'.

Let W' denote the root of the newly constructed derivative tree.

G4. [Update stack.] Remove the top d items from the stack. Set RLINK(W') to the previous top of the stack (or to Λ if the stack is empty), and make W' the new top item.

G5. [Advance.] If P is the last node in postorder, terminate. The stack then contains exactly one item, namely the derivative of the entire expression. Otherwise advance P to its successor in postorder and return to step G2.

To verify correctness, proceed by induction on the number of nodes processed. For a terminal node, step G3 produces exactly the derivative required by step D2; after step G4 the stack contains the derivative of that subtree. Assume the invariant holds before processing a node whose children are represented by subtrees $T_1,\ldots,T_d$. By postorder traversal, the derivatives of $T_1,\ldots,T_d$ have already been computed and occupy the top $d$ stack positions in reverse order. Step G3 therefore has available precisely the same derivative information that Algorithm 2.3.2D obtains through its bookkeeping in step D3. The derivative tree produced is therefore identical to that produced by step D4. Step G4 removes the children's derivatives and replaces them by the derivative of the whole subtree rooted at NODE(P), preserving the invariant. After the final node is processed, the unique stack entry is the derivative of the complete expression tree.

Thus Algorithm 2.3.2D can be rewritten in the style of Algorithm F, with all intermediate derivatives maintained on a stack whose links are stored in the RLINK fields of the derivative roots.

This completes the proof.

∎