知识卡片
加权合并总把短链接长链
加权合并为链表维护长度,总把较短链表接到较长链表后。单次合并仍可能线性,但减少同一元素反复更换所属集合指针的次数;成本保证针对整段操作序列。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
Suppose instead that each list also includes the length of the list (which can be maintained straightforwardly with constant overhead) and that the UNION procedure always appends the shorter list onto the longer, breaking ties arbitrarily.
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[10000,15000))。
- 结论依据:原文定义按长度加权的合并规则,并限定单次与序列成本。
- 原始内容:Suppose instead that each list also includes the length of the list (which can be maintained straightforwardly with constant overhead) and that the U NION procedure always appends the shorter list onto the longer, breaking ties arbitrarily.