By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,651 Members | 1,684 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,651 IT Pros & Developers. It's quick & easy.

Balanced binary tree with fixed leaf nodes

P: n/a
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

Nov 14 '05 #1
Share this Question
Share on Google+
7 Replies


P: n/a
On 7 Mar 2005 13:50:03 -0800, ab******@hotmail.com wrote in
comp.lang.c:
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.

--
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.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Nov 14 '05 #2

P: n/a
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....

Nov 14 '05 #3

P: n/a
ab******@hotmail.com wrote:

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.

--
"If you want to post a followup via groups.google.com, 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

Nov 14 '05 #4

P: n/a
On Mon, 07 Mar 2005 13:50:03 -0800, abhrajit wrote:
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

Nov 14 '05 #5

P: n/a
Lawrence: Thanks for the newsgroup pointers. Will take my woes there.

Nov 14 '05 #6

P: n/a
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:
On 7 Mar 2005 13:50:03 -0800, ab******@hotmail.com wrote in
comp.lang.c:
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.

--
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.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html


Nov 14 '05 #7

P: n/a
zr****@gmail.com wrote:
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).

Nov 14 '05 #8

This discussion thread is closed

Replies have been disabled for this discussion.