arrays - 扫描二叉搜索树与数组

在 BST 中查找元素（遍历）会比在数组中线性扫描要慢吗？

据说答案与缓存有关。有人可以解释这到底意味着什么以及为什么它是正确的吗？

您究竟是如何使用数组而不是使用 BST 缓存来“缓存这个”的？

谢谢

标签： arrayscachingtreeoperating-system

我的猜测是，使用 BST 不会给您带来任何优势，因为即使您正在缓存数据（这意味着存在某种局部性，例如，您可以稍后访问相同的元素），插入操作和查找操作总是花费O(h)，其中 h 是树的高度。在最坏的情况下，甚至O(n)。

而使用数组进行缓存当然意味着，起初它可能是线性的，但是当您之后访问数组的相同元素时，如果存在空间和时间局部性，您可能会发现自己直接重复访问相同的连续内存块，因为你已经知道它的索引，这意味着你有一个恒定的时间访问。