知识卡片

普通读书笔记卡 · 5654.d.1.e.4.x · 生成模型:未记录

惰性删除保留结构和数据

理解等级:中级

惰性删除只把匹配节点hidden设为1,查询把它当不存在,实际节点、键数据与左右链接仍在,所以无需因这次删除调整高度。bistree_size仍统计所有结构节点,不能当作当前可见成员数。

再次插入同键时可复用原位置:按回调销毁旧数据、换入新数据、hidden=0。大量隐藏项会长期占用空间,也让按结构规模计算的路径成本不同于仅按可见项数量估计;本实现没有自动物理回收/重建。

实际hide找到相等键就写hidden=1并返回0,未区分它是否原已隐藏,所以重复remove仍可能返回0。这个返回含义是找到了相应结构位置并设置隐藏,并不证明本次可见成员数量实际减少。

167及02877宏bistree_size(tree)=((tree)->size),只是字段读取;基本bitree插入新物理节点才增size,hide和隐藏同键恢复不改它。02879–02887全部实现已读,销毁包含隐藏对象,不能因其查询不可见而提前释放键。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      惰性移除。即只是将结点隐藏起来而并不是真正移除它们。要隐藏一个结点,将AvlNode结构中的hidden成员设置为1。如果稍后插入同样的数据,只需简单地将结点的hidden成员再次设置为0(见bistree_insert)。在实践中,相对于插入的结点数目,如果并不期望需要进行许多移除操作的话,这种方

    • · 查看原书依据

      size成员即可。 bistree_size的时间复杂度是O(1),因为访问结构体成员的操作能够在恒定的时间内完成。 示例9-5:二叉搜索树抽象数据类型的实现

    参考来源

    - 位置:《算法精解:C语言描述》第9章《bistree_remove》(spine1303;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1270.html;u165-ch09-025)。 - 结论依据:165完整解释、159不交还数据/size不减、02885完整hide和02884恢复代码实读;明确重复隐藏实际分支,未执行。 - 原始内容:惰性移除。即只是将结点隐藏起来而并不是真正移除它们。要隐藏一个结点,将AvlNode结构中的hidden成员设置为1。如果稍后插入同样的数据,只需简单地将结点的hidden成员再次设置为0(见bistree_insert)。在实践中,相对于插入的结点数目,如果并不期望需要进行许多移除操作的话,这种方 - 位置:《算法精解:C语言描述》第9章《bistree_size》(spine1305;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1272.html;u167-ch09-025)。 - 结论依据:167及02877宏bistree_size(tree)=((tree)->size),只是字段读取;基本bitree插入新物理节点才增size,hide和隐藏同键恢复不改它。02879–02887全部实现已读,销毁包含隐藏对象,不能因其查询不可见而提前释放键。 - 原始内容:size成员即可。 bistree_size的时间复杂度是O(1),因为访问结构体成员的操作能够在恒定的时间内完成。 示例9-5:二叉搜索树抽象数据类型的实现