From: Robert Klemme <shortcutter@...>
Date: 2008-06-30T20:01:12+09:00
Subject: Re: data structure

2008/6/30 Shashank Agarwal <shashank_hi@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