JavaScript is disabled for your browser. Some features of this site may not work without it.
Optimal Shortcuts for Balanced Search Trees

Author
Hartline, Jeff
Abstract
We present an alternative to tree rebalancing for improving the
expected search cost in weighted binary search trees. This alternative is based on the insertion of shortcut links between nodes in the search tree. We propose several shortcut models and give polynomial time algorithms to find the best shortcuts for two of these models.
Date Issued
2006-02-23Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2006-2017
Type
technical report