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

-- 
Change is inevitable, except from a vending machine.

It sounds to me like you want to build a separate index for the trie rather than do something clever.

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

Maybe maintain overall order via a linked list (head and tail pointers for the whole tree + next/prev on each node), modified at insertion/removal of nodes? That should provide O(1) access to largest and smallest number.

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?

Is it necessary to store decimal numbers?
Because if they would be stored binary, the highest number would automatically be among the longest strings.

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?
>

Just to get the dumb answer out of the way: we need to assume that the trie is updated dynamically, right? So just trivially taking the maximum while inserting all the members won't work.

In the dynamic case, keeping a separate sorted list sounds best if memory usage is of no concern to you. If you really need only the largest value and performance is a concern, a max heap would probably be faster than a fully sorted list.

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.