Sequential optimization of binary search trees for multiple cost functions

Maram Alnafie; Igor Chikalov; Shahid Hussain; Mikhail Moshkov

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 proceeding › Conference contribution › peer-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 ³) arithmetic operations per cost function such as weighted depth or average weighted depth.

Original language	English (US)
Title of host publication	Theory of Computing 2011 - Proceedings of the 17th Computing
Subtitle of host publication	The Australasian Theory Symposium, CATS 2011
Pages	41-44
Number of pages	4
State	Published - 2011
Event	Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011 - Perth, WA, Australia Duration: Jan 17 2011 → Jan 20 2011

Publication series

Name	Conferences in Research and Practice in Information Technology Series
Volume	119
ISSN (Print)	1445-1336

Other

Other	Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011
Country/Territory	Australia
City	Perth, WA
Period	01/17/11 → 01/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

Cite this

@inproceedings{e969273e7cfa440cbd8b2ae1274e9829,

title = "Sequential optimization of binary search trees for multiple cost functions",

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.",

keywords = "Binary search trees, Cost functions, Dynamic programming, Sequential optimization",

author = "Maram Alnafie and Igor Chikalov and Shahid Hussain and Mikhail Moshkov",

year = "2011",

language = "English (US)",

isbn = "9781920682989",

series = "Conferences in Research and Practice in Information Technology Series",

pages = "41--44",

booktitle = "Theory of Computing 2011 - Proceedings of the 17th Computing",

note = "Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011 ; Conference date: 17-01-2011 Through 20-01-2011",

}

Alnafie, M, Chikalov, I, Hussain, S & Moshkov, M 2011, Sequential optimization of binary search trees for multiple cost functions. in Theory of Computing 2011 - Proceedings of the 17th Computing: The Australasian Theory Symposium, CATS 2011. Conferences in Research and Practice in Information Technology Series, vol. 119, pp. 41-44, Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011, Perth, WA, Australia, 01/17/11.

Sequential optimization of binary search trees for multiple cost functions. / Alnafie, Maram; Chikalov, Igor; Hussain, Shahid et al.
Theory of Computing 2011 - Proceedings of the 17th Computing: The Australasian Theory Symposium, CATS 2011. 2011. p. 41-44 (Conferences in Research and Practice in Information Technology Series; Vol. 119).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Sequential optimization of binary search trees for multiple cost functions

AU - Alnafie, Maram

AU - Chikalov, Igor

AU - Hussain, Shahid

AU - Moshkov, Mikhail

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Binary search trees

KW - Cost functions

KW - Dynamic programming

KW - Sequential optimization

UR - http://www.scopus.com/inward/record.url?scp=84864609296&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84864609296

SN - 9781920682989

T3 - Conferences in Research and Practice in Information Technology Series

SP - 41

EP - 44

BT - Theory of Computing 2011 - Proceedings of the 17th Computing

T2 - Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011

Y2 - 17 January 2011 through 20 January 2011

ER -

Sequential optimization of binary search trees for multiple cost functions

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this