Balanced binary tree with fixed leaf nodes

[abhrajit@hotmail.com]

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]

Re: Balanced binary tree with fixed leaf nodes

On 7 Mar 2005 13:50:03 -0800, abhrajit@hotmai l.com wrote in
comp.lang.c:
[color=blue]
> I'm looking for a C/C++/Java library to create a balanced binary tree[/color]

http://www.google.com.

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

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++

http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

[abhrajit@hotmail.com]

Re: Balanced binary tree with fixed leaf nodes

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]

Re: Balanced binary tree with fixed leaf nodes

abhrajit@hotmai l.com wrote:[color=blue]
>
> 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....[/color]

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.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Lawrence Kirby]

Re: Balanced binary tree with fixed leaf nodes

On Mon, 07 Mar 2005 13:50:03 -0800, abhrajit wrote:
[color=blue]
> 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.[/color]

A good place to discuss datastructures and algorithms is comp.programmin g.
For libraries you might try asking in comp.sources.wa nted. Also according
to my newsreader there is a comp.lang.java hierarchy but no comp.lang.java
newsgroup.
[color=blue]
> 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).[/color]

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.programmin g.

Lawrence

[abhrajit@hotmail.com]

Re: Balanced binary tree with fixed leaf nodes

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

[zrelli@gmail.com]

Re: Balanced binary tree with fixed leaf nodes

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.

Jack Klein wrote:[color=blue]
> On 7 Mar 2005 13:50:03 -0800, abhrajit@hotmai l.com wrote in
> comp.lang.c:
>[color=green]
> > I'm looking for a C/C++/Java library to create a balanced binary[/color][/color]
tree[color=blue]
>
> http://www.google.com.
>
> And Java is off-topic in comp.lang.c.
>
> --
> Jack Klein
> Home: http://JK-Technology.Com
> FAQs for
> comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
> comp.lang.c++ http://www.parashift.com/c++-faq-lite/
> alt.comp.lang.l earn.c-c++
> http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html[/color]

[scooter.phd@gmail.com]

Re: Balanced binary tree with fixed leaf nodes

zrelli@gmail.co m wrote:[color=blue]
> 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[/color]
but[color=blue]
> it is not comiled.
> you can compile the library independentely from the whole bind9[/color]
package[color=blue]
> then use it.[/color]

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