Looking at the delete() method inside the Node class in your IntervalTree, and noticed your TODO comment:
//TODO: Should we rewire the Nodes rather than copying data?
// I suspect this method causes some code which seems like it
// should work to fail.
I was also looking at Java 7 TreeMap source code and they also use a Red-Black Tree based implementation, wondering if taking a cue from there you would want to slightly change your delete() implementation like so:
private boolean delete() {
if (isNil()) { // Can't delete the sentinel node.
return false;
}
Node y = this;
if (hasTwoChildren()) { // If the node to remove has two children,
y = successor(); // copy the successor's data into it and
copyData(y); // remove the successor. The successor is
maxEndFixup(); // guaranteed to both exist and have at most
} // one child, so we've converted the two-
// child case to a one- or no-child case.
Node x = y.left.isNil() ? y.right : y.left; // replacement
if(!x.isNil()) { // if (replacement != null)
x.parent = y.parent;
if (y.isRoot()) {
root = x;
} else if (y.isLeftChild()) {
y.parent.left = x;
y.maxEndFixup();
} else {
y.parent.right = x;
y.maxEndFixup();
}
if (y.isBlack) {
x.deleteFixup();
}
} else if(y.parent.isNil()) { // return if we are the only node.
root = nil;
} else { // No children. Use self as phantom replacement and unlink.
if (y.isBlack)
y.deleteFixup();
if (!y.parent.isNil()) {
if (y.isLeftChild())
y.parent.left = nil;
else if (y.isRightChild())
y.parent.right = nil;
y.parent = nil;
}
}
size--;
return true;
}
Looking at the delete() method inside the Node class in your IntervalTree, and noticed your TODO comment:
I was also looking at Java 7 TreeMap source code and they also use a Red-Black Tree based implementation, wondering if taking a cue from there you would want to slightly change your delete() implementation like so: