知识卡片

操作参考卡 · 5654.d.1.e.4.q · 生成模型:未记录

搜索树接口区分隐藏与交还

理解等级:中级

本章bistree_insert(BisTree,const void)以0表示实际插入或恢复隐藏位置,1表示键已可见而未插入,-1表示失败。bistree_lookup(BisTree*,void**)成功0并交回实际应用数据地址,未找到或目标隐藏则-1。实际头文件/实现使用非const树参数,与接口表原型的const不同。

bistree_remove(BisTree,const void)只标记隐藏,成功0、找不到-1,不交还数据地址,不释放数据,不减少结构size。即使逻辑上查不到,数据仍须有效,最终销毁或同键替换时可能再按回调释放。

bistree_init接受三路compare:小于负数、相等0、大于正数;这与集合/哈希的相等谓词非零真不同。02866把compare返回写成void是原型错误,实际02877及实现为int,才能决定搜索方向。

162和02886 bistree_init先bitree_init(tree,destroy),再tree->compare=compare;基本init本来不初始化compare,此处补上。函数返回void,固定状态初始化为O(1)。

166及02885–02886 helper lookup到NULL返回-1,比较后递归一侧;相等且hidden为0时*data=AvlNode.data并返回0,隐藏则-1。返回的是存储的应用对象地址,不是AvlNode包装本身,也不是包装中data字段的地址。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      bistree_remove 返回值 如果移除操作成功,返回0;否则返回-1。 描述 在由参数tree所指定的二叉搜索树中移除数据同参数data相吻合的结点。实际上,该操作仅仅只执行一种惰性移除,即该结点只是简单地标记为隐藏。因此,并不会返回指向结点数据的指针。更进一步的是,树中的数据就算被移除了也

    • · 查看原书依据

      显式地将compare成员设置为指定的比较函数,因为该成员在二叉树中并没有使用到,因此bitree_init并不能初始化该成员。 bistree_init的时间复杂度同bitree_init一样,都是O(1)。

    • · 查看原书依据

      AvlNode结构体中数据域成员的指针(见示例9-5)。该操作通过递归的方式调用lookup,从根结点开始逐层降低遍历树的结点,直到找到目标结点为止。在每个层级上,我们首先检查是否到达分支的边缘。如果我们处于分支的边缘则表示我们要找的结点不存在。否则,我们要么移动到左子结点,要么移动到右子结点,移动

    参考来源

    - 位置:《算法精解:C语言描述》第9章《二叉搜索树的接口定义》(spine1298;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1265.html;u159-ch09-018)。 - 结论依据:159全部六接口、02866–02871原型完整实读,02877头文件和02885–02887实际lookup/hide/公开入口核对签名及返回;未运行。 - 原始内容:bistree_remove 返回值 如果移除操作成功,返回0;否则返回-1。 描述 在由参数tree所指定的二叉搜索树中移除数据同参数data相吻合的结点。实际上,该操作仅仅只执行一种惰性移除,即该结点只是简单地标记为隐藏。因此,并不会返回指向结点数据的指针。更进一步的是,树中的数据就算被移除了也 - 位置:《算法精解:C语言描述》第9章《bistree_init》(spine1300;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1267.html;u162-ch09-018)。 - 结论依据:162和02886 bistree_init先bitree_init(tree,destroy),再tree->compare=compare;基本init本来不初始化compare,此处补上。函数返回void,固定状态初始化为O(1)。 - 原始内容:显式地将compare成员设置为指定的比较函数,因为该成员在二叉树中并没有使用到,因此bitree_init并不能初始化该成员。 bistree_init的时间复杂度同bitree_init一样,都是O(1)。 - 位置:《算法精解:C语言描述》第9章《bistree_lookup》(spine1304;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1271.html;u166-ch09-018)。 - 结论依据:166及02885–02886 helper lookup到NULL返回-1,比较后递归一侧;相等且hidden为0时*data=AvlNode.data并返回0,隐藏则-1。返回的是存储的应用对象地址,不是AvlNode包装本身,也不是包装中data字段的地址。 - 原始内容:AvlNode结构体中数据域成员的指针(见示例9-5)。该操作通过递归的方式调用lookup,从根结点开始逐层降低遍历树的结点,直到找到目标结点为止。在每个层级上,我们首先检查是否到达分支的边缘。如果我们处于分支的边缘则表示我们要找的结点不存在。否则,我们要么移动到左子结点,要么移动到右子结点,移动