G. Michael Barnes
John Noga
ABSTRACT
In this paper we propose using experiments with Balanced-Sample 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.
- Barnes, G. M. BSBTree source listing and JAVA™ documentation. http://www.csun.edu/ renzo/pub/BSBTree.html, September 2003.Google Scholar
- Devroye, L. A note on the height of binary search trees. Journal of the ACM 33, 3 (1986), 489--498. Google ScholarDigital Library
- Gonnet, G. H., and Baeza-Yates, R. Handbook of Data Structures and Algorithms in Pascal and C, second ed. Addison-Wesley, 1991. Google ScholarDigital Library
- Marsaglia, G. The marsaglia random number cd-rom with the diehard battery of tests of randomness. http://www.stat.fsu.edu/pub/diehard, 1995.Google Scholar
- Martin, W.A., and Ness, D.N. Optimizing binary trees grown with a sorting algorithm. Communications of the ACM 15, 2 (1972), 88--93. Google ScholarDigital Library
- Martinez, C., and Roura, S. Randomized binary search trees. Journal of the ACM 45, 2 (1988), 288--323. Google ScholarDigital Library
- Michie, D. 'Memo' functions and machine learning. Nature 218 (1968), 19--22.Google ScholarCross Ref
- Noga, J. Sbtree analysis. http://www.csun.edu/jnoga/pub/BSBTrees.html, September 2003.Google Scholar
- Noga, J. Additional BSBTree content. http://www.csun.edu/jnoga/pub/BSBTrees.html, May 2004.Google Scholar
- Wiegley, J. CS3 BSBTree project. http://www.csun.edu/jnoga/pub/BSBTrees.html, May 2004.Google Scholar
- Wirth, N. Algorithms + Data Structures = Programs. Prentice-Hall, 1985. Google ScholarDigital Library
Index Terms
- Experiments with balanced-sample binary trees
Recommendations
Experiments with balanced-sample binary trees
In this paper we propose using experiments with Balanced-Sample 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 ...
On subtrees of trees
We study that over a certain type of trees (e.g., all trees or all binary trees) with a given number of vertices, which trees minimize or maximize the total number of subtrees (or subtrees with at least one leaf). Trees minimizing the total number of ...
The Fermat star of binary trees
A Fermat point P is one that minimizes the sum @d of the distances between P and the points of a given set. The resulting arrangement, called here a Fermat star, is a particular Steiner tree with only one intermediate point. We extend these concepts to ...
Comments