Fringe analysis of binary search trees

Simple item page
dc.contributor.advisorHuang, Stephen S. H.
dc.contributor.committeeMemberJohnson, Olin G.
dc.contributor.committeeMemberWu, Tiee-Jian
dc.creatorLoo, Im Pa
dc.date.accessioned2023-11-27T17:11:57Z
dc.date.available2023-11-27T17:11:57Z
dc.date.issued1985
dc.description.abstractFringe analysis is a technique to analyze search trees. It was first formulated by A. Yao to estimate the expected number of nodes in 2-3 trees and B-trees. This technique has been used and studied by many researchers. We present a formal definition of a fringe and an algorithm to find a fringe base for fringe analysis in binary search trees. We also define classes of fringe (balanced) trees depending on a parameter d. These fringe balanced trees can be used to estimate the performance of certain balanced trees. The technique is applied to AVL trees, Internal Path Reduction trees and 1-2 brother trees.
dc.description.departmentComputer Science, Department of
dc.format.digitalOriginreformatted digital
dc.format.mimetypeapplication/pdf
dc.identifier.other12530992
dc.identifier.urihttps://hdl.handle.net/10657/15493
dc.language.isoen
dc.rightsThis item is protected by copyright but is made available here under a claim of fair use (17 U.S.C. Section 107) for non-profit research and educational purposes. Users of this work assume the responsibility for determining copyright status prior to reusing, publishing, or reproducing this item for purposes other than what is allowed by fair use or other copyright exemptions. Any reuse of this item in excess of fair use or other copyright exemptions requires express permission of the copyright holder.
dc.subjectData structures (Computer science)
dc.subjectBinary system (Mathematics)
dc.subjectFile organization (Computer science)
dc.titleFringe analysis of binary search trees
dc.type.dcmiText
dc.type.genreThesis
thesis.degree.collegeCollege of Natural Sciences and Mathematics
thesis.degree.departmentComputer Science, Department of
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Houston
thesis.degree.levelMasters
thesis.degree.nameMaster of Science

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Loo_1985_12530992.pdf
Size:
1.44 MB
Format:
Adobe Portable Document Format
Download

Collections

Legacy Theses and Dissertations (1940-2009)