xuh*_*156 6 tree complexity-theory trie red-black-tree data-structures
尝试和红黑树非常有效地存储字符串.
哪个时间复杂度更高？空间复杂性怎么样？
tem*_*def 13
这取决于许多因素,例如您存储的字符串以及如何表示trie.
在红黑树中,您需要对每个操作(插入,删除,查找等)进行O(log n)字符串比较.如果比较两个没有公共前缀的字符串,或者比较字符串很小的两个字符串,则比较的成本很小.比较的最坏情况是当一个字符串是另一个字符串的前缀时,在这种情况下必须读取所有字符.因此,如果你想在一个红黑色的字符串树中查找长度为L的字符串,在最坏的情况下,你可以通过进行O(log n)比较来进行O(L log n)工作,每个比较看一下输入字符串中的所有字符.但是,在最好的情况下,这只需要O(log n)时间,如果比较总是立即失败,则会发生这种情况.
在空间使用方面,红/黑树每个节点需要两个指针,每个字符串需要一个节点.(红色/黑色位通常可以打包到指针的低位).因此总空间为2n +(所有弦的总长度).
在一个特里,插入,删除和查找在最坏的情况下(如果必须考虑输入的所有字符)采用O(L),在最好的情况下采用O(1)(如果你提前脱离trie).这比红黑树快60倍(log n),这可能对大型集合很重要.然而,trie具有更差的局部性,因为涉及更多的指针追逐并且没有要扫描的连续字符阵列.
在内存使用方面,具有大小为k的字母表的trie通常需要总共kn指针,其中n是节点的数量.如果字母表大小很大,这可能比红/黑树差得多.但是,通过使用Patricia树表示压缩trie,使用更有效的数据结构来存储子指针,或者从trie构建DAWG,可以减少空间开销.
希望这可以帮助!