Sequential optimization of binary search trees for multiple cost functions

Maram Alnafie*, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

In this paper, we present a methodology to model the optimal binary search tree problem as a directed acyclic graph to extract all possible optimal solutions. We provide a mechanism to find optimal binary search trees relative to different types of cost functions, sequentially. We prove that for a set of n keys our optimization procedure makes O(n 3) arithmetic operations per cost function such as weighted depth or average weighted depth.

Original languageEnglish (US)
Title of host publicationTheory of Computing 2011 - Proceedings of the 17th Computing
Subtitle of host publicationThe Australasian Theory Symposium, CATS 2011
Pages41-44
Number of pages4
Volume119
StatePublished - 2011
EventTheory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011 - Perth, WA, Australia
Duration: Jan 17 2011Jan 20 2011

Other

OtherTheory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011
CountryAustralia
CityPerth, WA
Period01/17/1101/20/11

Keywords

  • Binary search trees
  • Cost functions
  • Dynamic programming
  • Sequential optimization

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems
  • Software

Fingerprint

Dive into the research topics of 'Sequential optimization of binary search trees for multiple cost functions'. Together they form a unique fingerprint.

Cite this