  The decision tree is one of the most fundamental programming abstractions. A
commonly used type of decision tree is the alphabetic binary tree, which uses
(without loss of generality) ``less than'' versus ''greater than or equal to''
tests in order to determine one of $n$ outcome events. The process of finding
an optimal alphabetic binary tree for a known probability distribution on
outcome events usually has the underlying assumption that the cost (time) per
decision is uniform and thus independent of the outcome of the decision. This
assumption, however, is incorrect in the case of software to be optimized for a
given microprocessor, e.g., in compiling switch statements or in fine-tuning
program bottlenecks. The operation of the microprocessor generally means that
the cost for the more likely decision outcome can or will be less -- often far
less -- than the less likely decision outcome. Here we formulate a variety of
$O(n^3)$-time $O(n^2)$-space dynamic programming algorithms to solve such
optimal binary decision tree problems, optimizing for the behavior of
processors with predictive branch capabilities, both static and dynamic. In the
static case, we use existing results to arrive at entropy-based performance
bounds. Solutions to this formulation are often faster in practice than
``optimal'' decision trees as formulated in the literature, and, for small
problems, are easily worth the extra complexity in finding the better solution.
This can be applied in fast implementation of decoding Huffman codes.
