> You can get rid of any stacks whatsoever by keeping a parent pointer in the tree node data structure. Effectively, this turns the tree into a (sort of) state machine. While traversing, you need no memory other than the current and previous node/state. The traversal algorithm is very simple:
While this sounds innocent, truly consider the ramifications of this decision.
Your node has now grown to be +8 bytes (the size of a 64-bit pointer). If you have 1-million nodes in your binary tree, you are using +8MB of memory.
-------
Lets consider the alternative: lets say you have 1-million nodes, and you have a red-black tree (imperfect balance: instead of a perfectly balanced 20-depth tree you have some branches which are 40-depth).
Traversing to 40-depth requires 40x pointers on the stack, or 320 bytes.
----------
In effect, you're spending 8-bytes per node (which could be millions, or even billions of nodes), to save log2(depth) space off of your stack frame.
While the state-machine is very "clean", it seems like a very bad tradeoff from an algorithmic / memory space point of view. I'd rather spend log2(depth) space on the stack, rather than O(+8 bytes * number nodes) in the heap.
I think there's something to be said about the clarity and cleanliness of the state-machine design. Its quite possible that some algorithms are easier to write with this "parent pointer in node" methodology. However, anyone seeking the highest performance per unit-memory will have to see that the +8 bytes per node is a terrible, terrible tradeoff.
-------------
> Update: Todd Lehman pointed out that given node-level locks, this algorithm allows concurrent traversal and update of the tree. Any atomic operation other than detaching a non-leaf node is safe.
Hmm... the parallel-angle I haven't thought about. But it does seem to be a potential building block as maybe even a lock-free data-structure.
Or just use locks, since locks are easier to think about.
Insertion and deletion into the tree seems possible, but "rebalance" is very difficult for me to think about (since it possibly requires modifying many, many nodes). Locking all nodes involved would be a heavy approach and probably work.
Red-black colors are kept track of for self-balancing purposes. Maybe more colors are needed to make the methodology "clean" for multi-threaded / lock free purposes.
While this sounds innocent, truly consider the ramifications of this decision.
Your node has now grown to be +8 bytes (the size of a 64-bit pointer). If you have 1-million nodes in your binary tree, you are using +8MB of memory.
-------
Lets consider the alternative: lets say you have 1-million nodes, and you have a red-black tree (imperfect balance: instead of a perfectly balanced 20-depth tree you have some branches which are 40-depth).
Traversing to 40-depth requires 40x pointers on the stack, or 320 bytes.
----------
In effect, you're spending 8-bytes per node (which could be millions, or even billions of nodes), to save log2(depth) space off of your stack frame.
While the state-machine is very "clean", it seems like a very bad tradeoff from an algorithmic / memory space point of view. I'd rather spend log2(depth) space on the stack, rather than O(+8 bytes * number nodes) in the heap.
I think there's something to be said about the clarity and cleanliness of the state-machine design. Its quite possible that some algorithms are easier to write with this "parent pointer in node" methodology. However, anyone seeking the highest performance per unit-memory will have to see that the +8 bytes per node is a terrible, terrible tradeoff.
-------------
> Update: Todd Lehman pointed out that given node-level locks, this algorithm allows concurrent traversal and update of the tree. Any atomic operation other than detaching a non-leaf node is safe.
Hmm... the parallel-angle I haven't thought about. But it does seem to be a potential building block as maybe even a lock-free data-structure.
Or just use locks, since locks are easier to think about.
Insertion and deletion into the tree seems possible, but "rebalance" is very difficult for me to think about (since it possibly requires modifying many, many nodes). Locking all nodes involved would be a heavy approach and probably work.
Red-black colors are kept track of for self-balancing purposes. Maybe more colors are needed to make the methodology "clean" for multi-threaded / lock free purposes.