Re:Tree traversal without recursion: the tree as a state mac...
by alkonaut on Tuesday September 03, 2019 @05:19AM
(#20864872)
It seems like by adding parent pointer one is shifting complexity from the traversal into the data structure, in order to avoid a stack. I know there are places where avoiding an explicit stack can be nice (perhaps a BVH tree in a shader or other places where constant space is required?) but are there more good reasons for it?
A DAG (such as a singly linked tree) has so many benefits for memory safety, GC performance, ability to extend it from a binary tree to N children etc., that it seems like an odd tradeoff in most scenarios.
[ Parent
| on HN ]
Re:Tree traversal without recursion: the tree as a state mac...
by HelloNurse on Tuesday September 03, 2019 @08:55AM
(#20866002)
Obviously, adding read-only data in the tree and to save mutable data in the traversal state can be amortized if we have many ongoing traversals rather than one. For example, in a massively parallel GPU computation running an arbitrary number of tree searches simultaneously in a fixed memory amount.