Y-Fast Tries – Recall From Friday

A y-fast trie representing a set S of n keys consists of the

following.

• A separator set containing n/log(u) of the entries in S, evenly

spaced.

• An x-fast trie representing the elements of the separator set.

• A collection of n/log(u) balanced search trees, each of which

contains the log(u) elements of S that are strictly between

two consecutive separators.

Last class, we argued that this structure requires Θ(n) memory

space.

1/7

Y-Fast Tries

Here is the example from Friday.

x-fast trie

0 1

00 01 10

000 010 101

0000 0100 1010

2 8 13

1 3 6 9 11 14

15

balanced search trees

2/7

Y-Fast Tries

QUICK EXERCISE. How does predecessor(x) work on a y-fast

trie? What is its run time?

Answer

• Start by applying the predecessor algorithm to the x-fast trie.

This costs O(loglog(u)) time as before.

• If the resulting leaf in the x-fast trie contains x, return x.

Otherwise, let v be the value in this leaf.

• Search for the predecessor of x in the balanced search tree

corresponding to this leaf. Since the height of this tree is

O(loglog(u)), this operation also costs O(loglog(u)) time.

• If x has no predecessor in the search tree, return v; otherwise

return the result from the search tree.

Total run time: O(loglog(u)).

3/7

Y-Fast Tries

QUICK EXERCISE. How does search(x) work in a y-fast trie?

How about insert(x)? What are the run times?

Answer

• For both operations, start with the predecessor routine on the

x-fast trie. React appropriately if the leaf of the trie contains

x.

• Otherwise, run the search or insert operation on the search

tree that corresponds to the leaf of the trie.

In both cases, the total run time is O(loglog(u)).

You may foresee a pitfall, which you will address in Assignment 1.

4/7

Y-Fast Tries

QUICK EXERCISE. How does delete(x) work if x is not one of

the keys in the x-fast trie? What about when it is one of the keys

in the x-fast trie?

Answer

As usual, start with predecessor(x) on the x-fast trie.

• If the leaf of the trie does not contain x, call delete(x) on

the corresponding search tree.

• If the leaf of the trie does contain x, delete x from the x-fast

trie, then find the minimum value in the corresponding search

tree, delete that value from the search tree, and insert it into

the x-fast trie.

5/7

Y-Fast Tries

Notice that the second case runs in O(log(u)) time due to the

operations on the x-fast trie.

The worst case occurs if the entry to be deleted is in the x-fast

trie. By construction, only n/log(u) of the n entries in S satisfy

this condition.

IF we assume that the entry to be deleted is selected uniformly

randomly from S, the probability that any one entry results in the

worst case is 1/log(u). Consequently, the expected run time of

the delete operation is

(cid:18) (cid:19)

1 1

E(run time) = ×log(u)+ 1− ×loglog(u)

log(u) log(u)

∈ Θ(loglog(u)).

6/7

Y-Fast Tries

Summary

• The structure of a y-fast trie only makes sense if n > log(u).

Under that assumption, notice that log(n) > loglog(u).

• A y-fast trie representing n keys requires Θ(n) space.

• The search and predecessor operations run in worst-case

O(loglog(u)) time (assuming worst-case O(1) time to search

a hash table).

• The insert operation runs in expected, amortized

O(loglog(u)) time (assuming expected O(1) time to insert

into a hash table).

• The delete operation runs in worst-case O(log(u)), although

the entries that give rise to the worst case are relatively rare.

7/7