2

POSIX 二叉树函数的手册页包括以下语句：

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

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

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

我是否正确解释了这一点？有没有办法解决我认为这种方法的局限性？

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

3 回答 3

2

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

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

  1. N通过适当的调用计算树中的元素数量twalk
  2. N分配一个指向树项的指针大小的数组
  3. twalk 通过树将该数组填充一秒钟
  4. 遍历这个数组，对于每个树节点，首先删除其数据，然后删除节点本身

如果你真的需要这样的东西，你可以在目录中的parXXL库中找到这些调用的线程安全 C++ 封装par/sys。

于 2010-09-11T16:01:29.850 回答
1

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

于 2010-09-11T14:36:12.723 回答
0

和 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;
}

运行它输出

我：0；元素：0xcb8010（0）；值：0xcb8030 (cb8010)
我：1；元素：0xcb8060（0）；值：0xcb8030 (cb8010)
我：2；元素：0xcb8080（1）；值：0xcb80a0 (cb8080)
我：3；元素：0xcb80d0（1）；值：0xcb80a0 (cb8080)
我：4；元素：0xcb80f0（2）；值：0xcb8110 (cb80f0)
我：5；元素：0xcb8140（2）；值：0xcb8110 (cb80f0)
我：6；元素：0xcb8160（3）；值：0xcb8180 (cb8160)
我：7；元素：0xcb81b0（3）；值：0xcb8180 (cb8160)
我：8；元素：0xcb81d0（4）；值：0xcb81f0 (cb81d0)
我：9；元素：0xcb8220（4）；值：0xcb81f0 (cb81d0)
我：-1；未找到
我：0；@0xcb8030 (cb8010)
我：1；@0xcb80a0 (cb8080)
我：2；@0xcb8110 (cb80f0)
我：3；@0xcb8180 (cb8160)
我：4；@0xcb81f0 (cb81d0)
我：5；未找到

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

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

于 2010-09-11T15:24:00.797 回答