Help : Merging Binary Search Trees

Discussion in 'C Programming' started by ptrSriram, Dec 10, 2005.

  1. ptrSriram

    ptrSriram Guest

    Can someone help me with an algorithm to merge two binary search trees.

    One method I thought of was to flatten both the trees into sorted
    lists(inorder traversal),merge those two sorted lists, and build a
    binary search tree from the new list.
    But this seems to be expensive in terms of space. Can this be done more
    efficiently ?
    Please help me.
     
    ptrSriram, Dec 10, 2005
    #1
    1. Advertising

  2. In article <>,
    ptrSriram <> wrote:
    >Can someone help me with an algorithm to merge two binary search trees.


    >One method I thought of was to flatten both the trees into sorted
    >lists(inorder traversal),merge those two sorted lists, and build a
    >binary search tree from the new list.
    >But this seems to be expensive in terms of space. Can this be done more
    >efficiently ?


    That depends. There are a number of different types of binary trees.
    Is there some particular property imposed on the trees you are
    using, such as that they must be "balanced" ? Do your tree entries
    have back-pointers or just downward pointers?
    --
    "No one has the right to destroy another person's belief by
    demanding empirical evidence." -- Ann Landers
     
    Walter Roberson, Dec 10, 2005
    #2
    1. Advertising

  3. ptrSriram

    Chuck F. Guest

    Walter Roberson wrote:
    > ptrSriram <> wrote:
    >
    >> Can someone help me with an algorithm to merge two binary
    >> search trees.

    >
    >> One method I thought of was to flatten both the trees into
    >> sorted lists(inorder traversal),merge those two sorted lists,
    >> and build a binary search tree from the new list. But this
    >> seems to be expensive in terms of space. Can this be done
    >> more efficiently ?

    >
    > That depends. There are a number of different types of binary
    > trees. Is there some particular property imposed on the trees
    > you are using, such as that they must be "balanced" ? Do your
    > tree entries have back-pointers or just downward pointers?


    I think the question should be answered in terms of a minimal
    organization. i.e. the fundamental data item should be very
    similar to:

    struct itemlink {
    struct itemlink *left, *right;
    void *dataptr;
    };

    together with some routine that will return a -1, 0, +1 comparison
    result when passed two struct itemlink * pointers. Then the trees
    to be merged are represented by two struct itemlink * pointers to
    the roots of the two trees.

    --
    Read about the Sony stealthware that is a security leak, phones
    home, and is generally illegal in most parts of the world. Also
    the apparent connivance of the various security software firms.
    http://www.schneier.com/blog/archives/2005/11/sonys_drm_rootk.html
     
    Chuck F., Dec 10, 2005
    #3
  4. ptrSriram

    Thad Smith Guest

    ptrSriram wrote:
    > Can someone help me with an algorithm to merge two binary search trees.
    >
    > One method I thought of was to flatten both the trees into sorted
    > lists(inorder traversal),merge those two sorted lists, and build a
    > binary search tree from the new list.
    > But this seems to be expensive in terms of space.


    Why would it be expensive in space? If the data is in a tree, each item
    should be held in a node with two or more pointers. You should be able
    to link the items into list, merge them, and place them in another tree
    without any additional space.

    --
    Thad
     
    Thad Smith, Dec 12, 2005
    #4
    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. binary search trees

    , Mar 5, 2008, in forum: C++
    Replies:
    2
    Views:
    276
  2. jacob navia

    Binary search trees (AVL trees)

    jacob navia, Jan 3, 2010, in forum: C Programming
    Replies:
    34
    Views:
    1,458
    Dann Corbit
    Jan 8, 2010
  3. Dann Corbit

    Re: Binary search trees or hash tables?

    Dann Corbit, Jan 6, 2010, in forum: C Programming
    Replies:
    0
    Views:
    633
    Dann Corbit
    Jan 6, 2010
  4. BGB / cr88192

    Re: Binary search trees or hash tables?

    BGB / cr88192, Jan 6, 2010, in forum: C Programming
    Replies:
    5
    Views:
    394
    BGB / cr88192
    Jan 7, 2010
  5. Gavin Kistner

    Diffing/Merging Hierarchical Trees

    Gavin Kistner, Aug 21, 2005, in forum: Ruby
    Replies:
    1
    Views:
    114
Loading...

Share This Page