Balanced binary tree with fixed leaf nodes

Discussion in 'C Programming' started by abhrajit@hotmail.com, Mar 7, 2005.

  1. Guest

    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
    , Mar 7, 2005
    #1
    1. Advertising

  2. Jack Klein Guest

    Jack Klein, Mar 8, 2005
    #2
    1. Advertising

  3. Guest

    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....
    , Mar 8, 2005
    #3
  4. CBFalconer Guest

    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
    CBFalconer, Mar 8, 2005
    #4
  5. 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
    Lawrence Kirby, Mar 8, 2005
    #5
  6. Guest

    Lawrence: Thanks for the newsgroup pointers. Will take my woes there.
    , Mar 8, 2005
    #6
  7. Guest

    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, 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/~ajo/docs/FAQ-acllc.html
    , Mar 9, 2005
    #7
  8. Guest

    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).
    , Mar 9, 2005
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Clive Moore

    Hide Leaf nodes in a jtree

    Clive Moore, Oct 29, 2003, in forum: Java
    Replies:
    1
    Views:
    774
    Harald Hein
    Oct 30, 2003
  2. Snyke

    Leaf linked binary tree

    Snyke, Nov 7, 2005, in forum: Java
    Replies:
    0
    Views:
    477
    Snyke
    Nov 7, 2005
  3. dkacher
    Replies:
    3
    Views:
    604
    dkacher
    Dec 5, 2006
  4. Lucas P Melo

    Balanced binary tree implementation

    Lucas P Melo, Jul 21, 2009, in forum: Python
    Replies:
    1
    Views:
    333
    Piet van Oostrum
    Jul 21, 2009
  5. William Main

    Fixed bug in IE Treeview Webcontrol when clicking on leaf node.

    William Main, Feb 1, 2005, in forum: ASP .Net Web Controls
    Replies:
    0
    Views:
    252
    William Main
    Feb 1, 2005
Loading...

Share This Page