Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
X-fast trie
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, an x-fast trie is a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> for storing <a href="/facts/Integer/PUwwrawx">integers</a> from a bounded domain. It supports exact and predecessor or successor queries in time <a href="/facts/Big-O_notation/weFFjSWg"><i>O</i></a>(log log <i>M</i>), using <i>O</i>(<i>n</i> log <i>M</i>) space, where <i>n</i> is the number of stored values and <i>M</i> is the maximum value in the domain. The structure was proposed by <a href="/facts/Dan_Willard/EFn9KKzE">Dan Willard</a> in 1982, along with the more complicated <a href="/facts/Y-fast_trie/RRAPcoeK">y-fast trie</a>, as a way to improve the space usage of <a href="/facts/Van_Emde_Boas_tree/X2L5WtU0">van Emde Boas trees</a>, while retaining the <i>O</i>(log log <i>M</i>) query time. </p>