5

我正在使用 tsearch() 创建一个二进制文件。自动创建的树是否平衡。如何验证树是平衡的还是不平衡的。

4

3 回答 3

4

前段时间，我在自己实现tsearch(). 对于此 API，使用 AVL 树比使用红黑树更有意义，因为通过回调函数执行比较具有相当高的开销。AVL 树更加平衡，这意味着回调的调用频率较低。

似乎tsearch()POSIX 中的定义不需要任何平衡，因此很遗憾您不能假设这些函数执行良好。我在查看一些现有实现时观察到的情况：

  • glibc 将其实现为红黑树。
  • musl 将其实现为 AVL 树，但在 2015-12-08 之前，它包含一个导致tdelete()树不平衡的错误。
  • Solaris 和 BSD 似乎都共享相同的实现，根本不使用任何平衡。
  • FreeBSD 11.0 将不再使用不平衡的实现，因为它现在使用我编写的实现。FreeBSD 11.0 应该会在今年晚些时候发布。
于 2016-06-14T20:27:44.313 回答
2

你可以通过调用tsearch一个有序的值列表来验证，然后调用twalk，提供一个打印出树深度的动作。如果没有发生树排序，那么有序插入将创建一个列表而不是树，并且您将输出升序的深度值。

void print_depth( const void *nodep, const VISIT which, const int depth )
{
    if( which == preorder || which == leaf ) printf( "%d\n", depth );
}

twalk( root, print_depth );
于 2013-11-11T22:30:06.097 回答
0

Paddy 的回答解释了如何验证要平衡的树，但没有回答树是否平衡的问题。

我按照 Paddy 的建议做了，对我来说答案是肯定的，它是平衡的（我在 Fedora 上运行 GCC 5.1.1，Glibc 2.21）

（我不确定这是否也适用于操作系统、编译器和标准库的不同组合。如果有人在他们的系统上尝试不同的答案，请在此处添加答案！）

于 2015-12-07T14:44:49.480 回答