首页 文章

二进制堆与二叉树C.

提问于
浏览
1

我对二进制搜索树和二进制堆上的find_min操作的运行时有些困惑 . 我知道在二进制堆中返回min是一个O(1)操作 . 我也理解为什么理论上,返回二进制搜索树中的最小元素是O(log(N))操作 . 令我惊讶的是,当我读到C STL中的数据结构时,文档声明将迭代器返回到映射中的第一个元素(与返回最小元素相同)是在恒定时间内发生的!难道这不能以对数时间返回吗?我需要有人帮助我理解C在引擎盖下做什么,以便在恒定时间内返回 . 因为那时,在C中真正使用二进制堆是没有意义的,因此 Map 数据结构将支持在常量时间中检索min和max,在O(log(N))中删除和搜索并保持所有内容的排序 . 这意味着数据结构具有BST和二进制堆的优点,所有这些都捆绑在一起!

我和一个面试官(不是真正的争论)就这个问题进行了争论,但我试图向他解释,在C中,C中的 Map 中返回min和max(这是一个自 balancer 的二叉搜索树)是在恒定的时间内发生的 . 他感到困惑,不停地说我错了,二进制堆是要走的路 . 澄清将非常感激

3 回答

  • 2

    通过在 Map 的头部结构中存储对RB树的最左侧和最右侧节点的引用来实现最小值和最大值的恒定时间查找 . 这是一个注释f rom the source code of the RB-tree,一个模板,从中导出了 std::setstd::mapstd::multimap 的实现:

    Headers 单元不仅与根连接,而且还与树的最左边节点相连,以启用常量时间begin()和树的最右边节点,以便在与通用一起使用时启用线性时间性能设置算法(set_union等)

    这里的权衡是需要维护这些指针,因此插入和删除操作将有另一个“内务操作” . 但是,插入和删除已经在对数时间内完成,因此维护这些指针没有额外的渐近成本 .

  • -1

    至少在典型的实现中, std::set (和 std::map )将实现为线程二进制树1 . 换句话说,每个节点不仅包含指向其(最多)两个子节点的指针,还包含按顺序指向上一节点和下一节点的指针 . 然后, set 类本身不仅指向树的根,还指向节点的线程列表的开头和结尾 .

    要按键搜索节点,使用普通的二进制指针 . 要按顺序遍历树,使用线程指针 .

    与二进制堆相比,这确实有许多缺点 . 最明显的是它为每个数据项存储了四个指针,其中二进制堆只能存储数据,没有指针(节点之间的关系隐含在数据的位置) . 在极端情况下(例如, std::set<char> ),这可能最终会为指针使用比实际关注的数据更多的存储空间(例如,在64位系统上,最终可能会得到每个64位的4个指针) ,存储每个8位字符) . 这可能导致缓存利用率低下(反过来)往往会损害速度 .

    此外,每个节点通常将单独分配,这可以非常严重地减少引用的局部性,再次损害缓存使用并进一步降低速度 .

    因此,即使线程树可以找到最小值或最大值,或者遍历O(1)中的下一个或上一个节点,并在O(log N)中搜索任何给定项目,常量也可能大大高于与堆相同 . 根据所存储项目的大小,所使用的总存储量也可能远大于堆积(最坏的情况显然是当每个节点中只存储少量数据时) .


    1.应用了一些 balancer 算法 - 通常是红黑色,但有时是AVL树或B树 . 可以使用任何数量的其他 balancer 树(例如,α balancer 树,k邻域树,二叉b树,一般 balancer 树) .

  • 6

    我不是 Map 专家,但返回 Map 的第一个元素将被视为各种各样的“根” . 总有一个指向它的指针,所以它的查找时间是即时的 . 这同样适用一个BSTree,因为它显然有一个根节点,然后有2个节点关闭它等等(顺便说一句,我会用AVL树来研究,因为最坏情况下的查找时间比BSTree好得多) .

    O(log(N))通常仅用于估计最坏情况 . 因此,如果你有一个完全不 balancer 的BSTree,你实际上会有O(N),所以如果你搜索最后一个节点,你必须对每个节点进行比较 .

    虽然 Map 与自 balancer 树不同,但我不太确定你的最后一句话,那些被称为AVL树(或者就是我所教的) . Map 使用“键”以特定方式组织对象 . 通过将数据序列化为数字来找到密钥,并且该数字大部分放在列表中 .

相关问题