知识卡片

普通读书笔记卡 · 3633.a.9

有序集合连接与分裂

理解等级:中级

连接与分裂是一对有序集合变换:

  • 连接要求左集合所有键小于分界键、右集合所有键大于它,结果包含三者;
  • 分裂要求分界键属于原集合,移除它后按大小划成两组。

第18章仅将2-3-4树的实现和时间界列作练习,不可把目标界当成已证结论。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第18章 B树 · 查看原书依据

      The join operation takes two dynamic sets S′ and S″ and an element x such that x′.key < x.key < x″.key for any x′ ∈ S′ and x″ ∈ S″. It returns a set S = S′ ∪ {x} ∪ S″. The split operation is like an “inverse” join: given a dynamic set S and an element x ∈ S, it creates a set S′ that consists of all elements in S − {x} whose keys are less than x.key and another set S″ that consists of all elements in S − {x} whose keys are greater than x.key.

    参考来源

    - 位置:《算法导论(第4版)》第18章《B树》问题18-2(OEBPS/chapter018.xhtml,文本字符[35000,40000))。 - 结论依据:题设将join与split定义为围绕分界键的逆向集合变换,并要求键互异;2-3-4树实现及复杂度为待证明的练习任务。 - 原始内容:The join operation takes two dynamic sets S ′ and S ″ and an element x such that x ′. key < x . key < x ″. key for any x ′ ∈ S ′ and x ″ ∈ S ″. It returns a set S = S ′ ∪ { x } ∪ S ″. The split operation is like an “inverse” join: given a dynamic set S and an element x ∈ S , it creates a set S ′ that consists of all elements in S − { x } whose keys are less than x . key and another set S ″ that consists of all elements in S − { x } whose keys are greater than x . key .