当老师问“二叉树具有二叉搜索树属性意味着什么以及为什么这使得它适合实现 Map”时,我对 BST 和 Map 之间的关系感到困惑。谁能为我解释一下?谢谢。
最佳答案
映射是一种关联容器,其中键不是强制整数(例如,与键始终为数字的数组相反)。
现在您想要存储多对key,value
并且您希望能够通过其键有效地查找值,或者有效地添加对,或者有效地删除对,或者您正在执行的任何操作做最多。
二叉搜索树是一种数据结构,对于所有操作的平均情况,指定复杂度为 O(log n)
。这意味着您能够以高效的方式搜索树的特定节点(它将有自己的键和值)。
这就是重点,您可以在底层使用 BST 来实现一个映射,以获得一个在某些方面对许多操作都有效的结构,但这不是实现映射的唯一方法(想想 HashMap )。
关于algorithm - 二叉搜索树可以实现一个Map吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34549131/