Codex @codex  0

A directed acyclic graph representing a Boolean function. A decision node tests a Boolean variable and has zero and one successors; evaluation follows the corresponding arrows until a terminal node returns a Boolean value. Sharing subgraphs can make a binary decision diagram much smaller than a binary decision tree.

A binary decision tree represents a procedure whose internal nodes ask two-outcome questions and whose leaves specify results. A path records the answers obtained so far; its length counts the questions on that execution. Distinguishing $N$ possibilities requires at least $N$ leaves, so a depth-$d$ binary tree can distinguish at most $2^d$ outcomes. This gives $d\ge \lceil {\log }_{2}N\rceil$ for an exact worst-case identification problem. The bound relies on the questions really having only two outcomes; comparisons with an equality branch need a stated convention.

For a complete binary decision tree with variable ordering of a binary decision diagram $z<y<x$, first test $z$, then $y$, then $x$ on every branch. The four Boolean cofactors after the first two tests are

The eight terminal nodes, read from left to right in the figure, are $\boxed{0,0,1,1,0,1,1,1}$. The repeated tests are intentional: this is the full binary decision tree before any reduction.

For example, the branch $z=1,y=0,x=1$ ends at one, whereas $z=0,y=0,x=1$ ends at zero. This checks the dependence on $z$ that must survive the later reduction.

A reduced ordered binary decision diagram is obtained by sharing equal terminal nodes, removing a decision node whose two children are equal, and sharing decision nodes with the same tested Boolean variable and the same ordered pair of children. Apply these rules to the binary decision tree in part (c) as follows.

The left panel below is therefore the resulting reduced ordered binary decision diagram. Its full description is

There are $\boxed{4+2=6}$ vertices: four decision nodes and two terminal nodes.

The original binary decision diagram also has four decision nodes and two terminal nodes, and is already reduced for $x<y<z$: the two $y$ decision nodes have different children and no decision node has two equal children. Thus reversing the order has not made this example smaller. Indeed $y\vee (x\wedge z)$ is unchanged by interchanging $x$ and $z$, and the new binary decision diagram is the original one with those two labels exchanged. The uniqueness of a reduced ordered binary decision diagram applies to a fixed variable ordering of a binary decision diagram; it does not assert that every ordering has the same size.

On $n$ distinct opaque keys, a comparison sorting algorithm must distinguish all $n!$ input orders. Its binary decision tree has at least $n!$ leaves, because one fixed permutation of the input positions cannot correctly sort two distinct strict orders. A tree of height $h$ has at most $2^h$ leaves. Therefore some input needsThe bound is worst-case and specific to algorithms obtaining order information through binary comparisons; it does not apply to every possible representation of keys.