2011年1月7日星期五

遍历trie

当时在网络所实习的时候,还没有学过数据结构,觉得trie是一种很神奇的东西。现在想来,tree作为用来查找的结构,要求元素构成全序即可,而trie还要求元素构成字典序。
http://en.wikipedia.org/wiki/Trie

通常trie是用来查找的,怎么遍历它呢?
假设假设某个国家实行实名制上网,你要负责设计一个IP(v4)到身份证号的字典,而且被要求只能用trie,而且是定义成这样的:

struct Trie{
    Trie * left;
    Trie * right;
}

根节点指向一个Trie数组的首地址。查询时指向左孩子,如果待查询IP的二进制表示最高位是0,否则指向右孩子。如果孩子结点地址不幸指向数组件外面,则表明那不是文件地址,而是身份证号+数组的字节数,这个人拥有的IP段是他从根节点走到这里沿途收集的0-1串作为IP二进制表示的前缀的所有IP。好吧,我应该事先声明,这个国家人口稀少,以至于一个人可以拥有多个全球互联网上的IP段,而且为了方便市民记忆,身份证号也被设计的也很短。
遍历:
调用p(&data[0], "")
其中
p(Trie* node, string m)
{
  if node 指向超出数组边界:打印身份证号为((int)arr)-文件长度, 他的IP段(二进制表示)有m+(32-m.length)个'0' ~ m+(32-m.length)个'1',return
  p(node->left, m+‘0’)
  p(node->right, m+'1')
}

谨以此文献给即将用尽的IPv4地址和囤积了大量地址空间的IP黄牛们。
强烈推荐一篇用时间序列方法研究IPv4何时耗尽的论文,十分有趣:http://www.potaroo.net/tools/ipv4/#r5

没有评论: