About extending trie

[aniervs]

I was thinking about supporting deleting a string.
There could be 2 interpretations, which don't conflict with each other:

• Erasing all occurrences of that word. That means that if a word was inserted N times, then after deleting it, it won't appear in the Trie.
• Erasing one of the occurrences of that word. That means that if a word was inserted N times, then after deleting it, it will appear N-1 times in the Trie.

Both things can be implemented clearly by adding an argument to the method that specifies which behavior is required. We can even add an argument that tells the number of occurrences to delete.

What do you think?

[albexl]

I think that if we add the argument to tell the number of occurrences to delete and we set the default value to 1, then we can reuse it.

This method by itself will allow the client to be able to delete as many occurrences as it wants. And we should control internally that this number is not greater than the number of times this word has been inserted.

On the other hand, if the client wants to delete all occurrences of one word, the easiest way I can think of is to have it do something like this:

• Get the number of occurrences.
• Delete (number of occurrences).

And I would not like the client to do that. Instead, I think we should have a different method delete_all, and then use the method that deletes occurrences with the "number" parameter set to the number of occurrences of the word.

Did I make myself clear? Does it sound good?

[albexl]

I added a preliminary version of this functionality (check here implementation.py).

Tests are here test_trie.py

It would be great if you could take a look.

[aniervs]

Seems alright! A concern: we should probably delete the node when the count becomes 0, right? If so, then we should probably implement a garbage collector, as when deleting a leaf, its parent may become a leaf, and the parent of its parent, and so on, ...
I think we can't rely on Python's garbage collector.

For implementing it, I guess we can either do it recursively (I don't like the idea) or iteratively by keeping track of the visited nodes during the forward pass and going backward to delete all the trash.

What do you think?

[aniervs]

UPD: I added a pull request implementing this.

[albexl]

I will take a look soon. Also, I will read about garbage collectors, specifically in Python. I might get a better idea of how it works and get back to you with a proper answer.

[aniervs]

I don't know much about garbage collectors either, but I just know they delete all memory that's not referenced (like nodes without parents, ...). In the Trie, we need to remove the corresponding leaf when the times arg is equal to the number of occurrences of the word. But after removing it, we will have a branch on the Trie that doesn't lead anywhere, and therefore for enhancing memory and time performance, better to remove it. That's all, I probably shouldn't have mentioned garbage collectors there, as that's not exactly what we are doing.