algorithm - 为排序值生成排序键

Question

我需要维护从键到字符串值的映射，以及从值到键的映射。我需要确保始终对这两个列表进行排序。可以随时将新值添加到列表中。什么是最好的数据结构，以便在添加新值时，我们可以维护两个排序列表，而不必重新生成许多键，也不会导致不平衡的树？

Answer 1

这可以描述为“在这个问题中，目标是维护一个链表，每个节点都有一个明确的标签，这样标签在整个列表中都是单调的，可以在任何给定位置插入和删除。”？

这是http://courses.csail.mit.edu/6.897/spring05/lec/lec24.pdf的第 3 部分。它们展示了如何通过将表视为隐式树结构来维护按排序顺序排列的键表，其中在表的一部分中重新组织键等效于重新平衡子树。