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);
}