KD-Tree节点删除异常求助：K近邻查询实现故障排查

问题背景 #

用KD-Tree实现目标点的5近邻查询，采用「查询最近邻→删除该节点→重复查询」的方式，但delete方法仅能删除部分节点，无法正常工作。Airport类包含double类型的latitude（纬度）和longitude（经度）。

现有代码 #

构建树的add方法 #

public void add(Airport airport) { //need to start recursive
    root = addRecursive(root, airport, 0); 
}
private KDNode addRecursive(KDNode current, Airport airport, int depth) {
    if (current == null)
        return new KDNode(airport);
    if (depth % 2 == 0) //Every odd depth we change the axis from x to y
    {
        if (airport.getLatitude() < current.a.getLatitude()) // Compare by x
        {
            current.left = addRecursive(current.left, airport, depth + 1); 
        } else if (airport.getLatitude() > current.a.getLatitude()) 
        {
            current.right = addRecursive(current.right, airport, depth + 1);
        } else {
            return current;
        }
    } else {
        if (airport.getLongitude() < current.a.getLongitude()) // Compare by y
        {
            current.left = addRecursive(current.left, airport, depth + 1); 
        } else if (airport.getLongitude() > current.a.getLongitude()) 
        {
            current.right = addRecursive(current.right, airport, depth + 1);
        } else {
            return current;
        }
    }
    return current;
}

现有delete方法 #

private Airport findSmallestValue(KDNode root) {
    return root.left == null ? root.a : findSmallestValue(root.left);
}

private KDNode deleteRecursive(KDNode current, Airport airport, int depth) {
    if (current == null)
        return null;

    if (airport == current.a)
    {
        if (current.left == null && current.right == null) {
            return null;
        }
        if (current.right == null)
            return current.left;
        if (current.left == null)
            return current.right;
        Airport smallestAirport = findSmallestValue(current.right);
        current.a = smallestAirport;
        current.right = deleteRecursive(current.right, smallestAirport, depth+1);
        return current;
    }

    if (depth % 2 == 0)
    {
        if (airport.getLatitude() < current.a.getLatitude())
        {
            current.left = deleteRecursive(current.left, airport, depth+1);
            return current;
        }
    }
    else
    {
        if (airport.getLongitude() < current.a.getLongitude())
        {
            current.left = deleteRecursive(current.left, airport, depth+1);
            return current;
        }
    }
    current.right = deleteRecursive(current.right, airport, depth+1);
    return current;
}

public void delete(Airport airport) {
    root = deleteRecursive(root, airport, 0);
}

问题分析 #

1. 对象匹配错误：用airport == current.a判断节点是否匹配，这是引用相等判断。如果待删除的Airport是新实例（仅经纬度和目标节点相同），会判断失败，导致无法删除。
2. 最小值查找逻辑错误：findSmallestValue仅递归找左子节点，未考虑KD-Tree的分割轴规则。删除节点时，应根据当前深度的分割轴，在右子树中找该轴上的最小值，而非单纯左子节点。
3. 节点查找路径缺失：递归查找待删除节点时，未处理经纬度等于当前节点的情况。比如在纬度分割轴时，若待删节点纬度等于当前节点，代码直接走右子树递归，会遗漏节点。

修复后的代码 #

第一步：修复节点匹配逻辑 #

给Airport类添加equals方法（或在删除时直接比较经纬度）：

// 在Airport类中添加
@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Airport airport = (Airport) o;
    return Double.compare(airport.latitude, latitude) == 0 &&
           Double.compare(airport.longitude, longitude) == 0;
}

@Override
public int hashCode() {
    return Objects.hash(latitude, longitude);
}

然后修改deleteRecursive中的匹配判断：

// 替换原有的if (airport == current.a)
if (airport.equals(current.a))

第二步：修复最小值查找方法 #

按当前分割轴查找最小值：

private KDNode findMin(KDNode node, int depth, int axis) {
    if (node == null) return null;

    int currentAxis = depth % 2;
    if (currentAxis == axis) {
        if (node.left == null) return node;
        return findMin(node.left, depth + 1, axis);
    }

    KDNode leftMin = findMin(node.left, depth + 1, axis);
    KDNode rightMin = findMin(node.right, depth + 1, axis);

    KDNode minNode = node;
    if (leftMin != null && compareByAxis(leftMin.a, minNode.a, axis) < 0) {
        minNode = leftMin;
    }
    if (rightMin != null && compareByAxis(rightMin.a, minNode.a, axis) < 0) {
        minNode = rightMin;
    }
    return minNode;
}

// 辅助方法：按指定轴比较两个Airport
private int compareByAxis(Airport a1, Airport a2, int axis) {
    if (axis == 0) { // 纬度轴
        return Double.compare(a1.getLatitude(), a2.getLatitude());
    } else { // 经度轴
        return Double.compare(a1.getLongitude(), a2.getLongitude());
    }
}

第三步：修复deleteRecursive方法 #

private KDNode deleteRecursive(KDNode current, Airport airport, int depth) {
    if (current == null)
        return null;

    int currentAxis = depth % 2;
    int cmp = compareByAxis(airport, current.a, currentAxis);

    if (cmp < 0) {
        current.left = deleteRecursive(current.left, airport, depth + 1);
    } else if (cmp > 0) {
        current.right = deleteRecursive(current.right, airport, depth + 1);
    } else {
        // 找到待删除节点
        if (current.left == null && current.right == null) {
            return null;
        }
        if (current.right == null) {
            return current.left;
        }
        if (current.left == null) {
            return current.right;
        }
        // 找到右子树中当前轴的最小值节点
        KDNode minNode = findMin(current.right, depth + 1, currentAxis);
        current.a = minNode.a;
        // 删除右子树中的最小值节点
        current.right = deleteRecursive(current.right, minNode.a, depth + 1);
    }
    return current;
}

额外建议 #

实现K近邻查询时，不需要频繁删除节点。可以直接在KD-Tree查询过程中维护一个大小为K的最大堆，记录最近的K个节点，效率更高，也避免了修改树结构带来的问题。

内容的提问来源于stack exchange，提问作者Артем