Understanding Binary Search Trees

理解二叉搜索树

• 批准号: 0430849
• 负责人: John Iacono
• 金额: --
• 依托单位: Polytechnic University of New York
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-01 至 2010-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430849&HistoricalAwards=false
• 关键词: Understanding; Binary; Search; Trees

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.

二叉搜索树可以说是计算机科学中最基本的非平凡数据结构。 尽管它们起源于计算的黎明，但直到今天，对它们的完全理解仍然是难以捉摸的。 二叉搜索树的一个令人惊讶的方面是，它们的在线和离线摊销性能被证明是相同的。 该项目旨在完全描述二叉搜索树计算模型。这项工作将允许未来的研究人员在数据结构中使用二叉搜索树，已被证明是动态最优的，或者知道他们的问题需要走出二叉搜索树的领域。