How is a Patricia tree node deleted?

Question

How do you delete a node from Patricia? By Patricia I specifically mean the radix two tree that has nodes pointing back up in the tree to end the search.

Answer 1

In my Java implementation, this is done like that :

       /**
        * 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--;
          }
       }