当老师问到“二叉搜索树具有二叉搜索树属性意味着什么，这使其适合实现Map”时，我对BST和Map之间的关系感到困惑。是否有人能为我解释一下？谢谢。
1个回答
7
地图是一种关联容器，其中的键不是强制性整数（与数组相反，在数组中，键始终是数字）。
现在您希望存储多个 key，value对，并且希望能够高效地按其键查找值或高效地添加对或删除对以及进行其他操作。
二叉搜索树是一种数据结构，其所有操作的平均时间复杂度为O(log n)。这意味着您可以高效地搜索树的特定节点（该节点将具有自己的键和值）。
这就是使用BST实现地图的重点，从而获得某些操作方面高效的结构，但这不是实现地图的唯一方法（考虑哈希表）。
- Jack
6
1数组中键值总是数字 - 在许多编程语言中，但并非所有。 - greybeard
因此，二叉搜索树实现的映射仍然不如哈希映射好，后者的复杂度为O(1)。 - 1ang
@greybeard：如果数组的键不是数字，则它不是数组，而是关联数组或映射。现在这个术语有点模糊，因为一些编程语言假装将它们的映射称为数组（因为它们允许将任何类型的键与值进行映射），但它们不是数组，它们是映射。 - Jack
@1ang：是的，哈希表的时间复杂度为O(1)，但对于较小的数据结构，这种固定复杂度可能比简单的O(logn)查找更高。此外，您还需要考虑内存复杂度，必须考虑到当哈希表超过其负载因子时需要重新哈希的事实，最重要的是BST可以管理排序，而哈希表则不能。 - Jack
@greybeard：我并不考虑平衡树，我说的是一般的BST。对于平均情况，你有O(logn)，对于最坏情况，你有O(n)。你可以用平衡树来改善最坏情况，但这不是重点。在“通过计算复杂性理论证明”的意义上指定，还有另一个问题，这不是答案的重点，也与OP无关。 - Jack
你指出的一些区别确实超出了“二叉搜索树能否实现映射”的讨论范围。 - greybeard
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
Map应该支持哪些操作？它们可以使用BST实现吗？一个BST的存储复杂度是多少？在什么条件下，使用BST比使用链表要快，比如说，这些操作会更快呢？ - greybeard