From: Vandana <nairvan@...>
Date: 2008-06-30T23:57:20+09:00
Subject: Re: data structure

On Jun 30, 10:05 am, Robert Klemme <shortcut...@googlemail.com> wrote:
> 2008/6/30 Vandana <nair...@gmail.com>:
>
>
>
> > 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?
>
> 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