Decision Trees and Data Structures
Eyal Kushilevitz, Noam Nisan · Cambridge University Press eBooks · 1996
Decision Trees One of the simplest models of computation is the decision tree model. In this model we are concerned with computing a function f : {0, 1} m → {0, 1} by using queries. Each query is given by specifying a function q on {0, l} m taken from some fixed family Q of allowed queries (the queries need not be Boolean). The answer given for the query is simply the value of q ( x 1 , …, x m ). The algorithm is completely adaptive, that is the i -th query asked may depend in an arbitrary manner on the answers received for the first i − 1 queries. The only wayto gain information about the input x is through these queries. The algorithm can therefore be described as a labeled tree , whose nodes are labeled by queries q ∈ Q , the outgoing edges of each node are labeled by the possible values of q ( x 1 , …, x m ), and the leaves are labeled by output values. Each sequence of answers describes a path in the tree to a node that is either the next query or the value of the output. In Figure 9.1 a decision tree is shown that computes (on inputs x 1 , …, x 4 ) whether at least three of the input bits are 1s. It uses a family of queries Q consisting of all disjunctions of input variables and conjunctions of input variables. The cost measure we are interested in is the number of queries performed on the worst case input; that is, the depth of the tree. Definition 9.1: The decision tree complexity of a function f using the family of queries Q, denoted T Q ( f ), is the minimum cost decision tree algorithm over Q for f .