Binary search trees are arguably the most fundamental nontrivial class of data structures in computer science. Despite their origins at the dawn of computing, a complete understanding has remained elusive to this day. A surprising aspect of binary search trees is that their online and offline amortized performance are conjectured to be identical. This project seeks to completely characterize the binary search tree model of computation. This work will allow future researchers in data structures either to use a binary search tree that has been shown to be dynamically optimal or to know that their problem requires stepping outside the realm of binary search trees.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
0430849
Program Officer
Tracy J. Kimbrel
Project Start
Project End
Budget Start
2004-08-01
Budget End
2010-07-31
Support Year
Fiscal Year
2004
Total Cost
$245,999
Indirect Cost
Name
Polytechnic University of New York
Department
Type
DUNS #
City
Brooklyn
State
NY
Country
United States
Zip Code
11201