← 返回刚才阅读的位置

知识卡片

问题卡 · 5654.d.1.e.4.w · 生成模型:未记录

新增包装字段必须全部初始化

理解等级:中级

本章insert在空树根分支为AvlNode写factor、hidden=0、data;但非空树的左/右新孩子分支只写factor和data,漏了hidden。随后lookup、hide和同键insert都会读取hidden,未初始化的值不能可靠表达可见性。

因此正常新增孩子也可能在查询或重复判断中出现不符合接口的结果。修正方向是在每一个新包装分支都明确初始化hidden=0,并保持同一新建对象规则,而不能只因根分支做过一次就当所有节点都有初值。

另有失败路径:包装malloc成功后,bitree_ins_left/right仍会分配外层节点;若后者失败,原insert直接返回-1而没有释放新包装。数据归属与两次分配的清理责任要分别处理。此处准确记录原代码问题,未运行或声称修复通过。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      动态分配一个AvlNode结构体,并将其插入树中,作为当前结点的子结点。如果待插入结点的数据恰好与某个隐藏结点的数据一致(由于执行了移除操作,使结点成为隐藏的,但并未真正移除),就销毁当前结点中的数据,将新的数据插入原来的位置上,并标识该结点不再为隐藏的。在这种情况下,不需要重新平衡树。 除此之外,

    参考来源

    - 位置:《算法精解:C语言描述》第9章《bistree_insert》(spine1302;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1269.html;u164-ch09-024)。 - 结论依据:164新增包装说明与02882根分支、02883左右新增分支、02884后续hidden读取逐项实读;比较三处分支字段写入,结合基本插入第二次malloc定位失败泄漏。 - 原始内容:动态分配一个AvlNode结构体,并将其插入树中,作为当前结点的子结点。如果待插入结点的数据恰好与某个隐藏结点的数据一致(由于执行了移除操作,使结点成为隐藏的,但并未真正移除),就销毁当前结点中的数据,将新的数据插入原来的位置上,并标识该结点不再为隐藏的。在这种情况下,不需要重新平衡树。 除此之外,