From: Vandana <nairvan@...>
Date: 2008-06-30T22:22:18+09:00
Subject: 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?