For the access operation, it should take advantage of contiguous memory (memory locality) somehow which I am having a hard time determining how that should work for a tree.
The generalized solution I use nowadays which isn't necessarily optimal (the optimal solution depends on use case as pointed out, and you can get extremely compact with some further assumptions, but this keeps the assumptions minimal, and also works for N-ary trees and unbalanced ones), but at least achieves locality of reference in nodes frequently accessed together and reasonable compactness is a two-pass approach (the first pass is just concerned with building the tree, the second pass traverses it and optimizes for locality of reference).
The first aspect of the solution is that it does store all the nodes contiguously in one array (ex:
std::vector in C++ or
ArrayList in Java) for the entire tree. The
parent->child links are not stored as 64-bit pointers prone to invalidation (if the array needs to be resized) but 32-bit indices, and halving the size there of the links also tends to translate to more neighboring nodes being able to fit into a cache line.
// Child links as indices into the nodes array. -1 is
// used in place of a null pointer.
// The array storing all the nodes for the tree.
Now depending on how the tree is built, the links could be pointing all over the place into the array, skipping around a lot for your common case traversal patterns.
So I have a second pass inside a copy constructor which creates a copy of the tree, and the copy constructor traverses the tree in a way that aligns with the critical execution paths and inserts the nodes in that traversal order. That has the effect, with this approach, of putting nodes frequently accessed together during a traversal right next to each other in this
If the tree is prone to be updated (insertions and removals) often, and I still want to improve spatial locality (I'd need to see some hotspots to consider even doing this for a dynamic use case), then I might periodically do this copy construction pass to optimize its memory layout when the tree is marked as having been changed and swap the optimized copy with the original.
I have a little thing I whipped up for another question using this technique of optimizing linked structures for locality of reference, and again it's not optimal but easy to implement and a very generalized "decent" solution. Here it is in GIF form with half a million agents moving around per frame with collision detection (which involves half a million queries into the spatial index per frame) and the CPU rasterization all happening in one thread at over 100 FPS (something unfortunately not communicated well in the GIF, and the frame rates do drop a bit when I zoom out all the way to see all half a million agents at once, but that's due to the rasterization rather than the link traversal), and its performance is largely the result of this sort of LOR optimization using this "links as indices into one array" approach for the spatial index used for collision detection:
Again I could do better than this (just a quick 2-hour implementation for an SO question and I deliberately wrote the code single-threaded and simple to make it easier to understand) if I made further assumptions that created a more tailored structure, but this is a quick and lazy sort of approach which works for any kind of linked structure. You can also create linked lists this way using an array with indices as links to skip around.
The linked list storing nodes in a contiguous array:
Removing an element from the middle in constant-time:
Inserting a new element:
And you can see the spatial locality of traversal degrades when we do things like insert and remove to/from the middle of the linked list (because constant-time insertions to middle are actually appending to the back of the array), but that spatial locality is quickly restored by simply copying the list which traverses it in order and inserts to the copy in traversal order. It's the same approach here with the doubly-linked list node looking like this:
// Using -1 in place of a null.
// Stores all the nodes for the linked list in one array.
// Stores an index to the first removed node in the array to reclaim
// on subsequent insertions, or -1 if there are no removed (free) nodes.
It's somewhat combining what you'd get with a free list allocator and a separate linked list implementation from the allocator, but combined into one data structure with a much simpler and less error-prone implementation with half the size of the links on 64-bit architectures. These days I barely use custom allocators because I find it so much simpler to just consolidate the concerns of efficient memory allocation and memory layout into the data structure itself without fiddling with allocators (about the only reason I use custom allocators these days is for non-performance-related reasons, like being able to superficially impose a limit on the amount of memory an allocator can allocate to test to make sure out of memory exceptions are handled properly in tests).
Same thing for like a quadtree:
// Stores all the nodes for the tree.
... though for quadtrees I prefer this rep and find I get better performance out of it (even though it can create more nodes than necessary, the nodes end up being much smaller in size):
// All four children are always stored contiguously, so we
// only need the index of the first child.
And so forth. I use the same approach for any linked structure these days which needs to be reasonably efficient and avoid cache misses all over the place but not like as efficient as possible (I do use much more complex approaches for things like offline rendering which has the most critical performance requirements with its bounding volume hierarchy).
The very first thing you need is one array to store all the nodes since that's going to be a practical requirement as far as memory allocation to have any kind of spatial locality. Then you can just use indices instead of pointers. Finally when you get to that stage, you realize a copy construction pass can just insert nodes in traversal order to get nodes you frequently traversed together right next to each other in memory (in the array) for the copy.