Is the tree created by tsearch() balanced tree?

Question

I am creating a binary using tsearch(). Is the tree created balanced automatically. How can I verify the tree is balanced or unbalanced.

Answer 1

I looked into this some time ago while working on my own implementation of tsearch(). For this API, it makes more sense to use an AVL tree than a Red-Black tree, as performing comparisons through a callback function has a pretty high overhead. AVL trees are more optimally balanced, meaning that the callback is invoked less frequently.

It seems that the definition of tsearch() in POSIX does not require any balancing, so unfortunately you cannot assume that these functions perform well. What I observed while looking at some existing implementations:

• glibc implements it as a Red-Black tree.
• musl implements it as an AVL tree, but until 2015-12-08 it contained a bug that caused tdelete() to make the tree unbalanced.
• Solaris and the BSDs all seem to share the same implementation that doesn't use any balancing at all.
• FreeBSD 11.0 will no longer use the unbalanced implementation, as it now uses the implementation that I wrote. FreeBSD 11.0 should be released later this year.