From: Robert Klemme Date: 2008-06-30T23:05:26+09:00 Subject: Re: data structure 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