java来存储百万长度的百万密钥，红黑树和基数树哪个更好？ 5 月，2 周 Questions & Answers 141 我想存储多个长度为百万的键（字符串）及其关联对象。因此，我必须非常频繁地在数据结构（rbtree或基数树）中插入，并且与插入相比，搜索的时间非常少。任何推荐都将不胜感激。多谢各位
# 1 楼答案 既然插入是您最关心的问题，那么您应该使用红黑树，因为它的插入时间复杂度在输入大小中是对数的，即O(k*log n)，其中log是以2为底的对数，k是每个输入的大小或长度，n是输入的数量。基数树的插入在每个输入的大小k和输入的数量n上是线性的，即O(k*n)，这比红黑树更糟糕，除非字符串键的许多共享足够长的前缀，以便在n的亚对数表达式中转换n
# 1 楼答案
既然插入是您最关心的问题，那么您应该使用红黑树，因为它的插入时间复杂度在输入大小中是对数的，即
O(k*log n)，其中log是以2为底的对数，k是每个输入的大小或长度，n是输入的数量。基数树的插入在每个输入的大小k和输入的数量n上是线性的，即O(k*n)，这比红黑树更糟糕，除非字符串键的许多共享足够长的前缀，以便在n的亚对数表达式中转换n