Figure Nr.03 Balanced and unbalanced trees
To get to behavior H, the first tree needs 8 decisions, whereas the second tree only needs 3. In fact, if all behaviors were equally likely, then the first tree would need an average of nearly 4 ⅟2 decisions, whereas the second tree would always only need 3.
At its worst, with a severely unbalanced tree, the decision tree algorithm goes from being O(log2 n) to O(n). Clearly, we’d like to make sure we stay as balanced as possible, with the same number of leaves resulting from each decision.
Although a balanced tree is theoretically optimal, in practice the fastest tree structure is slightly more complex. In reality, the different results of a decision are not equally likely. Consider the example trees in Figure Nr.03 again. If we were likely to end up in behavior A the majority of the time, then the first tree would be more efficient; it gets to A in one step. The second tree takes 3 decisions to arrive at A.
Not all decisions are equal. A decision that is very time consuming to run (such as one that searches for the distance to the nearest enemy) should only be taken if absolutely necessary.Having this further down the tree, even at the expense of having an unbalanced tree, is a good idea.