w8r / splay-tree

Fast splay-tree data structure
https://npm.runkit.com/splaytree
114 stars 18 forks source link

Remove method sometimes fails to remove the minimum node #42

Closed BrandonQDixon closed 6 months ago

BrandonQDixon commented 6 months ago

Sometimes, in the case where I attempt to retrieve and remove the minimum node from the tree, which I've just retrieved, the removal fails to take place.

Here is a minimal reproduction of my code:

const cellTree = new SplayTree<HexokuCellConstraint>(
    HexokuCellConstraintComparator.bind(HexokuCellConstraintComparator, visitor)
);
for (const cell of cells) {
    cellTree.insert(cell);
}

/** ... unrelated code omitted ... **/
const cell = cells.min()!;
const tmpOne = cells.size;
cells.remove(cell);
const tmpTwo = cells.size;

console.log(`${tmpOne} <> ${tmpTwo}`); // 7 <> 7 (indicating nothing happened)
BrandonQDixon commented 6 months ago

Please disregard, surprisingly, the comparator that I'm using is causing some kind of issue with how the tree internally structures itself. I became suspicious after seeing the same behavior in other libraries.

w8r commented 6 months ago

Cheers!