3
$\begingroup$

Let T be a binary tree that is stored in the disk following the preorder layout.

For example if this is $T$:

enter image description here

then $T$ will be stored in the disk as follows:

10, 11, 0, 12, 13, 2, 7, 3, 14, 1, 15, 16, 4, 8, 17, 18, 5, 9, 6

Every node of the tree is a struct that stores the offset of the left child, the offset of the right child, the id of the node and a size variable. If a node is a leaf the offsets are set to -1.

Suppose that now in every node $u \in T$ we want to know what is the size of the subtree rooted on $u$. Assume that the elements between the disk and the memory are transferred in blocks of size $B$, the size of the memory is $M$ and it holds that $M \geq B$. Is it possible to do that in $O(\frac{N}{B})$ I/Os?

$\endgroup$
  • 1
    $\begingroup$ If you were using a post-order traversal you could just scan the array left-to-right. Is there a reason why you want to use a pre-order traversal? $\endgroup$ – GEL Sep 13 '16 at 13:48
  • $\begingroup$ how could you do it with a post order traversal and scanning? wouldn't you still have to access for every node $u$ the $\phi$ values of the two children, that can be stored far apart in the array? edit: Actually you are probably right because we could use a stack that maintains the most recent found $\phi$ values, and every time we visit an internal node, the sum of the top 2 $\phi$ values in the stack will be the $\phi$ value of the internal node. That is interesting, could we still however argue about the complexity when using preorder? Is it harder when using preorder layout? $\endgroup$ – jsguy Sep 13 '16 at 14:13
  • $\begingroup$ @jsguy I don't think there's any benefit to the pre-order traversal. the post-order traversal with your suggestion should help avoid cache misses. $\endgroup$ – GEL Sep 14 '16 at 1:28
  • $\begingroup$ 1. Presumably the running time is going to depend on the amount of memory available. If you have $N$ memory space available, then there's a trivial algorithm that uses only $O(N/B)$ I/O's: read the entire tree into memory and process it there. I suggest you edit the question further to specify how much memory is available. 2. Are there any guarantees on the height of the tree? For instance, is the tree guaranteed to be approximately balanced or to have height $O(\lg N)$? $\endgroup$ – D.W. Sep 21 '16 at 15:28
  • $\begingroup$ I updated some information about the memory size. There isn't a guarantee on the height, the tree can be huge, for example stored in a disk of size 10 TB and there aren't any constraints on the structure of the tree. All we know is, every time we access the disk, we access B nodes that are stored sequentially in the array. Personally I do not think it is possible to do it in $O(\frac{N}{B})$ I/Os unless the tree is stored in a post order layout. If it is stored in a post order layout, you can read $B$ nodes at a time, and maintain a stack to deal with the sizes. $\endgroup$ – jsguy Sep 21 '16 at 15:58
3
+150
$\begingroup$

It is possible to do it in $O(\frac{N}{B})$ if you have $B + D$ memory available, where $D$ is the maximum depth of the tree. Algorithm:

  1. Read $B$ nodes into a buffer.
  2. For each node in the buffer:
    1. Push $(node.id, num\_children(node), 0)$ to stack $S$ (respectively $(id, num, d)$).
    2. While $S.peek().num = 0$:
      1. $d = S.peek().d$
      2. Output $(S.peek().id, d)$.
      3. $S.pop()$
      4. $S.peek().num = S.peek().num - 1$
      5. $S.peek().d = max(S.peek().d, d + 1)$.
  3. If there are more nodes to process, go to 1.

The idea behind this algorithm is to associate pushing on the stack with going down a child node, and popping coming back up to a parent node.

If we initialize every node with a counter containing the number of child nodes, and we decrement this counter everytime after popping, it means that once the counter hits 0 we have visited every child node as we visit this node: we are in post-order.

We also store a maximum subtree size $d$ with every node. If we pop (go back to visit the parent node) we store the maximum of $node.d$ and $child\_node.d + 1$ into this node. This means that once we are in post-order we have the maximum size of all child subtrees + 1 stored in $d$.

$\endgroup$
  • $\begingroup$ @D.W. Added the explanation. It's fairly basic pre-order to post-order conversion using a stack. $\endgroup$ – orlp Sep 21 '16 at 18:09
  • $\begingroup$ Nice! I think you can improve this further, so we use only $O(B)$ memory, regardless of the maximum depth of the tree. Store the stack on disk in blocks of size $B$, but with the last 1-2 blocks of the stack in a buffer in memory. I think you can implement push and pop so that the amortized number of I/O's per push/pop of the stack is $O(1/B)$, i.e., the total number of I/O's to maintain the stack is $O(N/B)$, and the memory consumption for the stack is $O(B)$. Thus we obtain an algorithm whose running time is $O(N/B)$ and memory use is $O(B)$, regardless of $D$. I think. $\endgroup$ – D.W. Sep 21 '16 at 18:16
  • $\begingroup$ @D.W. The OP never mentioned anything about writing anything to disk, only queries of $B$ sized blocks. Regardless, how you store stack $S$ is entirely up to you. If you run low on memory you can write the low part of the stack to disk until it's needed again. However, you still need $D$ space to store the stack, whether that's in RAM or disk. $\endgroup$ – orlp Sep 21 '16 at 18:23
  • $\begingroup$ Yes. In the external algorithms setting, it's usually reasonable/safe to assume that there is plenty of additional space on disk available for temporary/scratch storage. My point is that you don't need $B+D$ memory -- it's enough to have $O(B)$ memory and $D$ space on disk. In other words, your (very nice) algorithm can be made to work with even less memory, even when the tree has very large depth. Just noting a further improvement to your already-excellent algorithm. $\endgroup$ – D.W. Sep 21 '16 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.