sayeef006's blog

Upper bound for number of nodes in a trie?
By sayeef006, history, 2 years ago, In English

Can we estimate the upper bound of number of nodes of a trie? I'm using the array based implementation of trie, so i have to declare an array with the highest number of nodes, i know when inserting 32bit numbers the node count cant be greater than (N*32), but the actual upper bound should be way less right? Because for each node there are only two options for the next node? Am I right on this and if i am, can we estimate that value?

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Doesn't single insertion require 32 nodes? But for random insertions I don't know the expected value.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that this construction is optimal:

Greedy construction for 4 bits

Let's notice that the pattern of counts is $$$2, 2, 4, 8, 16, 32, 64, 128, 256$$$... So the answer is $$$2 * 32 + 2 * 31 + 4 * 30 + 8 * 29$$$... and so on while the sum of coefficients is less than $$$n$$$.

→ Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

Let's call the group of nodes which are at distance $$$x$$$ from the root 'level $$$x$$$' of the trie. In a binary tree, the number of nodes in level $$$x$$$ of the tree is at most $$$2^x$$$. Furthermore, in a trie, the number of nodes in any level is at most $$$N$$$.

Hence, the maximum number of nodes needed is $$$\sum\limits_{x=0}^{31}min(2^x, N)$$$. For $$$N = 10^6$$$, this number is $$$13048575$$$. I believe it is also possible to construct a trie with this number of nodes. (Construct a complete binary tree of minimal height such that it contains N leaves, then extend each of these leaves in a chain until each leaf is at depth 31. Then assign labels to each edge.)

→ Reply