successor of q is contained in the p1 subtree, and if the next bit of q is 1, then the predecessor of q is contained in the p0 subtree. This suggests the following algorithm for determining the exact location of q: Use parallel comparison to find the index i such that sketch(xi-1) ≤ sketch(q) ≤ sketch(xi). Compute the longest common prefix p of q and either xi-1 or xi (taking the longer of the two). Let l-1 be the length of the longest common prefix p. If the l-th bit of q is 0, let e = p10w-l. Use parallel comparison to search for the successor of sketch(e). This is the actual predecessor of q. If the l-th bit of q is 1, let e = p01w-l. Use parallel comparison to search for the predecessor of sketch(e). This is the actual successor of q. Once either the predecessor or successor of q is found, the exact position of q among the set of keys is determined. Fusion hashing An application of fusion trees to hash tables was given by Willard, who describes a data structure for hashing in which an outer-level hash table with hash chaining is combined with a fusion tree representing each hash chain. In hash chaining, in a hash table with a constant load factor, the average size of a chain is constant, but additionally with high probability all chains have size , where is the number of hashed items. This chain size is small enough that a fusion tree can handle searches and updates within it in constant time per operation. Therefore, the time for all operations in the data structure is constant with high probability. More precisely, with this data structure, for every inverse-quasipolynomial probability , there is a constant such that the probability that there exists an operation that exceeds time is at most . References External links MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003) MIT CS 6.897: Advanced Data Structures: Lecture 5, More fusion trees; self-organizing data structures, move-to-front, static optimality, Prof. Erik Demaine (Spring 2003) MIT CS 6.851: Advanced Data Structures: Lecture 13, Fusion Tree notes, Prof. Erik Demaine (Spring 2007) MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof. Erik Demaine (Spring 2012) Trees (data structures) Associative arrays