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

Question

POSIX binary tree functions 的联机帮助页包括以下语句:

tdelete() returns a pointer to the parent of the item deleted, or NULL if the item was not found.

tdelete() frees the memory required for the node in the tree. The user is responsible for freeing the memory for the corresponding data.

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

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

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

Answer 1

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

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

1. 计算 N 中元素的数量 您的树并适当调用 twalk
2. 分配一个大小为 N 的数组 指向树项的指针
3. 将此数组填充第二个 twalk 穿过树
4. 运行一下这个 数组并首先对每个树节点 删除其数据，然后删除节点 本身

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