当老师问到“二叉搜索树具有二叉搜索树属性意味着什么,这使其适合实现Map”时,我对BST和Map之间的关系感到困惑。是否有人能为我解释一下?谢谢。
当老师问到“二叉搜索树具有二叉搜索树属性意味着什么,这使其适合实现Map”时,我对BST和Map之间的关系感到困惑。是否有人能为我解释一下?谢谢。
地图是一种关联容器,其中的键不是强制性整数(与数组相反,在数组中,键始终是数字)。
现在您希望存储多个 key,value
对,并且希望能够高效地按其键查找值或高效地添加对或删除对以及进行其他操作。
二叉搜索树是一种数据结构,其所有操作的平均时间复杂度为O(log n)
。这意味着您可以高效地搜索树的特定节点(该节点将具有自己的键和值)。
这就是使用BST实现地图的重点,从而获得某些操作方面高效的结构,但这不是实现地图的唯一方法(考虑哈希表)。
Map
应该支持哪些操作?它们可以使用BST
实现吗?一个BST
的存储复杂度是多少?在什么条件下,使用BST
比使用链表要快,比如说,这些操作会更快呢? - greybeard