Geek asks and answers

Is sorted iteration an integral feature of Trie, or is it designed to be implemented?

Regarding Trie from Wikipedia:

[Compared to HashTable] Tries support ordered iteration

I'm not sure what is implied here in the first place. Is it the same as sorted iteration?
Also, should this be an integral feature of this data structure?
I mean, if you use, for example, a HashSetfor the children of each node in, Triewe can access O(1)to find children for branching or with the help LinkedListyou save space on the nodes.
Maybe I'm wrong, but from my point of view, the only way to support orderediteration would be to keep an array of all the keys on the node not even used.
Is this a bad approach?
And the last question:
Iforderedhere is related to the insertion order (and not sorted), how do we get this, because we insert each word (using characters in the form of keys) into the corresponding node, but I don’t see how this gives us information in the input order?
Can someone help me clear these things in my head? Thank.

+3
source share
2 answers

What they mean is that a search three times three times gives lexicographically ordered output of strings in trie.

But yes, you’re right, it assumes that all siblings at this level are visited in lexicographic order, and this is far from given, especially with large alphabets, where it makes sense to implement a node child table through a hash table.

, , .

, trie , arent , - trie node , trie - O (n) - -, , O (n log n).

+3

. - . , . ( ), .

0

More articles:


All Articles