What is the main difference between binary decision tree and binary decision diagram(BDD)? From what I can tell I only understand that a binary decision diagram is a more compact representation because it eliminates nodes that have both edges pointing to the same node, eliminates nodes that have removes and removes terminal $2^n$ terminal nodes to just $2$, and but perhaps there is fundamental difference other then this?
$\begingroup$
$\endgroup$
asked Oct 12, 2017 at 23:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
One is a tree; one is not. A BDD is a directed acyclic graph (dag), but not necessarily a tree. This allows a BDD to be more compact, in some cases.
That's the only essential difference. Of course, they have different properties (that follow from this difference in their definition).
