remove method
void
remove(
- dynamic point
Remove the Node from the K-d Tree
Implementation
void remove(point) {
var node;
Node? nodeSearch(Node? node) {
if (node == null) {
return null;
}
if (node.obj == point) {
return node;
}
var dimension = _dimensions[node.dimension];
if (point[dimension] < node.obj[dimension]) {
return nodeSearch(node.left);
} else {
return nodeSearch(node.right);
}
}
void removeNode(Node node) {
var nextNode, nextObj, pDimension;
Node? findMin(Node? node, dim) {
var dimension, own, left, right, min;
if (node == null) {
return null;
}
dimension = _dimensions[dim];
if (node.dimension == dim) {
if (node.left != null) {
return findMin(node.left, dim);
}
return node;
}
own = node.obj[dimension];
left = findMin(node.left, dim);
right = findMin(node.right, dim);
min = node;
if (left != null && left.obj[dimension] < own) {
min = left;
}
if (right != null && right.obj[dimension] < min.obj[dimension]) {
min = right;
}
return min;
}
if (node.left == null && node.right == null) {
if (node.parent == null) {
_root = null;
return;
}
pDimension = _dimensions[node.parent!.dimension];
if (node.obj[pDimension] < node.parent?.obj[pDimension]) {
node.parent?.left = null;
} else {
node.parent?.right = null;
}
return;
}
// If the right subtree is not empty, swap with the minimum element on the
// node's dimension. If it is empty, we swap the left and right subtrees and
// do the same.
if (node.right != null) {
nextNode = findMin(node.right, node.dimension);
nextObj = nextNode.obj;
removeNode(nextNode);
node.obj = nextObj;
} else {
nextNode = findMin(node.left, node.dimension);
nextObj = nextNode.obj;
removeNode(nextNode);
node.right = node.left;
node.left = null;
node.obj = nextObj;
}
}
node = nodeSearch(_root);
if (node == null) {
return;
}
removeNode(node);
}