如何删除Patricia树节点

Question

如何从Patricia中删除节点？Patricia，我特别指的是基数二树，它的节点指向树上以结束搜索。

Answer 1

在我的Java实现中，这是这样做的：

/**
* Removes the key from the set if the key is present.
* @param key the key
* @throws IllegalArgumentException if {@code key} is {@code null}
* @throws IllegalArgumentException if {@code key} is the empty string.
*/
public void delete(String key) {
if (key == null) throw new IllegalArgumentException("called delete(null)");
if (key.length() == 0) throw new IllegalArgumentException("invalid key");
Node g;             // previous previous (grandparent)
Node p = head;      // previous (parent)
Node x = head;      // node to delete
do {
g = p;
p = x;
if (safeBitTest(key, x.b)) x = x.right;
else                       x = x.left;
} while (p.b < x.b);
if (x.key.equals(key)) {
Node z;
Node y = head;
do {            // find the true parent (z) of x
z = y;
if (safeBitTest(key, y.b)) y = y.right;
else                       y = y.left;
} while (y != x);
if (x == p) {   // case 1: remove (leaf node) x
Node c;     // child of x
if (safeBitTest(key, x.b)) c = x.left;
else                       c = x.right;
if (safeBitTest(key, z.b)) z.right = c;
else                       z.left  = c;
}
else {          // case 2: p replaces (internal node) x
Node c;     // child of p
if (safeBitTest(key, p.b)) c = p.left;
else                       c = p.right;
if (safeBitTest(key, g.b)) g.right = c;
else                       g.left  = c;
if (safeBitTest(key, z.b)) z.right = p;
else                       z.left  = p;
p.left = x.left;
p.right = x.right;
p.b = x.b;
}
count--;
}
}