ABSTRACT
In this paper we propose using experiments with BalancedSample
Binary Trees (BSBTrees) as assignments and lecture
material in intermediate data structures courses (CS2/3).
BSBTrees are composite data structures that have a temporarily
constructed form that precedes their normal construction.
We present them in the context of binary search
trees. To do this we first investigate the retrieval properties
of randomly generated binary search trees and show how
temporary construction can improve both worst case and
average case behavior. We provide a brief analysis of BSBTree
performance and description of the classes that can
be used for BSBTree implementation. Last we discuss the
use of BSBTrees in CS2 and CS3 courses and a survey of
student opinions about BSBTrees.