Numerically largest entry in a trie of digits
Alexandru Ermicioi
alexandru.ermicioi at gmail.com
Wed Apr 20 10:00:14 UTC 2022
On Tuesday, 19 April 2022 at 16:35:21 UTC, H. S. Teoh wrote:
> Just thought I'd pick all the bright minds here: I have a set
> of numbers in string form (as decimal digits), stored in a
> trie. How do I retrieve the largest number in the set?
>
> My initial guess was to find the rightmost child in the trie.
> Unfortunately, this is incorrect, because the rightmost child
> may not necessarily be the largest numerically. For example,
> consider the set {1, 9, 10}. In trie form, 10 would be a child
> of 1 (it would be stored as the digit path 1 -> 0), and the
> rightmost child would be 9, which is less than 10.
>
> It would appear that what I want is the rightmost *longest*
> entry in the trie. Is there a more efficient way to compute
> this, short of brute-force traversal over the entire trie?
>
>
> T
Perhaps have each node children sorted first by:
- having themselves a child
- digit itself
Then rightmost/leftmost chain of nodes should give what you want.
Alexandru.
More information about the Digitalmars-d
mailing list