• ACM Transactions on Algorithms 18(1):1-11(2022)

  With Marek Chrobak, Mordecai Golin and J. Ian Munro
  In 1971, Knuth gave an O(n²)-time algorithm for the classic problem of finding an optimal binary search tree. Knuth's algorithm works only for search trees based on 3-way comparisons, while most modern computers support only 2-way comparisons (e.g., <, <=, =, >=, and >). Until this paper, the problem of finding an optimal search tree using 2-way comparisons remained open --- poly-time algorithms were known only for restricted variants. We give an O(n⁴)-time algorithm for the general case. The algorithm and analysis are simpler than those for the previously solved special case.

  See also [Chrobak21Cost, Chrobak22Huang, Chrobak15Optimal.]

  • more...
  •   full text
    
  •   bibtex
    
  •   google scholar
    
  •   doi
    

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.