Using arrays to speed up static tree traversal

Over the last two weeks I wrote about how to construct and query a string prefix-trie. We used the data structure to quickly find all strings with a given prefix, and to find the longest common prefix in that list.

Today we will take a look at how we can use arrays to improve performance even further. We will also take a closer look at the run-time of our algorithms from last week’s posts and show how our new approach is significantly better.

While we are looking at the example of a prefix-trie, the same method can be applied to any static tree.

Tree traversal

When we are talking about tree traversal, we mean the enumeration of the entire tree – or one of its sub-trees – in question. In the case of a prefix-trie, we are most often interested in retrieving all contained strings starting with a given prefix.

The way we did this in our previous implementation was by finding the node representing the given prefix and then enumerating the tree of which that node is the root. The implementation of that is not necessarily straight forward, if we care about performance.

After exploring other possibilities, this is the algorithm we ended with:

IEnumerable<string> enumerateAllValues(Node root)
{
    var stack = new Stack<Node>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var node = stack.Pop();
        if (node.value != null)
            yield return node.value;
        if (node.children == null)
            continue;
        foreach (var child in node.children.Values)
            stack.Push(child);
    }
}

Note how we use a stack to allow the method to behave as if it were recursive, without running into the problem of repeated re-iteration using the yield statement.

Overall this implementation is fairly efficient. It runs in O(k * l) time, and uses (roughly*) _O(l)_ space, where _k_ is the number of returned strings, and _l_ is the length of the longest such string.

*we are assuming a bounded branching factor

Clearly the algorithm has to be linear in k, to be able to return all strings.

The dependency on l – in both time and space – however is less obvious. In this case it is caused by the fact that we have to iterate through all the nodes, which means essentially one node per character.

This dependency can be problematic if we are dealing with very long – or even just very many – strings. Ideally, we would like to improve our algorithm to be entirely independent of l, and simply run in O(k) – the optimal time.

Using a backing array for faster iteration

With the code we have so far, our prefix-trie is entirely static after construction. As long as this is the case, we can use this fact to significantly increase performance of our tree traversal – by entirely removing it, and this the dependency on l.

Let us revisit how we construct our prefix-trie: In essence, we use a divide and conquer algorithm on a sorted list of our strings to split the current sub-list into children for the current node.

Node(List<string> strings, int characterIndex, int iMin, int iMax)
{
    var s = strings[iMin];
    if (s.Length == characterIndex)
    {
        this.key = s;
        iMin++;
    }
    if (iMin >= iMax)
        return;
    this.children = createChildrenDictionary(
        strings, characterIndex, iMin, iMax);
}

For the code behind the chreateChildrenDictionary method, see the post on constructing our prefix-trie.

The only thing we have to do is in addition to storing the node’s value – if it has one – and its children also store the minimum and maximum index of the strings contained in this sub-tree:

Node(List<string> strings, int characterIndex, int iMin, int iMax)
{
    this.iMin = iMin;
    this.iMax = iMax;
    /* rest of the constructor */
}

If we then keep track of our method as well, we can use the list and indices to enumerate a node’s sub-tree almost trivially:

IEnumerable<string> enumerateAllValues(Node root, List<string> strings)
{
    for (int i = root.iMin; i < root.iMax; i++)
        yield return strings[i];
}

This method now clearly runs in O(k) time and requires only constant space.

Exposing more data by returning an IReadOnlyList

While we are at it, we can go even further and expose even more data to our users. For example, it would be trivial to calculate the number of returned strings by subtracting the stored indices. In addition we could provide an indexer to allow callers to quickly search the resulting collection, iterate it backwards, or do whatever else they like.

Clearly we cannot give access to our internal list however. If we did so, anyone could modify it and invalidate the entire data structure.

Instead, we will write a small class wrapping the concept of a read-only sub-list. The class will implement the IReadOnlyList<T> interface, which in turn implements IReadOnlyCollection<T> and IEnumerable<T>

The members we will have to implement are:

IEnumerator<T> IEnumerable<T>.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator();
int IReadOnlyCollection.Count;
T IReadOnlyList.Item[int index];

Our constructor will be as follows:

public ReadOnlySubList(List<T> list, int iMin, int iMax)
{
    if (list == null)
        throw new ArgumentNullException("list");
    if (iMin < 0)
        throw new ArgumentOutOfRangeException("iMin");
    if (iMax > list.Count)
        throw new ArgumentOutOfRangeException("iMax");
    this.list = list;
    this.iMin = iMin;
    this.iMax = iMax;
}

With this in place, we can copy our iteration code from above to implement the enumerators:

public IEnumerator<T> GetEnumerator()
{
    for (int i = this.iMin; i < this.iMax; i++)
        yield return this.list[i];
}
IEnumerator IEnumerable.GetEnumerator()
{
    return this.GetEnumerator();
}

The Count property is also rather trivial:

public int Count { get { return this.iMax - this.iMin; } }

The thing we have to be most careful about is our indexer. We have to make sure to not only perform the correct subtraction to convert the sub-list index to that of the actual list, but we also have to make sure to check the index for whether it in fact falls within the sub-list’s range. If we do not do so, a caller might give us too large – or even negative – indices, and we might return strings happily, since the sub-list may be located in the middle of the actual list.

public T this[int index]
{
    get
    {
        var i = index - this.iMin;
        if (i < this.iMin || i >= this.iMax)
            throw new ArgumentOutOfRangeException("index");
        return this.list[i];
    }
}

And that is all!

We can now replace our original method with the following to return an instance of our new class, exposing much more potentially useful information to the caller.

IReadOnlyList<string> enumerateAllValues(Node root, List<string> strings)
{
    return new ReadOnlySubList<string>(strings, root.iMin, root.iMax);
}

Conclusion

Today we explored some possibilities for improving the performance of a previously developed algorithm. We took advantage of the static tree constraint of our data structure to develop a direct access algorithm which allowed us to do an effective tree-traversal without actually having to look at any of the nodes.

We further wrote a small helper class through which we can give our callers even more information about the result of the algorithm, empowering them to optimize their own algorithms.

As a bonus, we ended up with a neat utility class that could come in handy in a number of circumstances.

Enjoy the pixels!