Title page for ETD etd-07122006-160111


Type of Document Master's Thesis
Author Ding, Song
Author's Email Address sding1@lsu.edu
URN etd-07122006-160111
Title Optimal Binary Trees with Height Restrictions on Left and Right Branches
Degree Master of Science (M.S.)
Department Mathematics
Advisory Committee
Advisor Name Title
James Madden Committee Chair
Jianhua Chen Committee Member
Robert Perlis Committee Member
Keywords
  • knuth's algorithm
  • binary search tree
Date of Defense 2006-06-30
Availability unrestricted
Abstract
We begin with background definitions on binary trees. Then we review known algorithms for finding optimal binary search trees. Knuth's famous algorithm, presented in the second chapter, is the cornerstone for our work. It depends on two important results: the Quadrangle Lemma and the Monoticity Theorem. These enabled Knuth to achieve a time complexity of O(n2), while previous algorithms had been O(n3) (n = size of input). We present the known generalization of Knuth's algorithm to trees with a height restriction. Finally, we consider the previously unexamined case of trees with different restrictions on left and right heights. We prove the Quadrangle Lemma and the Monoticity Theorem in this case, and present an algorithm based on this.
Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Ding_thesis.pdf 345.58 Kb 00:01:35 00:00:49 00:00:43 00:00:21 00:00:01

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.