# Data structure **URL:** \ **Category:** Ruby\ **Created:** [June 30, 2008, 1:15am UTC](https://www.ruby-forum.com/t/data-structure/141716 "2008-06-30T01:15:36Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 1:15am UTC](https://www.ruby-forum.com/t/data-structure/141716/1 "2008-06-30T01:15:36Z")
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? Thanks, Vandana. ---
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 1:31am UTC](https://www.ruby-forum.com/t/data-structure/141716/2 "2008-06-30T01:31:18Z")
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? > > Thanks, > Vandana. 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. Do check the function coz I made them as I typed. ---
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 8:45am UTC](https://www.ruby-forum.com/t/data-structure/141716/3 "2008-06-30T08:45:53Z")
On 2008-06-29, Vandana [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > 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? I would suggest the use of an algorithm. ---
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 1:04pm UTC](https://www.ruby-forum.com/t/data-structure/141716/4 "2008-06-30T13:04:58Z")
2008/6/30 Shashank A. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > 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 ---
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 3:25pm UTC](https://www.ruby-forum.com/t/data-structure/141716/5 "2008-06-30T15:25:55Z")
On Jun 30, 7:01 am, Robert K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > > 1. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes. > > – > 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? ---
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 3:45pm UTC](https://www.ruby-forum.com/t/data-structure/141716/6 "2008-06-30T15:45:15Z")
-------- Original-Nachricht -------- > Datum: Mon, 30 Jun 2008 22:22:18 +0900 > Von: Vandana [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) > An: removed\_email\_address@domain.invalid > Betreff: Re: data structure > > > > 1. The tree is balanced. > > > > would be x_5 + 1, x_5 + 2, …, x\*5 + 5. Similarly, floor((x - 1) /5) > > > > robert > > > > 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](http://www.rubyquiz.com/quiz137.html) Best regards, Axel ---
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 3:53pm UTC](https://www.ruby-forum.com/t/data-structure/141716/7 "2008-06-30T15:53:27Z")
Am I right that given a number of nodes N, you want to know how to construct a most balanced tree? You’re not so interested in dynamic behaviour - you just want the best static tree to keep it as balanced as possible? This is more of a maths question than a datastructures question. I think you’d want to give a stronger definition of what you want from the tree. For example, I’d imagine that you’d want only the direct leaf’s parents to not be full, and all other nodes to have 5 children? Cheers, B ---
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 4:08pm UTC](https://www.ruby-forum.com/t/data-structure/141716/8 "2008-06-30T16:08:41Z")
2008/6/30 Vandana [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > > > > 1. The tree is balanced. > > > > will be the parent’s node. > > 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. [Red–black tree - Wikipedia](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 ---
**Author:** ![Vandana](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/aeb1de/32.png) [@Vandana](https://www.ruby-forum.com/u/Vandana)\ **Post date:** [June 30, 2008, 5:03pm UTC](https://www.ruby-forum.com/t/data-structure/141716/9 "2008-06-30T17:03:18Z")
On Jun 30, 10:05 am, Robert K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > > > > I would like to implement a tree with the following properties. > > > > > children and so on. The function to find node x’s (five) children then > > > children and the last one having just 2 children. This situation I > > is a particular use case. > > 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