in C++ STL's term, don't invalidate iterators on removal of elements, except those pointing to the removed node.
(if the nodes returned in various APIs are to be regarded as "iterators", with the assumption that users don't tamper with it, which is common in the javascript world)
the modification is rather straightforward. in remove function, instead of assigning the data
and key
of the "lifted node" to the "deleted node", maintain the left, right, parent
references to/from the "lifted node" and cut the "deleted node"'s outward references (but preserve the key and data).
within my knowledge of the currently implemented APIs, the remove operation is the only one that breaks this. (more care may be needed if split, join
are to be added)
this allows iterator usages to work (there might not be much, but i really have code using iterators the iterator way). without this property, though workaround exists, one has to find by .key
, prev/next, store .key
again and again, that's hurts both readability (+code size) and overall performance.
also returning the node deleted makes more sense (may be inserted again with the fictional insertNode
API).
there might be performance degradation due to more operations to do. but since the remove operation is the fastest operation here, it's nice to have this property with a little price. or maybe removeGracefully
?