3 ms·

You add integer slots to each node and store the index of the child nodes in them. So you have, for a binary tree, [actualTreeNodeData1,child1Idx,child2Idx][

• rocqua 7y ago
  That feels like it'll start hurting when you don't know the (maximum) degree of your nodes. As you won't have fixed-size object anymore.
  • vnorilo 7y ago
    Typically you'd have a handful in-object and a heap allocated tail if needed. A bit like small string optimization.
  • silasdavis 7y ago
    Hurting because of memory alignment or something else? Given we have indices along the serialisation for child nodes I would have thought not having nodes start at the consistent intervals doesn't hurt us for traversal at least. I'd quite like to use this idea for a file backed immutable tree. The array of children would have variable size with bit field to index then nth child in the sparse array.
    • rocqua 7y ago
      Constant time array indexing depends on a fixed array member size. So, the actual memory layout of storing the nodes with non-fixed size could not use an array of nodes. I suppose you could (should) write your own allocator to ensure nodes are allocated in a contiguous piece of memory, and have a separate array of indexes / pointers that tells you where the n-th node starts. That is another array that'll have to be kept in cache though.