为了实践,我一直在玩trie数据结构(没有与课程相关的工作)。该类用于存储字符串的子字符串。对于长度为n的字符串,有n(n+1)/2总子字符串。特别是,trie的这种实现保留了自然排序,并且比随机字符串上的TreeMap或TreeSet更有效。同时,存储单个字符而不是整个字符串可以节省内存。我认为,对于存储子字符串,后缀数组可能是更好的方法,但在启动新项目之前,我希望确保这个trie类在速度上得到了合理的优化。class Trie final Trie my_parent;
因此,我正在尝试阅读Trie,对我来说,这是一种相对较新的数据结构。在我读到的任何地方,trie中的每个节点都由一个整数变量组成,该变量将标记一个单词的结尾,并且还将由26个指针组成,每个指针指向较低级别的节点(假设单词只包含小写字母字符)。如下例所示:
另外,这是我实现插入的算法。struct trie int val;
trie* ap