h3. Sorting Big Numbers using Trie-Forest based search

h1. Sorting Big Numbers using Trie-Forest based search

h2. authors : Serban Lupulescu and Mircea Dima

h1. The first idea is that if you have a string of length h, you can insert it in a trie of height h. We could maintain a list of tries,

h3. The first idea is that if you have a string of length h, you can insert it in a trie of height h. We could maintain a list of tries,

trie H[N], where H[i] is a trie with height i so when we insert a string with lenght i, we insert it in H[i].

h3. trie H[N], where H[i] is a trie with height i so when we insert a string with lenght i, we insert it in H[i].

But what happens when we have, say 2 strings, one of length 3, and one with length 10^20? We can't declare H[10^20].

h3. But what happens when we have, say 2 strings, one of length 3, and one with length 10^20? We can't declare H[10^20].

Instead we can keep an optimal binary search tree, where the keys are the length of the trie, and the additional information is the

h3. Instead we can keep an optimal binary search tree, where the keys are the length of the trie, and the additional information is the

trie itself.

h3. trie itself.

Now if we have a string with length h we have 2 possibilities:

h3. Now if we have a string with length h we have 2 possibilities:

1) if there is a trie with height h in the binary search tree, we insert the string in that trie

h3. 1) if there is a trie with height h in the binary search tree, we insert the string in that trie

2) if there isn't a trie with height h in the binary search tree, we create it, we insert the string, and then we insert the trie in

h3. 2) if there isn't a trie with height h in the binary search tree, we create it, we insert the stringh, and then we insert the trie in

the binary search tree.

h3. the binary search tree.

== code(c) |