Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Interleave lower bound
open-in-new
<p>In the theory of <a href="/facts/Optimal_binary_search_tree/ESfe6hoL">optimal binary search trees</a>, the interleave lower bound is a <a href="/facts/Asymptotically_optimal/fnfvbMYE">lower bound</a> on the number of operations required by a Binary Search Tree (BST) to execute a given sequence of accesses. </p><p>Several variants of this lower bound have been proven. This article is based on a variation of the first Wilber's bound. This lower bound is used in the design and analysis of <a href="/facts/Tango_tree/GwavH3cj">Tango tree</a>. Furthermore, this lower bound can be rephrased and proven geometrically, <a href="/facts/Geometry_of_binary_search_trees/c7orbGdH">Geometry of binary search trees</a>. </p>