知识卡片

结构图卡 · 5654.d.1.e.4.u · 生成模型:未记录

搜索节点在通用树外包一层

理解等级:中级

BisTree通过typedef BiTree BisTree复用树容器,但每个BiTreeNode.data实际指向AvlNode包装,再由包装的data指向应用数据。hidden保存逻辑可见性,factor保存平衡状态;左右链接仍在外层BiTreeNode中。

结构图:

classDiagram
class BiTree
class BisTree["BisTree(BiTree别名)"]
class BiTreeNode {
 void* data
 BiTreeNode* left
 BiTreeNode* right
}
class AvlNode {
 void* data
 int hidden
 int factor
}
class SearchAPI["搜索树公开函数组(非类型)"] {
 bistree_init(BisTree* tree, compare, destroy) void
 bistree_destroy(BisTree* tree) void
 bistree_insert(BisTree* tree, const void* data) int
 bistree_remove(BisTree* tree, const void* data) int
 bistree_lookup(BisTree* tree, void** data) int
}
BisTree ..> BiTree : 同一类型另名,非继承
BiTree --> BiTreeNode : root
BiTreeNode --> AvlNode : data指向包装
AvlNode --> 应用数据 : data借存用户对象地址
SearchAPI ..> BisTree : 维护键序与AVL状态

compare/destroy参数是与BiTree字段相同的函数指针简写。基本bitree_data返回的是包装地址,搜索lookup才返回应用地址;直接对BisTree调用基本树销毁或任意插入,并不自动履行两层数据与平衡契约。

163及02881–02882 destroy_left/destroy_right使用正确if/else定位根或孩子,先递归清孩子,再对AvlNode.data调用tree->destroy,随后free包装、free外层节点、置链接NULL、size–。它们没有沿用基本树rem函数漏else的那一缺陷。02886公开destroy从根调用后清空容器,连隐藏节点的数据也会释放。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      AvlNode包含3个成员:data是存储在结点中的数据,hidden用来标识结点是否已经移除的一个成员,factor则代表该结点的平衡因子。本节给出的实现使用标识符来标识平衡因子可能的值。示例9-4将AVL_LEFT_HEAVY定义为1,AVL_BALANCED定义为0,AVL_RGT_HEAVY

    • · 查看原书依据

      两个额外的辅助函数:destroy_left和destroy_right。这两个函数按照递归的方式销毁某个结点下方的左右子树。它们的工作方式同前文定义过的bitree_rem_left和bitree_rem_right类似。针对二叉搜索树,需要单独的析构函数来销毁AvlNode中数据成员所引用的空间

    参考来源

    - 位置:《算法精解:C语言描述》第9章《AVL树的旋转》(spine1299;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1266.html;u161-ch09-022)。 - 结论依据:161包装字段/别名说明、02876–02877完整头文件及02881–02886实现实读;纠正正文自指别名笔误,实际typedef BiTree BisTree,不画语言继承。 - 原始内容:AvlNode包含3个成员:data是存储在结点中的数据,hidden用来标识结点是否已经移除的一个成员,factor则代表该结点的平衡因子。本节给出的实现使用标识符来标识平衡因子可能的值。示例9-4将AVL_LEFT_HEAVY定义为1,AVL_BALANCED定义为0,AVL_RGT_HEAVY - 位置:《算法精解:C语言描述》第9章《bistree_destroy》(spine1301;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1268.html;u163-ch09-022)。 - 结论依据:163及02881–02882 destroy_left/destroy_right使用正确if/else定位根或孩子,先递归清孩子,再对AvlNode.data调用tree->destroy,随后free包装、free外层节点、置链接NULL、size--。它们没有沿用基本树rem函数漏else的那一缺陷。02886公开destroy从根调用后清空容器,连隐藏节点的数据也会释放。 - 原始内容:两个额外的辅助函数:destroy_left和destroy_right。这两个函数按照递归的方式销毁某个结点下方的左右子树。它们的工作方式同前文定义过的bitree_rem_left和bitree_rem_right类似。针对二叉搜索树,需要单独的析构函数来销毁AvlNode中数据成员所引用的空间