我想使用三元搜索树中的键删除特定节点。这在大多数情况下工作得很好，但在我的一些测试集中，没有中间子节点的节点也不会存储值，这是不应该发生的。
我尝试了在网上找到的不同方法，但几乎所有这些方法都使树处于肮脏状态，这使得搜索变得很麻烦，因为你需要检查你找到的叶子是否确实具有值，这应该'不会发生。
这是我的相关代码
private boolean hasChildren(Node x) {
return (x.left != null || x.mid != null || x.right != null);
}
private void reHang(Node x) {
if (hasChildren(x)) {
if (x.left != null) {
x.parent.mid = x.left;
x.left.right = x.right;
} else if (x.right != null) {
x.parent.mid = x.right;
}
}
}
private boolean remove(Node x, String key, int d) {
if (x == null) return false;
char c = key.charAt(d);
if (c < x.c) {
if (!remove(x.left, key, d)) {
x.left = null;
}
} else if (c > x.c) {
if (!remove(x.right, key, d)) {
x.right = null;
}
} else if (d < key.length() - 1) {
if (!remove(x.mid, key, d + 1)) {
x.mid = null;
if (x.val != null) return true;
}
} else {
x.val = null;
}
reHang(x);
return hasChildren(x);
}
private class Node
{
private Value val;
private char c;
private Node left, mid, right, parent;
}
具体来说，我用于前缀查找的这个函数出现了问题:
private Node getMidPath(Node x) {
if (x.left != null) return getMidPath(x.left);
if (x.mid == null) return x;
return getMidPath(x.mid);
}
每个没有 x.mid 的节点都应该有一个 x.val 集，但删除后情况并非总是如此，这意味着我有脏节点。
任何帮助将不胜感激。
最佳答案
您必须看到一棵三叉树，它是:一些嵌套的二叉树，但每个级别只有一个字符作为键而不是整个字符串。沿着二叉树向下走，直到字符串耗尽。在这里，您将有两个最终引用，一个是实际数据，另一个是具有相同前缀的较长字符串的实际子树。现在将数据设置为空。当子树引用为空时，删除该节点。当现在整个子树为空时，继续使用前一个字符的子树。这里将子树引用设置为 null。现在两个引用都为空，删除该节点。当现在整个子树为空时，继续使用前一个字符的子树。等等
关于java - 正确删除三元搜索树中的节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56210684/