Блог пользователя sayeef006

Автор sayeef006, история, 2 года назад, По-английски

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?

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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$$$.

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

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.)