splay-tree icon indicating copy to clipboard operation
splay-tree copied to clipboard

adds removeNode

Open shaunc opened this issue 7 years ago • 1 comments
trafficstars

This adds removeNode (which was in doc but not implemented). This allows the replacement of a node with particular data, given a tree with duplicates.

It uses the first remove strategy in the wikipedia article, as splay() only works up to key equality. It also uses removeNode() to implement remove(): arguably (depending on use case), splaying on removal won't help search performance.

Experimental "findParent" to find the parent of a node also added (though I haven't written tests for it separately -- it is used in removeNode for the case that the removed node is a leaf).

shaunc avatar Oct 15 '18 16:10 shaunc

Thanks a lot! Let me take a look at the findParent to understand it better, and run the benchmarks

w8r avatar Oct 17 '18 21:10 w8r