May 14, 2010

Multi-Level Trees ( Stacked Circular Linked Lists ) : A Perspective

As I had mentioned in my earlier post on fundamental work in computer science, I try to think about how simple things such as data structures can be visualized in a different or new manner which can lead to an efficient solution for certain use cases. Before reading this post, there are a few things I must warn you about. First, the structure I have described here is much further from an actual tree data structure than anything else, I call it a tree for different reasons. Second, the idea presented here might have already been thought about by someone and dumped for not being any useful, so don't condemn the post pointlessly, this is just an effort to attract some peer review on my thought process.

Now to the actual stuff. The ml-tree consists of various levels, the number of levels (k) is fixed and describes the tree. At each level there is a central node and there are n(i) nodes (where "i" is the level) which are connected in a circular doubly linked list. Each node in the circular doubly linked list is connected to the central node (though I have strong doubts about the need to connect all the nodes). The central node serves the purpose of performing "daily-wage" jobs for its level and is not supposed to hold any important data, all the data must be stored in the "nodes on the circle". More so the central node in some cases can hold a hash for the data in the "nodes on the circle". In some cases it can also act as a cache for the data on that level (I will try to discuss this usage of the data structure as a distributed cache system in a separate post).
The central nodes of all the levels are in turn connected in a linked list as represented below.

Describing Parameters 
The structure is primarily described by the number of levels k. Secondly, the number of nodes at each level n(i) also describes the structure. You might be wondering why I used a function based notation for n(i) rather than a subscript based notation, there is a subtle meaning here, the number of nodes at each level can also be passed as a function, n(i) = i , or something like n(i) = i*i , and other such variants depending on the use case and the requirement.

Why is it named a ml-tree ?
Ok this might be the most idiotic part of the whole post, the first inspiration I had for this structure was from a real world tree, more so from the structural beauty of a pine tree (or something similar, a conical shape in plain terms). This ignited a further thought process (all the crap going on in my brain) on why a tree data structure is so different from a real world "3-D" tree .
This structure can also be visualized as a stack of circles (or circular doubly linked lists to be more precise) as my friend Harshit rightly pointed out, but that is only when the number of nodes at each level (n(i)) is a constant. Otherwise it leads to a stack of elements with dissimilar properties.

What next ?
I will try to write a separate post describing some possible use cases and why this structure would be an easier representation than something else. If you can think of something, do leave a comment. :)