通过 POSIX tdelete() 访问节点数据

Question

POSIX 二叉树函数 的联机帮助页包括以下语句：

tdelete() 返回指向已删除项目的父级的指针，如果未找到该项目，则返回 NULL。

tdelete() 释放树中节点所需的内存。用户 负责释放相应数据的内存。

这意味着无法通过 tdelete() 调用访问给定键的节点数据。需要调用 tfind() （而不是 tsearch() 以免添加给定的键），销毁节点数据，然后调用 < code>tdelete() 使用相同的键从二叉树中删除节点。

我的解释正确吗？有什么办法可以解决我认为这种方法的局限性吗？

1. 如果键是堆分配的，则在删除节点之前无法释放它（或使其对正在使用的比较函数无用）。这需要调用 tfind() 获取指向数据的指针，调用 tdelete() 删除节点，然后销毁从 tfind() 检索到的数据调用。
2. 需要两次查找才能删除节点并销毁其包含的数据。

Answer 1

马特，我认为你的解释是正确的。对于单独删除元素来说，这似乎是不可避免的。 （但无论如何，对于 \Omega \log N 成本的操作来说，它只是 2 的一个因素；）

我很长一段时间没有使用这些函数，但通过旧代码，看起来你可以避免部分开销，如果你通过使用两次 twalk 调用一次性销毁树（如果这是您的情况）：

1. 计算其中元素的数量 N
   通过适当调用 twalk 为您的树
2. 分配一个大小为 N 的数组
   指向树项的指针
3. 通过第二次 twalk 填充此数组
   穿过树
4. 穿过这个
   数组并首先对每个树节点
   删除其数据，然后删除节点
   如果您确实需要这样的东西，

您可以在我们的库中找到这些调用的线程安全 C++ 封装 parXXL 在目录 par/sys 中。

Answer 2

我以前从未使用过这组功能，但你似乎是正确的。但是，我会尝试使用从 tfind() 返回的指针作为 tdelete() 的 rootp 参数。这将使第二次搜索基本上成为无操作。 AFAICT，数据结构允许将任何节点视为根，因此您可以找到该节点，然后从以您找到的节点为根的子树中删除它。

Answer 3

和 D.Shawley 一样，我以前从未使用过这些函数，所以我编写了一个泄漏内存的小测试程序。

#include <search.h>
#include <stdio.h>
#include <stdlib.h>

int fx(const void *a, const void *b) {
  if (*(int*)a < *(int*)b) return -1;
  return (*(int*)a > *(int*)b);
}

int main(void) {
  int i, *elem;
  void *root = NULL, *val;

  for (i = 0; i < 10; i++) {
    elem = malloc(sizeof *elem); /* LEAK, leak, leak */
    *elem = i/2;
    val = tsearch(elem, &root, fx); /* assume all OK */
    printf("i: %d; elem: %p (%d); val: %p (%x)\n",
           i, (void*)elem, *elem, val, *(int*)val);
  }

  for (i = -1; i < 6; i++) {
    val = tfind(&i, &root, fx);
    printf("i: %d; ", i);
    if (val) {
      printf("@%p (%x)\n", val, *(int*)val);
    } else {
      printf("NOT FOUND\n");
    }
  }

  return 0;
}

运行它输出

i: 0; elem: 0xcb8010 (0); val: 0xcb8030 (cb8010)
i: 1; elem: 0xcb8060 (0); val: 0xcb8030 (cb8010)
i: 2; elem: 0xcb8080 (1); val: 0xcb80a0 (cb8080)
i: 3; elem: 0xcb80d0 (1); val: 0xcb80a0 (cb8080)
i: 4; elem: 0xcb80f0 (2); val: 0xcb8110 (cb80f0)
i: 5; elem: 0xcb8140 (2); val: 0xcb8110 (cb80f0)
i: 6; elem: 0xcb8160 (3); val: 0xcb8180 (cb8160)
i: 7; elem: 0xcb81b0 (3); val: 0xcb8180 (cb8160)
i: 8; elem: 0xcb81d0 (4); val: 0xcb81f0 (cb81d0)
i: 9; elem: 0xcb8220 (4); val: 0xcb81f0 (cb81d0)
i: -1; NOT FOUND
i: 0; @0xcb8030 (cb8010)
i: 1; @0xcb80a0 (cb8080)
i: 2; @0xcb8110 (cb80f0)
i: 3; @0xcb8180 (cb8160)
i: 4; @0xcb81f0 (cb81d0)
i: 5; NOT FOUND

显然“二叉树内部”的值是指向数据的指针的副本。副本由 函数管理，数据应由程序管理。

内存0xcb8030应该通过调用tdelete()来释放，相应的0xcb8010（elem值为0）应该由程序释放（以及之前丢失的0xcb8060）。