知识卡片

普通读书笔记卡 · 1292.f.1.a.6

持久树只复制修改路径

理解等级:中级

持久集合保存每个版本的根。

插入时复制从根到目标位置的受影响节点,并与旧版本共享未变子树,避免整树复制;本章问题以无父指针节点为前提,完整插入、删除复杂度仍是题目要求论证的部分。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 13 章问题 13-1(`OEBPS/chapter013.xhtml`,文本字符 [45000, 50000);图 13.8、Art_P446)。 - 结论依据:问题 13-1 的图 13.8 在插入键 5 时复制受影响的根到插入点路径,其他子树与旧版本共享;题设规定节点无父指针,插删复杂度留作问题证明。 - 原始内容:Thus, you copy only part of the tree and share some of the nodes with the original tree