Tech Report CS-90-35

Dynamic Expression Trees

Robert F. Cohen and Roberto Tamassia

December 1990

Abstract:

We present a technique for dynamically maintaining a collection of arithmetic expressions represented by binary trees (whose leaves are variables and whose internal nodes are operators). A query operation asks for the value of an expression (associated with the root of a tree). Update operations include chaining the value of a variable and combining or decomposing expressions by linking or cutting the corresponding trees. Our dynamic data structure uses linear space and supports queries and updates in logarithmic time. An important application is the dynamic maintenance of maximum flow and shortest path in series-parallel digraphs under a sequence of vertex and edge insertions, series and parallel compositions, and their respective inverses. Queries include reporting the maximum flow or shortest {\em st}-path in a series-parallel subgraph.

(complete text in pdf or gzipped postscript)