知识卡片
持久树只复制修改路径
持久集合保存每个版本的根。
插入时复制从根到目标位置的受影响节点,并与旧版本共享未变子树,避免整树复制;本章问题以无父指针节点为前提,完整插入、删除复杂度仍是题目要求论证的部分。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
Thus, you copy only part of the tree and share some of the nodes with the original tree
参考来源
- 位置:《算法导论(第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