Balanced binary tree with fixed leaf nodes

[abhrajit]

I'm looking for a C/C++/Java library to create a balanced binary tree
data structure given a set of leaf nodes as input. A leaf node should
never become an interior node.

So if I wish to create a tree that will have a,b,c & d as leaf nodes -
this tree will contain nodes other than a,b,c & d as interior nodes:

e.g.
x
/ \
y z
/ \ / \
a b c d

The tree is balanced (to the extent possible) and all the input nodes
are leaves. (x,y,z are internal nodes that were not specified as
input).

Appreciate any help,
Abhrajit

 

[Jack Klein]

I'm looking for a C/C++/Java library to create a balanced binary tree

http://www.google.com.

And Java is off-topic in comp.lang.c.

 

[abhrajit]

Apologies for the cross post. There are plenty of libraries for binary
& balanced binary tree creation but none that meet my specific
requirements. Was hoping someone on this list may have an inkling....

 

[CBFalconer]

Apologies for the cross post. There are plenty of libraries for
binary & balanced binary tree creation but none that meet my
specific requirements. Was hoping someone on this list may have
an inkling....

The cure for the cross post is obvious - don't do it. F'ups set.

There are various ways of creating balanced binary trees. Look up
AVL (Adelson-Velski) trees and red-black trees. Ben Pfaffs
writings on trees are fairly definitive, and freely available.
Read Knuth and Sedgewick. Then write your own code if you don't
like what you find.

 

[Lawrence Kirby]

I'm looking for a C/C++/Java library to create a balanced binary tree
data structure given a set of leaf nodes as input. A leaf node should
never become an interior node.

A good place to discuss datastructures and algorithms is comp.programming.
For libraries you might try asking in comp.sources.wanted. Also according
to my newsreader there is a comp.lang.java hierarchy but no comp.lang.java
newsgroup.

So if I wish to create a tree that will have a,b,c & d as leaf nodes -
this tree will contain nodes other than a,b,c & d as interior nodes:

e.g.
x
/ \
y z
/ \ / \
a b c d

The tree is balanced (to the extent possible) and all the input nodes
are leaves. (x,y,z are internal nodes that were not specified as
input).

That's an unusual datastructure, most of this sort benefit from placing
data in internal nodes too. It might help if you explained why you can't
do this, probably in comp.programming.

Lawrence

 

[abhrajit]

Lawrence: Thanks for the newsgroup pointers. Will take my woes there.

 

[zrelli]

hi ,

in bind9, there is a library called isc, useful AVL functions are
implemented there. I know that it exists by defulat in FreeBSD-5.3 but
it is not comiled.
you can compile the library independentely from the whole bind9 package
then use it.

 

[scooter.phd]

hi ,

in bind9, there is a library called isc, useful AVL functions are
implemented there. I know that it exists by defulat in FreeBSD-5.3 but
it is not comiled.
you can compile the library independentely from the whole bind9 package
then use it.

Paul Vixie wrote those routines many years ago and released them under
a BSD-style licence. They work well (I've used them before happily).