data structure

Discussion in 'Ruby' started by Vandana, Jun 30, 2008.

  1. Vandana

    Vandana Guest

    Hello All,

    I would like to implement a tree with the following properties.

    1. The tree is balanced.
    2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
    3. The tree remains static. Number of nodes known from the beginning.

    How would I implement this in ruby?

    Thanks,
    Vandana.
    Vandana, Jun 30, 2008
    #1
    1. Advertising

  2. Vandana wrote:
    > Hello All,
    >
    > I would like to implement a tree with the following properties.
    >
    > 1. The tree is balanced.
    > 2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
    > 3. The tree remains static. Number of nodes known from the beginning.
    >
    > How would I implement this in ruby?
    >
    > Thanks,
    > Vandana.


    If the number of nodes are known, then an array based implementation
    would be better. So basically, arr[0] is the root. Since it has maximum
    5 sub nodes, index 1-5 are the roots children, 6-10 are array[1]'s
    children and so on. The function to find node x's (five) children then
    would be x*5 + 1, x*5 + 2, ..., x*5 + 5. Similarly, floor((x - 1) /5)
    will be the parent's node.

    Do check the function coz I made them as I typed.
    --
    Posted via http://www.ruby-forum.com/.
    Shashank Agarwal, Jun 30, 2008
    #2
    1. Advertising

  3. Vandana

    Seebs Guest

    On 2008-06-29, Vandana <> wrote:
    > 1. The tree is balanced.
    > 2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
    > 3. The tree remains static. Number of nodes known from the beginning.
    >
    > How would I implement this in ruby?


    I would suggest the use of an algorithm.

    --
    Copyright 2008, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    Seebs, Jun 30, 2008
    #3
  4. 2008/6/30 Shashank Agarwal <>:
    > Vandana wrote:
    >> Hello All,
    >>
    >> I would like to implement a tree with the following properties.
    >>
    >> 1. The tree is balanced.
    >> 2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
    >> 3. The tree remains static. Number of nodes known from the beginning.
    >>
    >> How would I implement this in ruby?

    >
    > If the number of nodes are known, then an array based implementation
    > would be better. So basically, arr[0] is the root. Since it has maximum
    > 5 sub nodes, index 1-5 are the roots children, 6-10 are array[1]'s
    > children and so on. The function to find node x's (five) children then
    > would be x*5 + 1, x*5 + 2, ..., x*5 + 5. Similarly, floor((x - 1) /5)
    > will be the parent's node.


    This might not even be needed depending on the usage of the tree, i.e.
    if the tree is ordered then a binary search on the array might be
    sufficient.

    Btw, RAA also references a read black tree implementation...

    Kind regards

    robert


    --
    use.inject do |as, often| as.you_can - without end
    Robert Klemme, Jun 30, 2008
    #4
  5. Vandana

    Vandana Guest

    On Jun 30, 7:01 am, Robert Klemme <> wrote:
    > 2008/6/30 Shashank Agarwal <>:
    >
    >
    >
    > > Vandana wrote:
    > >> Hello All,

    >
    > >> I would like to implement a tree with the following properties.

    >
    > >> 1. The tree is balanced.
    > >> 2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
    > >> 3. The tree remains static. Number of nodes known from the beginning.

    >
    > >> How would I implement this in ruby?

    >
    > > If the number of nodes are known, then an array based implementation
    > > would be better. So basically, arr[0] is the root. Since it has maximum
    > > 5 sub nodes, index 1-5 are the roots children, 6-10 are array[1]'s
    > > children and so on. The function to find node x's (five) children then
    > > would be x*5 + 1, x*5 + 2, ..., x*5 + 5. Similarly, floor((x - 1) /5)
    > > will be the parent's node.

    >
    > This might not even be needed depending on the usage of the tree, i.e.
    > if the tree is ordered then a binary search on the array might be
    > sufficient.
    >
    > Btw, RAA also references a read black tree implementation...
    >
    > Kind regards
    >
    > robert
    >
    > --
    > use.inject do |as, often| as.you_can - without end


    Thanks for your replies. My problem is i dont know how to keep the
    tree balanced.

    For example if there are a total of 17 nodes, then I need 1 main_root
    node, and I could use 3 sub_root_nodes, with the first 2 having 5
    children and the last one having just 2 children. This situation I
    want to avoid. More ideally all the sub nodes should have number of
    children ranging from 3 -5
    I dont want some of the sub_nodes to be full and the last one to be
    not even half full.

    Any ideas on how to do this best?
    Vandana, Jun 30, 2008
    #5
  6. Vandana

    Axel Etzold Guest

    -------- Original-Nachricht --------
    > Datum: Mon, 30 Jun 2008 22:22:18 +0900
    > Von: Vandana <>
    > An:
    > Betreff: Re: data structure


    > On Jun 30, 7:01 am, Robert Klemme <> wrote:
    > > 2008/6/30 Shashank Agarwal <>:
    > >
    > >
    > >
    > > > Vandana wrote:
    > > >> Hello All,

    > >
    > > >> I would like to implement a tree with the following properties.

    > >
    > > >> 1. The tree is balanced.
    > > >> 2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
    > > >> 3. The tree remains static. Number of nodes known from the beginning.

    > >
    > > >> How would I implement this in ruby?

    > >
    > > > If the number of nodes are known, then an array based implementation
    > > > would be better. So basically, arr[0] is the root. Since it has

    > maximum
    > > > 5 sub nodes, index 1-5 are the roots children, 6-10 are array[1]'s
    > > > children and so on. The function to find node x's (five) children then
    > > > would be x*5 + 1, x*5 + 2, ..., x*5 + 5. Similarly, floor((x - 1) /5)
    > > > will be the parent's node.

    > >
    > > This might not even be needed depending on the usage of the tree, i.e.
    > > if the tree is ordered then a binary search on the array might be
    > > sufficient.
    > >
    > > Btw, RAA also references a read black tree implementation...
    > >
    > > Kind regards
    > >
    > > robert
    > >
    > > --
    > > use.inject do |as, often| as.you_can - without end

    >
    > Thanks for your replies. My problem is i dont know how to keep the
    > tree balanced.
    >
    > For example if there are a total of 17 nodes, then I need 1 main_root
    > node, and I could use 3 sub_root_nodes, with the first 2 having 5
    > children and the last one having just 2 children. This situation I
    > want to avoid. More ideally all the sub nodes should have number of
    > children ranging from 3 -5
    > I dont want some of the sub_nodes to be full and the last one to be
    > not even half full.
    >
    > Any ideas on how to do this best?


    Vandana,

    have a look here:

    http://www.rubyquiz.com/quiz137.html

    Best regards,

    Axel
    --
    Der GMX SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen!
    Ideal für Modem und ISDN: http://www.gmx.net/de/go/smartsurfer
    Axel Etzold, Jun 30, 2008
    #6
  7. Vandana

    Guest

    Am I right that given a number of nodes N, you want to know how to
    construct a most balanced tree? You're not so interested in dynamic
    behaviour - you just want the best static tree to keep it as balanced as
    possible?

    This is more of a maths question than a datastructures question. I think
    you'd want to give a stronger definition of what you want from the tree.
    For example, I'd imagine that you'd want only the direct leaf's parents to
    not be full, and all other nodes to have 5 children?

    Cheers,
    B
    , Jun 30, 2008
    #7
  8. 2008/6/30 Vandana <>:
    > On Jun 30, 7:01 am, Robert Klemme <> wrote:
    >> 2008/6/30 Shashank Agarwal <>:
    >>
    >>
    >>
    >> > Vandana wrote:
    >> >> Hello All,

    >>
    >> >> I would like to implement a tree with the following properties.

    >>
    >> >> 1. The tree is balanced.
    >> >> 2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
    >> >> 3. The tree remains static. Number of nodes known from the beginning.

    >>
    >> >> How would I implement this in ruby?

    >>
    >> > If the number of nodes are known, then an array based implementation
    >> > would be better. So basically, arr[0] is the root. Since it has maximum
    >> > 5 sub nodes, index 1-5 are the roots children, 6-10 are array[1]'s
    >> > children and so on. The function to find node x's (five) children then
    >> > would be x*5 + 1, x*5 + 2, ..., x*5 + 5. Similarly, floor((x - 1) /5)
    >> > will be the parent's node.

    >>
    >> This might not even be needed depending on the usage of the tree, i.e.
    >> if the tree is ordered then a binary search on the array might be
    >> sufficient.
    >>
    >> Btw, RAA also references a read black tree implementation...
    >>
    >> Kind regards
    >>
    >> robert
    >>
    >> --
    >> use.inject do |as, often| as.you_can - without end

    >
    > Thanks for your replies. My problem is i dont know how to keep the
    > tree balanced.
    >
    > For example if there are a total of 17 nodes, then I need 1 main_root
    > node, and I could use 3 sub_root_nodes, with the first 2 having 5
    > children and the last one having just 2 children. This situation I
    > want to avoid. More ideally all the sub nodes should have number of
    > children ranging from 3 -5
    > I dont want some of the sub_nodes to be full and the last one to be
    > not even half full.
    >
    > Any ideas on how to do this best?


    Not sure what you are after. If you need a balanced tree you can just
    use the red black tree from RAA. And, as I said, hiding a sorted
    Array in some class with a tree like API might be sufficient if this
    is a particular use case.

    If you want to implement this yourself there are explanations in about
    every textbook about balanced trees. This is pretty basic stuff and
    there's even documentation online, e.g.
    http://en.wikipedia.org/wiki/Red_black_tree - if this is homework I
    strongly suggest to read about tree balancing and implementing this
    yourself vs. trying to extract an implementation from a public
    community.

    Cheers

    robert

    --
    use.inject do |as, often| as.you_can - without end
    Robert Klemme, Jun 30, 2008
    #8
  9. Vandana

    Vandana Guest

    On Jun 30, 10:05 am, Robert Klemme <> wrote:
    > 2008/6/30 Vandana <>:
    >
    >
    >
    > > On Jun 30, 7:01 am, Robert Klemme <> wrote:
    > >> 2008/6/30 Shashank Agarwal <>:

    >
    > >> > Vandana wrote:
    > >> >> Hello All,

    >
    > >> >> I would like to implement a tree with the following properties.

    >
    > >> >> 1. The tree is balanced.
    > >> >> 2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
    > >> >> 3. The tree remains static. Number of nodes known from the beginning.

    >
    > >> >> How would I implement this in ruby?

    >
    > >> > If the number of nodes are known, then an array based implementation
    > >> > would be better. So basically, arr[0] is the root. Since it has maximum
    > >> > 5 sub nodes, index 1-5 are the roots children, 6-10 are array[1]'s
    > >> > children and so on. The function to find node x's (five) children then
    > >> > would be x*5 + 1, x*5 + 2, ..., x*5 + 5. Similarly, floor((x - 1) /5)
    > >> > will be the parent's node.

    >
    > >> This might not even be needed depending on the usage of the tree, i.e.
    > >> if the tree is ordered then a binary search on the array might be
    > >> sufficient.

    >
    > >> Btw, RAA also references a read black tree implementation...

    >
    > >> Kind regards

    >
    > >> robert

    >
    > >> --
    > >> use.inject do |as, often| as.you_can - without end

    >
    > > Thanks for your replies. My problem is i dont know how to keep the
    > > tree balanced.

    >
    > > For example if there are a total of 17 nodes, then I need 1 main_root
    > > node, and I could use 3 sub_root_nodes, with the first 2 having 5
    > > children and the last one having just 2 children. This situation I
    > > want to avoid. More ideally all the sub nodes should have number of
    > > children ranging from 3 -5
    > > I dont want some of the sub_nodes to be full and the last one to be
    > > not even half full.

    >
    > > Any ideas on how to do this best?

    >
    > Not sure what you are after. If you need a balanced tree you can just
    > use the red black tree from RAA. And, as I said, hiding a sorted
    > Array in some class with a tree like API might be sufficient if this
    > is a particular use case.
    >
    > If you want to implement this yourself there are explanations in about
    > every textbook about balanced trees. This is pretty basic stuff and
    > there's even documentation online, e.g.http://en.wikipedia.org/wiki/Red_black_tree- if this is homework I
    > strongly suggest to read about tree balancing and implementing this
    > yourself vs. trying to extract an implementation from a public
    > community.
    >
    > Cheers
    >
    > robert
    >
    > --
    > use.inject do |as, often| as.you_can - without end


    Thanks all.

    From my understanding Red-Black trees are solely used for bianry
    trees.
    I doubt I can use it for this purpose.

    Consider the following scenario: I have 16 nodes and I want to create
    a balanced tree such that each sub_node has a max of 7 nodes.
    (example)
    I can create the tree in the following 2 ways:

    Case 1: Make a root node, with 3 sub_nodes, 2 sub_nodes have 7 leaf
    nodes and the third sub_node of the root node has 2 leaf nodes.

    Case 2: Make a root node, with 3 sub_nodes, distribute the leaf nodes
    such that all 3 sub_nodes have 5 leaf nodes and 1 of them has an
    extra.

    I am interested in case 2.

    Regarding the dynamic behavior: I must first construct this and then
    be able to move around the leaf nodes and ensure that this 'balance'
    is not lost.
    I know I have to use AVL principles of rotation, but since text books
    explain only for binary trees, i wanted some help on it.
    Any ideas/pointers to the correct group to post this will be most
    helpful.

    @Robert: No this is not homework question :)

    Thanks
    Vandana
    Vandana, Jun 30, 2008
    #9
    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. Excluded_Middle

    Pointers to structure and array of structure.

    Excluded_Middle, Oct 24, 2004, in forum: C Programming
    Replies:
    4
    Views:
    752
    Martin Ambuhl
    Oct 26, 2004
  2. Leo Nunez
    Replies:
    3
    Views:
    1,214
    Neil Kurzman
    Feb 9, 2005
  3. Replies:
    2
    Views:
    605
  4. Replies:
    9
    Views:
    25,301
    Lal Bahadur Singh
    Nov 11, 2011
  5. A
    Replies:
    27
    Views:
    1,596
    Jorgen Grahn
    Apr 17, 2011
Loading...

Share This Page