Notes #11 --- Inductive Definitions and Trees

Inductive definitions, recursive algorithms, and inductive proofs are central to Computer Science, and are closely connected.

Inductive definitions of a set:

The general form of an inductive definition of a set S is:

Base cases:

b_i is in S

There may be any number of these.

Formation rules:

If a_1, a_2, . . . , a_k_j are all in S, then so is f (a_1,a_2, . . . ,a_k_j)

There may be any number of these.
The number is not necessarily related to the number of base cases.

Minimality:

Nothing else is in S.

Examples of Inductive Definitions

Inductive definitions of a property:

We can define a property of the elements of a set defined inductively by defining it for the base cases, and showing how to combine the values for the constructs of the formation rules:

Examples of inductive property definitions

Recursive algorithms:

A typical inductive definition of a property naturally gives rise to a recursive algorithm, of the form:

Rec ( X ) {

if ( X in base_case_1 ) then return (base_result_1);

else if ( X in base_case_2 ) then return (base_result_2);

. . .

else if ( X == f1 (Y1, . . . , Yk_1) ) then {

z1 = Rec (Y1); z2 = Rec (Y2); . . . ; zk = Rec (Yk);

return combine_rule_1 (z1, z2, . . . , zk); }

else if ( X == f2 (Y1, . . . , Yk_2) ) then

. . .

else /* no base case or formation rule applies */

error ( error_msg);

}

Example of Recursive Algorithm

Structural induction:

Similarly, an inductive proof follows the same structure: prove the formula for each base case, and show that if the formula holds for each argument for a formation rule, that it will hold for the result. Then (by the minimality rul e) it will hold for all elements of the set.

Examples of Structural Induction

Problems

Give an inductive definition for a full ternary (3-ary) tree. Use this to define the height of a ternary tree.

Extract the proper inductive definition of a (not necessarily full) binary tree from the recursive algorithm for height above.

Formulate a result about the number of leaves and internal nodes in a full ternary tree. Use your definition in part 1 to give a strucutal inductive proof for your claim.

Connection to grammars

There is a strong connection between inductive definitions and context-free grammars (CFGs). Intuitively, we can think of the productions of a CFG as its rules: productions whose right-hand sides contain another grammar symbol are t he formation rules, while productions whose right-hand sides consist entirely of language symbols (or are empty) are the base cases.

Trees and tree balance

The properties of binary trees, and of balanced binary trees, are often derivable by inductive definition.

We would like use binary search trees for external storage. Each pointer potentially represents an access to a new memory location. Thus, the number of accesses to external memory is essentially the height/depth of the tree. If even a few paths can be very long, then this cost can be unacceptable. The cost can be reduced with blocking by a constant factor, by blocking not in level order, but making a block out of subtrees rooted at every k-th level (multi-level or hierarchical BSTs).

Example of Binary and Blocked Binary Search Trees

File systems will often use multi-level trees as a paging scheme for tree-structured files.

For ease of discussion, and because a search will have to end with success or with following a nil pointer, we will add failure nodes at every nil pointer, thus regarding the tree as a full binary tree.

Depth properties of binary trees

AVL trees

AVL trees are one particular approach to guaranteeing good maximum depth in a binary search tree.