tsearch()创建的树是否是平衡二叉树？

Question

我正在使用tsearch()创建二叉树。这个树会自动平衡吗？如何确定这个树是平衡的还是不平衡的。

- Priyatham51

---

创建一个简单的例子并查看树 - 你看到了什么？有一个早期的答案回答了一般问题“这棵树是否平衡”在这里。将其应用于您的树，您就会得到答案。 - Floris

Answer 1

我曾在制作 自己的tsearch()实现 时研究过这个问题。对于这个API，使用AVL树比使用红黑树更有意义，因为通过回调函数进行比较具有相当高的开销。AVL树更平衡，这意味着回调函数被调用的频率较低。

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

• glibc将其实现为红黑树。
• musl将其实现为AVL树，但直到2015-12-08它都存在一个错误，导致tdelete()使树失去平衡。
• Solaris和BSD都似乎共享同一个没有使用任何平衡的实现。
• FreeBSD 11.0将不再使用不平衡的实现，因为它现在使用了我编写的实现。FreeBSD 11.0预计将在今年晚些时候发布。

- Ed Schouten

---

有趣的是，你的实现似乎与POSIX根本不兼容，因为它将根声明为posix_tnode *而不是POSIX所规定的void *。 - Chris Dodd

那本来会非常有趣的，克里斯，但只有这是真实的时候才会如此。只需在网络上搜索posix_tnode，您就会发现其中一个热门结果是我提交给POSIX添加此数据类型的问题。它将成为第八版的一部分。它已经在最新的草案中了。因为'posix_*'是POSIX兼容系统上的保留命名空间，所以我决定无条件地声明它。为了简化实现过程，我将其声明为结构类型，而不是'void'，但仅作为tsearch.c / tdelete.c / ...编译单元的一部分。 - Ed Schouten

这似乎是规范中一个不好的（破坏向后兼容性）更改，除非它需要被typedef为void。主要问题是你的代码不能作为tsearch的即插即用替代品，因为它会破坏大多数使用它的程序（如果posix_tnode不是void，则无法隐式转换void **为posix_tnode **）。 - Chris Dodd

这就是它应该被定义的方式：作为 void。它仅仅是为了提高签名的可读性而添加的。我并没有声称我的实现是一个即插即用的替换品；它只是一个实现。 - Ed Schouten

Answer 2

你可以通过在有序值列表上调用tsearch，然后调用twalk来验证，提供一个打印树深度的action。如果没有进行树排序，则有序插入将创建一个列表而不是一棵树，您将输出升序深度值。

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 );

- paddy

Answer 3

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

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

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

- Dacav