草庐IT

c++ - std::map已知位置删除摊余的复杂度和红黑树重新着色的次数

coder 2024-02-04 原文

std::map::erase(iterator)的复杂度以O(1)摊销(例如，参见here)。尽管标准库没有规定实现方式，但事实上，这意味着将红黑树所需的重新平衡操作数摊销为O(1)。实际上，关于红黑树的Wikipedia条目seems to confirm this:

Restoring the red–black properties requires a small number (O(log n) or amortized O(1)) of color changes (which are very quick in practice) and no more than three tree rotations (two for insertion).



但似乎没有链接(我在其他地方找不到)。

由于转数是恒定的，因此摊销取决于节点根路径上所需的重新着色数量。尽管平衡树中的大多数节点都朝向树的底部(因此平均路径是对数的)，但显然它是摊销的O(1)，这令人惊讶且有趣。如何证明摊销的固定成本？

最佳答案

我将在此答案中假设您熟悉摊销分析，并且熟悉银行家的方法。我还要假设您知道红黑树不变式。

对于一些小的常数k，简短的答案是，将k个硬币放在每个没有一个红色 child 的黑色节点上。

请注意，红黑树中有多种不同的删除算法。用迭代器擦除显然需要自下而上的算法之一。此处的分析假设该算法的执行大致如下:

  • 向上遍历，直到找到一个黑色节点。这总是可能的，因为根是黑色的，并且由于红色节点不能有红色的子节点，所以它的跳数绝不会超过两跳。
  • 在O(1)时间内对根于该黑色节点的子树执行“修复”操作。如果修复程序降低了子树的高度或将根的颜色从黑色更改为红色，请向根再走一步，然后返回到＃1。

    • 需要做一些工作才能看到＃2是可能的。实际上，这种复杂性是Sedgewick左倾红黑树的动机之一。这主要是枚举所有情况，进行一次或两次轮换，然后仔细检查您是否未违反任何不变性的问题。

    fixup操作的一个变体(如果您已经有了另一个有效的变体，这很难找到)在遍历树的过程中保留了两个其他不变式:
  • 当子树的高度减小1时，子树的根(a)最初有两个黑人 child (b)现在正好有一个红色 child 。
  • 子树从不将颜色从黑色更改为红色。

    • 因此，对于遍历的每个步骤，
  • 子树的根有一个或两个红色子代。我们执行O(1)工作，最多添加O(1)个硬币，然后停止
  • 我们执行O(1)工作，通过将具有两个黑色子节点的节点变成具有一个红色子节点的节点来获得O(1)硬币，并继续

    • 案例2是摊销后的免费，只要硬币数量足够大以支付案例2中的重组和重新着色费用。因此，删除的总摊销成本是我们在单个删除操作中达到案例＃1的次数，最多为一次，因为在我们执行删除操作后我们就停止了。

    虽然这涵盖了解释算术的原理，但并没有真正解释为什么删除要摊销O(1)。

    有时会教给学生有关摊销成本的一种情况是增加二进制数的情况。在最坏的情况下，成本为Ω(lg n)，但在摊销意义上，通过将恒定数量的硬币放在每个“1”数字上，成本为O(1)。

    类似地，递减是通过将恒定数量的硬币放在每个“0”数字上来摊销O(1)。但是，即使在摊销设置中，将两者混合也会使每个成本Ω(lg n)，因为摊销分析取决于所有遍历步骤，除了最后一个步骤会返还恒定数量的硬币。

    这个遍历是免费的，直到您停止为止，该主题类似于上面的红黑树分析。必须放置硬币的数字是代表将要进行的结构调整的数字。使用物理学家的方法，像这样将势能添加到每个数字的结构中。

    考虑一个不同的二进制数字表示形式，其中的数字可以是0、1，或2 (但是d_i仍然表示d_i * 2 ^ i)。这称为冗余二进制。现在，您可以将恒定数量的硬币放在所有0或2位数字上，并获得摊销的恒定时间增量和减量。原因是级联的递增或递减将0s或2s更改为1s，因此总是将硬币取回。

    因此，使用两位数，递增或递减值将分摊O(1)，但不能同时摊销，而使用三位数，都可以摊销O(1)。

    同样，插入或删除(但不能同时删除)在所有以下项中均摊销O(1):
  • 黑色节点中只能有一个红色子节点的红黑树
  • AA树
  • 2-3棵树
  • (a，2a-1)树，对于任何> 1的树

    虽然插入和删除都在红黑树，(2,4)树和(a，2a)树中对于任何a> 1进行O(1)摊销。

    • 关于c++ - std::map已知位置删除摊余的复杂度和红黑树重新着色的次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36069394/

    已知ampbr的恒定c++time-complexityerasered-black-treeamortized-analysis

    有关c++ - std::map已知位置删除摊余的复杂度和红黑树重新着色的次数的更多相关文章

    1. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

      我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

    2. ruby - 我可以使用 Ruby 从 CSV 中删除列吗？ - 2

      查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html

    3. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

      我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

    4. ruby - 我可以使用 aws-sdk-ruby 在 AWS S3 上使用事务性文件删除/上传吗？ - 2

      我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的

    5. ruby - 如何安全地删除文件？ - 2

      在Ruby中是否有Gem或安全删除文件的方法？我想避免系统上可能不存在的外部程序。“安全删除”指的是覆盖文件内容。 最佳答案 如果您使用的是*nix，一个很好的方法是使用exec/open3/open4调用shred:`shred-fxuz#{filename}`http://www.gnu.org/s/coreutils/manual/html_node/shred-invocation.html检查这个类似的帖子:Writingafileshredderinpythonorruby?

    6. ruby-on-rails - 标准化文件名的字符串，删除重音和特殊字符 - 2

      我正在尝试找到一种方法来规范化字符串以将其作为文件名传递。到目前为止我有这个:my_string.mb_chars.normalize(:kd).gsub(/[^\x00-\x7F]/n,'').downcase.gsub(/[^a-z]/,'_')但第一个问题:-字符。我猜这个方法还有更多问题。我不控制名称，名称字符串可以有重音符、空格和特殊字符。我想删除所有这些，用相应的字母('é'=>'e')替换重音符号，并将其余的替换为'_'字符。名字是这样的:“Prélèvements-常规”“健康证”...我希望它们像一个没有空格/特殊字符的文件名:“prelevements_routin

    7. ruby - 使用 `+=` 和 `send` 方法 - 2

      如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

    8. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

      HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

    9. ruby - 正则表达式在哪个位置失败？ - 2

      我需要一个非常简单的字符串验证器来显示第一个符号与所需格式不对应的位置。我想使用正则表达式，但在这种情况下，我必须找到与表达式相对应的字符串停止的位置，但我找不到可以做到这一点的方法。(这一定是一种相当简单的方法……也许没有？)例如，如果我有正则表达式:/^Q+E+R+$/带字符串:"QQQQEEE2ER"期望的结果应该是7 最佳答案 一个想法:你可以做的是标记你的模式并用可选的嵌套捕获组编写它:^(Q+(E+(R+($)?)?)?)?然后你只需要计算你获得的捕获组的数量就可以知道正则表达式引擎在模式中停止的位置，你可以确定匹配结束

    10. ruby - 如何计算 Liquid 中的变量 +1 - 2

      我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

    随机推荐