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