5

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

Priyatham51
  • 1,864
  • 1
  • 16
  • 24
  • Create a simple example and look at the tree - what do you see? There is an earlier answer to the general question "is this tree balanced" [here](http://stackoverflow.com/questions/742844/how-to-determine-if-binary-tree-is-balanced). Apply it to your tree and you will have your answer. – Floris Nov 11 '13 at 22:22

3 Answers3

4

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.
Ed Schouten
  • 500
  • 2
  • 5
  • Funny that your implementation seems to be fundamentally incompatible with POSIX as it declares the root as a `posix_tnode *` instead of a `void *` as POSIX mandates. – Chris Dodd Oct 23 '21 at 01:17
  • That would have been incredibly funny, Chris, but only if it were true. Just do a web search for posix_tnode and you will find that one of the top hits is an issue I filed against POSIX to add this data type. It will be part of the eighth edition. It's already in the latest drafts. Because 'posix_*' is a reserved namespace on POSIX compliant systems, I took the liberty of declaring it unconditionally. To simplify the implementation a bit, I'm declaring it as a struct type instead of 'void', but only as part of the tsearch.c / tdelete.c / ... compilation units. – Ed Schouten Oct 24 '21 at 11:06
  • This seems like a bad (backwards-compatibility breaking) change in the spec, unless it is required to be typedef'd to void. The main problem being your code cannot be used as a drop-in replacement for tsearch, as it will break most programs that use it (you cant implicitly convert a `void **` to a `posix_tnode **` if posix_tnode is not void.) – Chris Dodd Oct 24 '21 at 18:51
  • That’s exactly how it needs to be defined: as void. It’s merely been added to improve the readability of the signatures. I was not claiming that my implementation is a drop-in replacement; it is just an implementation. – Ed Schouten Oct 25 '21 at 19:06
2

You can verify by calling tsearch on an ordered list of values, and then invoking twalk, supplying an action that prints out the depth of the tree. If no tree ordering is taking place then the ordered inserts would have created a list rather than a tree and you will output ascending depth values.

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
  • 60,864
  • 6
  • 61
  • 103
0

Paddy's answer explains how to verify the tree to be balanced, but does not answer the question whether the tree is balanced or not.

I did what suggested by Paddy, and the answer for me is yes, it is balanced (I run GCC 5.1.1 on Fedora, Glibc 2.21)

(I'm not sure if this also applies on different combination of Operating System, Compiler and Standard Library. If anyone experiments a different answer on their systems, please add an answer here!)

Dacav
  • 13,590
  • 11
  • 60
  • 87