← 返回刚才阅读的位置

知识卡片

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

附加链接用空间换访问路径

理解等级:中级

树节点增加父指针可支持从子往上走,增加兄弟链接可在同层相关节点间移动。它们不会改变基本父子层次,却能让原本需绕行的访问更直接;代价是额外存储与变更时更多链接维护。

本章用B+树叶节点之间的链接说明:先按搜索树找到范围起点,再沿叶层链接读取之前/之后的相关记录,从而兼顾按键定位和顺序访问。并非所有普通树节点都天然具有这些附加指针,前文BiTreeNode实际就没有父指针。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      维护了从子结点指回它们父结点的指针。还有一些树中在兄弟结点之间也维护互相关联的指针。为什么要这么做呢? 答:一般来说,维护附加的指针为遍历树时提供了更加灵活的方式。比如,维护父结点与子结点之间的指针使我们既能够自上而下也能够自下而上遍历这棵树。维护兄弟结点之间的指针,则使我们能够方便地遍历所有子结点

    参考来源

    - 位置:《算法精解:C语言描述》第9章《问与答》(spine1306;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1273.html;u168-ch09-026)。 - 结论依据:168首问完整问答实读,保留父/兄弟链接和B+叶层顺序链用途,未添加BiTreeNode未定义字段。 - 原始内容:维护了从子结点指回它们父结点的指针。还有一些树中在兄弟结点之间也维护互相关联的指针。为什么要这么做呢? 答:一般来说,维护附加的指针为遍历树时提供了更加灵活的方式。比如,维护父结点与子结点之间的指针使我们既能够自上而下也能够自下而上遍历这棵树。维护兄弟结点之间的指针,则使我们能够方便地遍历所有子结点