2

i'm search a solution for the following task:

i have a flat list with a lot of data.

Now i want to transfrom this list into an tree with the following rules:

  • all of my listitems should be leafs
  • the number of nodes per tree depth should be limit the a certain limit
  • nodes can be nested with unlimited depth

i think it's like an k-ary (with k is the node limit per level) tree, but maybe this thing has annother name.

The background for this task is a visualisation problem of my list in a radial tree. Displaying all leafs on the first level in the radial tree doesn't look good when there are too much. So i think it's better to insert some nodes to group my data when the level limit is reached. The resulting tree should be able to display the leafs in a better visually way.

is there an algorithm or even better an implementation for this task?

Thanks for any pointer or infos.

Improve this question
4
  • Should the tree keep the elements in some special order (e.g. sorted), or simply in the order from the list? Commented Jul 22, 2011 at 16:58
  • special ordering is not so important. the list entries has some sort of order. Commented Jul 22, 2011 at 17:00
  • Does the k limit the total number of nodes at a level? K-ary means k child nodes per internal node (no per-level limit) which is a different thing. Commented Jul 22, 2011 at 19:40
  • k should limit the number of siblings per level Commented Jul 23, 2011 at 7:37

1 Answer 1

Reset to default
4

Let's say N, the number of items in your list is 4 and K=2. So this will be a binary tree.

Step 1: Create 2 nodes

 P1 P2 1 2 3 4

Step 2: Create links between the 2 nodes and K of the leaf nodes

 P1 P2 / \ / \ 1 2 3 4

Step 3: Create another node

 P5 P1 P2 / \ / \ 1 2 3 4

Step 4: Create the links between that node and the 2 previous nodes you created

 P5 / \ P1 P2 / \ / \ 1 2 3 4

See the pattern? You can do this iteratively pretty easily for any such N and K. You have to worry a little about cases where N is not a perfect power of K. Basically the number of children of every node is at most ceil(N/K).

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Isn't the constraint K nodes per level? If this is the case, then the leaf level breaks the constraint. If the constraint is K children per node, then of course it's OK.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.