在2个AVL节点之间搜索最大值[重复]

|                                                                                                                   这个问题已经在这里有了答案：                                                      
2019-12-31 2 条评论
分享

没有找到相关结果

    已邀请:

    田眯衅

    您需要在此组合树上执行哪些其他操作，以及它们需要哪些复杂性界限？ 如果唯一的限制是查找键范围（j，k）的最大值，则存在一个愚蠢的解决方案，可以任意多地预先计算所有这些n ^ 2最大值时间;您会将固定k的所有值存储在树中节点k中的数组中；那么您的操作将简化为查找。但是，如果您想支持插入或删除，那么复杂度将类似于O（n ^ 2）。 一个更现实的选择是存储每个子树的最大值。在任何两个节点之间最多有O（log（n））个子树，您在从根到两个键j和k的途中或在树中它们的下面遇到了所有这些树，因此将是O（ log（n））。这样，您仍然可以插入O（log（n）），但是我认为现在删除可能就是O（n），因为要恢复已删除的子树的最大值很复杂。一个条目。     
    2019-12-31 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.05958890914917