Group Group Group Group Group Group Group Group Group

raywenderlich.com Forums

Swift Algorithm Club: Swift Trie Data Structure

Learn how to implement the trie data structure in Swift - a data structure that is extremely handy for prefix-matching in the English language.


This is a companion discussion topic for the original entry at https://www.raywenderlich.com/892-swift-algorithm-club-swift-trie-data-structure

There is a bug in your code for removing a word. You can reproduce the bug with the following code:

trie.insert(word: “cute”)
trie.insert(word: “cut”)
trie.remove(word: “cute”)
trie.contains(word: “cut”)
trie.contains(word: “cute”)

The last statement returns false which is wrong.

To fix the bug, replace the code marked “4” with

    if currentNode.children.count > 0 {
        currentNode.isTerminating = false
    } else {
        var character = currentNode.value
        while currentNode.children.count == 0, let parent = currentNode.parent {
            currentNode = parent
            currentNode.children[character!] = nil
            character = currentNode.value
            if currentNode.isTerminating {
                break
            }
        }
    }

Sorry, the last statement returns true.

Good catch @zampano! I’ll update the repository to correct that.

@Zampano Here’s the PR https://github.com/raywenderlich/swift-algorithm-club/pull/310. Feel free to give me some feedback so we can get some peer review going!

The insert method ends with the following two lines:

if currentIndex == characters.count {
currentNode.isTerminating = true
}

It seems that because of the condition on the while loop, this if will always be true and that the assignment alone is sufficient to complete this method. Are there any instances where this test makes a difference?

You mention that count, words and isEmpty are O(1) operations. isEmpty is fairly obvious. It seems that count would be O(1) if you introduce a new property count that gets increased every time isTerminating gets set to true and decreased every time it gets set to false. A count would then return the value of this property. Is there a better way to do this?

The words method would return a list of all of the words in the trie. I don’t see how this could be an O(1) operation. Wouldn’t it be a recursive traversal?

Even though the if statement confirms that

currentNode.children.count == 0

is true, don’t you still need the test in the while loop? You want to continue moving up removing all nodes that have zero children.

Peer review FTW :slight_smile:

Let’s bring this conversation over to the repo, so it’s easier to keep track of the discussions regarding the changes: https://github.com/raywenderlich/swift-algorithm-club/pull/310

I would like to see code for serializing a trie using NSCoding and saving it to a file. I’ve looked around for examples that use NSCoding to serialize a recursive structure, but haven’t found any. Does anyone have ideas on how to do this? The only downside of adding this (that I can see) is that the trie nodes can no longer be generic. A class that implements NSCoding cannot be generic. This doesn’t seem like a big problem to me though. The Trie class is based on the fact that nodes contain characters.

Hmm, I’m not sure. I suppose you want to avoid reconstructing the tree during deserialization? One way could be extracting all the words of the Trie, serializing that into an array. When you deserialize, you can reassemble it into a Trie.

We should get more eyes on this question by posting it on the repo. Interesting question :slight_smile:

Loved the guide!

I was trying to create a recursive function that could search the Trie for words contained in an anagram. For example, it might take a scrambled string “rehnla” and would return and array of strings [“learn”,“heal”,“hen”, etc.]. The idea was described here http://stackoverflow.com/a/880611

Any ideas on how I could try and implement this?

This tutorial is more than six months old so questions are no longer supported at the moment for it. We will update it as soon as possible. Thank you! :]