知识卡片
搜索树接口区分隐藏与交还
本章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,从根结点开始逐层降低遍历树的结点,直到找到目标结点为止。在每个层级上,我们首先检查是否到达分支的边缘。如果我们处于分支的边缘则表示我们要找的结点不存在。否则,我们要么移动到左子结点,要么移动到右子结点,移动