尝试和红黑树对于存储字符串非常有效。
哪个时间复杂度更高？空间复杂度如何？
最佳答案
这取决于许多因素，例如要存储的字符串以及表示特里的方式。
在红黑树中，您将需要对每个操作(插入，删除，查找等)进行O(log n)字符串比较。如果比较两个没有公共(public)前缀的字符串，或者比较两个字符串较小的字符串，则比较的开销很小。比较的最坏情况是一个字符串是另一个字符串的前缀，在这种情况下，必须读取所有字符。因此，如果您想在一串红黑的字符串树中查找长度为L的字符串，在最坏的情况下，您将通过进行O(log n)比较来完成O(L log n)的工作，每个比较输入字符串中的所有字符。但是，在最佳情况下，这仅需要O(log n)时间，如果比较总是立即失败，则会发生这种情况。
就空间使用而言，红色/黑色树每个节点需要两个指针，每个字符串需要一个节点。 (红色/黑色位通常可以打包到指针的低位中)。因此，总空间为2n +(所有字符串的总长度)。
在特里树中，插入，删除和查找在最坏的情况下(如果必须考虑输入的所有字符)采用O(L)，在最坏的情况下(如果您提早退出特里树)采用O(1)。这比红黑树快O(log n)，这对于大型馆藏而言可能很重要。但是，特里树的位置较差，因为涉及更多的指针追逐，并且没有要扫描的连续字符数组。
就内存使用而言，一个字母大小为k的特里树通常需要总共kn个指针，其中n是节点数。如果字母大，这可能比红/黑树差得多。但是，可以通过使用Patricia树表示压缩Trie，使用更有效的数据结构存储子指针或从Trie构建DAWG来减少空间开销。
希望这可以帮助!