知识卡片
有序集合连接与分裂
连接与分裂是一对有序集合变换:
- 连接要求左集合所有键小于分界键、右集合所有键大于它,结果包含三者;
- 分裂要求分界键属于原集合,移除它后按大小划成两组。
第18章仅将2-3-4树的实现和时间界列作练习,不可把目标界当成已证结论。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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 .