我知道 STL 中的 Map 容器内部是一棵红黑树，它是一棵自平衡树。
在 Map 中，最低的元素位于树的顶部。因此，对于整数到“任何东西”的映射，最小的整数将位于顶部，依此类推。它总是平衡自己。这就是为什么我们在搜索整数及其相关值时会得到 log n 复杂度。
但是在将字符串映射到“任何东西”的情况下，如果可以，它如何平衡和排序自己？哪个字符串会在树的顶部？它是否与 ASCII 值匹配？
这可能很蹩脚，但我需要知道这一点，因为我必须确保我在代码中遵守 log n 的复杂性。
问问题
116 次
1 回答
0
在 Map 中，最低的元素位于树的顶部。
不，最小的元素在最左边的节点，你可以通过跟随左子指针直到它为空来到达那个节点。在字符串的情况下，最小元素是始终比较“小于”您插入到映射中的所有其他字符串的元素。默认比较是字典顺序的。
平衡通过一堆指针交换照常进行。无论如何，从根到任何叶子的路径都保证具有长度 Θ(lg n)。
（这是假设 的原始 STL 实现map仍然很常见，尽管符合标准的 C++ 库可能使用不同的结构。）
于 2011-07-05T09:46:28.467 回答