This week's giveaway is in the Android forum. We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line! See this thread for details.

Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with. If I know I have a binary tree, then I can store the values of each node in an array tier by tier, but I have to leave empty cells wherever a node has fewer than two children. And I have to be extremely careful about the order in which I do this. Any way I look at it, I can't see how walking the tree would work at all.

Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

That depends on the nature of the tree. Since the question is quite vague, with no details about the tree other than that it is n-ary, it's impossible to be very specific. If the tree behaves like a List, where iteration order matches insertion order, or if the tree behaves like a SortedSet, where iteration order follows sorting rules, then you'll get back what you started with. If neither of these are true, then it's impossible to do what the OP asks without more details about how elements will be added to and iterated over in the specific tree in question.

Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

It might well not, and that may indeed be what you want.

For example, I could imagine a balancing method that went something like (pseudo-ish):

Although, as Jeff says, it's difficult to tell much from OP's description exactly what the requirements are.

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here

dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808

posted

0

Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

Winston Gutkowski wrote:It might well not, and that may indeed be what you want.

If I don't care what the result is, I'm not sure why I need an algorithm.

Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

Winston Gutkowski wrote:It might well not, and that may indeed be what you want.

If I don't care what the result is, I'm not sure why I need an algorithm.

I think it all just goes back to trying to take a broad swipe at a very vague question.

Dorothy Taylor
Ranch Hand

Joined: Nov 26, 2007
Posts: 104

posted

0

If it was as simple as Jeff's solution suggests, I wouldn't have posted in this forum. So obviously the problem is convert the n-ary tree to an array. So if the root node is n, then left child is 2n+1 and right is 2n+2. That is clear, however, it will leave some empty values in the array. Hence this solution is not space efficient. Again, suppose we devise a space efficient algorithm in which there are no empty array elements. then how do we get back the tree from this array? Moreover the algorithm has to be generic i.e. n-ary. This means that the 'n' is also an input.

So my question is that is Jeff's solution the best that can be done in this case, or is there a better way out?

Dorothy Taylor
Ranch Hand

Joined: Nov 26, 2007
Posts: 104

posted

0

Jeff Verdegan wrote:

Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

That depends on the nature of the tree. Since the question is quite vague, with no details about the tree other than that it is n-ary, it's impossible to be very specific.

If the tree behaves like a List, where iteration order matches insertion order, or if the tree behaves like a SortedSet, where iteration order follows sorting rules, then you'll get back what you started with. If neither of these are true, then it's impossible to do what the OP asks without more details about how elements will be added to and iterated over in the specific tree in question.

Since there are no specific things given other than it is an n-ary tree, one is free to make assumptions. However, for a binary or n-ary tree, I do not understand why the tree behaviour should be like a list or sorted set. A tree is a tree that can be traversed using breadth first or depth first traversals. We are not going to choose any elements from the tree on weightages etc. and create an array. Obviously we have to make use of tree properties only when only that is given to us.

Dorothy Taylor wrote:So obviously the problem is convert the n-ary tree to an array. So if the root node is n, then left child is 2n+1 and right is 2n+2. That is clear,

Actually not. In a proper n-ary tree, the left child will be something like p(n^L)+1, where L is the level and p is the 'position' of the parent node in its level; and even then the formula only holds if the tree is perfectly balanced. The case you are quoting is for a heap, which is a special case of a binary tree.

however, it will leave some empty values in the array. Hence this solution is not space efficient.

Actually, if n is large enough, the space taken up by unused slots is very small. SkipLists, for example, use a stack of 'fast-track' pointers akin to your tree to access the elements in a linked list, and the main space inefficiency is in the linked list itself. If n=8, the total overhead for storing the pointers for x nodes in a well-balanced tree approaches x/7, whereas for the linked list itself, it's x (or 2x if the LL is bi-directional).

So my question is that is Jeff's solution the best that can be done in this case, or is there a better way out?

You might want to have a look at skiplists. Java's implementation is as a ConcurrentSkipListMap or Set, which are heavily skewed for concurrent operation, but the docs have references to William Pugh's paper, which shows you how to write your own.

Dorothy Taylor wrote:If it was as simple as Jeff's solution suggests, I wouldn't have posted in this forum. So obviously the problem is convert the n-ary tree to an array.

I guess I was making some assumptions and oversimplifying the problem. Although a bit more detail in the original question would have helped.

So if the root node is n, then left child is 2n+1 and right is 2n+2. That is clear, however, it will leave some empty values in the array. Hence this solution is not space efficient.

Ah, now we're getting somewhere.

So you want to keep track of holes in the tree, but you want to consume zero memory to do so?

Again, suppose we devise a space efficient algorithm in which there are no empty array elements. then how do we get back the tree from this array?

In other words, "If I remove information, how do I get it back?" You don't.

Now, depending on the nature of the pattern of nodes and holes, you might be able to make use of some sort of compression. For instance, keep a separate array for runs of consecutive holes. If you have more than 4 consecutive holes in the main array, add indications for their start and end in the hole array.

Are you really dealing with such a huge amount of data with so many holes that it's really worth it though?

Have you actually tried it the simplest, most straightforward way and measured that it will waste an unacceptable amount of memory? Or are you just assuming and prematurely optimizing?