Entscheidungsbäume mit Sharing

ausgehend von eben definiertem Baum: konstruiere DAG (gerichteten kreisfreien Graphen):

• Blätter zusammenfassen: nur zwei Blätter 0,1
• alle Knoten mit gleichem (v, l, r) zusammenfassen
• alle Knoten mit (v, l, r) und l = v durch l ersetzen

reduziertes geordnetes binäres Entscheidungsdiagramm (ROBDD)

Randal E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, C-35(8):677-691, 1986