Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks.
I want to traverse this type of tree giving equal opportunity/priority/time(?) for each group with respect to its parent.
For example, if the root have 3 sub-trees (node or leaf), first I want to complete 1 task from the first sub-tree, then complete another task from the second sub-tree, and finally complete a task from the third sub-tree. When all sub-trees processed, the algorithm would start from the beginning this time selecting the second task from the sub-trees. This way, all the sub-trees would have equal processing time in terms of tasks in a given time frame. The same requirement is also present in each sub-trees themselves recursively of course.
This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?
Consider the following tree structure as an example:
So the traversal I am thinking about would be as following for this example.
- Level 0 has no task, 3 sub-trees, go into first sub-tree to find a task
- We follow as in depth-first to arrive at task A and select it (complete it)
- Now the first sub-tree in level 1 has a task completed, while its siblings are at 0, so we select from the second sub-tree
- Level 1 second sub-tree has only one task, D, so we select it
- Similarly we go in to the third sub-tree and find the task F and select it
- Now we return to level 1 and try to find our second task from the first sub-tree
- IMPORTANT: We have already selected a task from level 1's first sub-tree, so we go into its second sub-tree and select task E
- Now level 1 first sub-tree has two tasks completed, and the second sub-tree has no other tasks, so we skip it and go into third sub-stree and select G
- Similary, we loop again and select B from left side, and I from right side (we don't select H because its sibling already selected)
- Then we select C from the left side completing this side and K from the right side (J is not selected similarly)
- Only the right is left, so we select first H and finally the J, completing our traversal.
Traversal of leaves: (A->D->F)->(E->G)->(B->I)->(C->K)->(H)->(J)
[Adding this clarifying paragraph from the comments:]
Essentially the algorithm prevents any sub-grouping getting ahead (more than 1 tasks) of its unfinished siblings. It might be considered, in part, as a hierarchical round-robin scheduling giving equal time in terms of task operations.
So my questions are:
Is there a name for this kind of tree traversal. If not, what would you call it?
How would you approach traversing this tree in an efficient way and what would be the complexity?
EDIT: Changed "opportunity" to "opportunity/priority/time(?)" in text and removed it from the title.
UPDATE: I have used the final algorithm from Apass.Jack and compared some different trees on it. Calculating the complexity proved difficult, though it definitely looks lower than $O(n\log n)$,.
JS Code can be found as a:
Here are some execution results for different depths (D) and leaf counts (L):
D3L10 | D3L1000 | D6L10 | D6L1000 =================================== Push | 35 | 3350 | 50 | 4698 | Unshift | 14 | 1150 | 17 | 1549 | Splice | 35 | 3350 | 50 | 4698 | Access | 35 | 3350 | 50 | 4698 | Traverse()| 16 | 1351 | 20 | 1808 | Zip() | 5 | 151 | 8 | 550 | -----------------------------------
NOTE: My question traversed siblings in left to right order but as Apass.Jack has stated below, a randomized recursive round-robin (RRRR) algorithm would indeed be more useful in task-management situation and current algorithm could be modified to do that easily.