From: Axel Etzold <AEtzold@...>
Date: 2008-06-30T22:42:04+09:00
Subject: Re: data structure


-------- Original-Nachricht --------
> Datum: Mon, 30 Jun 2008 22:22:18 +0900
> Von: Vandana <nairvan@gmail.com>
> An: ruby-talk@ruby-lang.org
> Betreff: Re: data structure

> On Jun 30, 7:01 am, Robert Klemme <shortcut...@googlemail.com> wrote:
> > 2008/6/30 Shashank Agarwal <shashank...@yahoo.com>:
> >
> >
> >
> > > 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