Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
A tree’s root is at level 1, not level 0.
The proof that any tree satisfying the sort property is a functionally sorted collection should read, in part, “Either one of the two values is the root of T', or one is in each child of T'….” (i.e., the children refered to are those of T', not of T).
Proof that a binary tree is fully balanced if and only if it either is empty or both of its subtrees are fully balanced and have the same height. All occurrences of variable h in the third paragraph of the induction step should be H (i.e., the tree size for which the induction step is proving the proposition).
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 8, 2005 by Doug Baldwin