Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Key-independent optimality
open-in-new
<p>Key-independent optimality is a property of some <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree </a> data structures in <a href="/facts/Computer_science/lN3pEyPz">computer science</a> proposed by <a href="/facts/John_Iacono/q1obsg5x">John Iacono</a>. Suppose that <a href="/facts/Attribute%E2%80%93value_pair/buweLY96">key-value pairs</a> are stored in a data structure, and that the keys have no relation to their paired values. A data structure has key-independent optimality if, when randomly assigning the keys, the expected performance of the data structure is within a constant factor of the optimal data structure. Key-independent optimality is related to <a href="/facts/Optimal_binary_search_tree/ESfe6hoL">dynamic optimality</a>. </p>