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.
- Merge the three zero terminal nodes into one zero terminal node, and merge the five one terminal nodes into one one terminal node.
- At the decision node has children . Remove it and redirect its incoming arrow to zero.
- At and the two decision nodes each have children . Remove both and redirect their incoming arrows to one.
- The remaining decision node, at , has children , so retain it.
- The decision node under now has children , while the one under has children . These are different, so neither can be merged or removed. The top decision node also has different children.
The left panel below is therefore the resulting reduced ordered binary decision diagram. Its full description is
Reduced ordered decision diagrams: reversing the given order preserves its size, while testing y first saves one decision node
. Details. 
The original binary decision diagram also has four decision nodes and two terminal nodes, and is already reduced for : the two decision nodes have different children and no decision node has two equal children. Thus reversing the order has not made this example smaller. Indeed is unchanged by interchanging and , 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.
Articles by others on the same topic
There are currently no matching articles.