# Doubly-Logarithmic Time

Learn about XFastTrie and YFastTrie searching.

`XFastTrie`

: searching in doubly-logarithmic Time

The performance of the `BinaryTrie`

structure is not very impressive. The
number of elements, `n`

, stored in the structure is at most $2^w$, so $\log n \leq w$. In other words, any of the comparison-based `SSet`

are at least as efficient as a `BinaryTrie`

, and are not restricted to only storing integers.

Next, we describe the `XFastTrie`

, which is just a `BinaryTrie`

with $w + 1$
hash tables—one for each level of the trie. These hash tables are used to
speed up the `find(x)`

operation to $O(\log w)$ time. Recall that the `find(x)`

operation in a `BinaryTrie`

is almost complete once we reach a node, `u`

, where the search path for `x`

would like to proceed to `u.right`

(or `u.left`

) but `u`

has no right (respectively, left) child. At this point, the search uses `u.jump`

to jump to a leaf, `v`

, of the `BinaryTrie`

and either return `v`

or its successor in the linked list of leaves. An `XFastTrie`

speeds up the search process by using binary search on the levels of the trie to locate the node `u`

.

To use binary search, we need a way to determine if the node `u`

we are looking for is above a particular level, `i`

, or if `u`

is at or below level `i`

. This information is given by the highest-order `i`

bits in the binary representation of `x`

; these bits determine the search path that `x`

takes from the root to level `i`

.

### Visual demonstration of the search path

The visual demonstration of the search path is shown below:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy