Decision tree

A decision tree is a tree representing the logical structure of certain algorithms on various inputs. The nodes of the tree represent branch points of the computation — places where more than one outcome are possible based on some predicate of the input — and the leaves represent possible outcomes. Given a particular input, one starts at the root of the tree, performs the test at that node, and descends accordingly into one of the subtrees of the root. Continuing in this way, one reaches a leaf node which represents the outcome of the computation.

Given a function [math]f:\{-1,1\}^n \to \{-1,1\}[/math], a simple decision tree for the function is a binary tree whose internal nodes have labels from [math]{1, 2, . . . , n}[/math] and whose leaves have labels from [math]{-1, 1}[/math]. If a node has label i, then the test performed at that node is to examine the ith bit of the input. If the result is -1, one descends into the left subtree, whereas if the result is 1, one descends into the right subtree. The label of the leaf so reached is the value of the function on the input. While it is clear that any such function f has a simple decision tree, we will be interested in simple decision trees for f which have minimal depth decision tree complexity D(f). D(f) is called the decision tree complexity of f.