以下是课本上的一个问题算法导论，但是没有给出问题的解决方案...
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?
对于这个问题，我相信如果列表已排序，搜索的运行时间将是相同的，因为它们是链接列表，并且仍然需要遍历整个列表才能找到值。
但是，对于插入，会花费更长的时间，因为现在必须保留顺序，因此不能只将值插入到列表的头部。我相信它不再是O(1)。
对于删除我不知道。
事实上，我不太确定我的答案是否正确，有人可以帮我吗？
最佳答案
您可以通过对同一槽中的元素进行排序来提高性能，但不能使用链表。
相反，可能使用平衡树(而且，通常是红黑树)。
但是，这是一个权衡，只有当同一槽中的元素超过一定数量时，才会真正提高性能。
示例 - Java 的 HashMap
在 Java 8 中，HashMap 被重写为使用链表 和红黑树 来表示槽中的元素。
有 treeify() 和 untreeify() 操作可在两种结构之间进行转换，由预定义的阈值触发。
关于algorithm - 通过保持列表的排序顺序来提高哈希表操作的运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55265201/