Re: proper deletion algorithm for Patricia trie

In article <2005081117573916807%pafriend@octavianorg>, Peter Friend
<pafriend@xxxxxxxxxxxx> writes
>I have been working on a Patricia trie implementation for storing
>counts of version 4 IP addresses. When the count reaches 0, I need to
>delete the node.
>
>I am using a variant that contains no NULL links. The deletion cases I
>think I need to handle are:
>
>1. node has left and right pointers that point up to the node itself
>2. the left or right pointer points to the node itself
>3. the node is internal, and both branches point down the tree
>
>Cases 1 and 2 are straightforward. The third case is trickier, and I
>have it working *most* of the time, but I am missing something.
>
I Have played a bit with Patricia trees: see http://www.mcdowella.demon.
co.uk/Patricia.html, which has a link to a zip file of C++ and the
following text:

Delete is trickier. If you are lucky, the node you wish to delete will
have at most one link to a node other than itself. These cases are easy
edits. If your node has two pointers out to nodes other than itself,
some node further down the tree must have an up pointer to it. It turns
out that if you take this second node and change its bit offset to that
of the node to be deleted, you can shove it in where the node to be
deleted was with only a few pointer changes, and still have a valid
Patricia tree afterwards.

There is also a Java class uk.co.demon.mcdowella.algorithms.Patricia in
a zip file of miscellaneous Java stuff described in http://www.mcdowella
..demon.co.uk/programs.html. The Java implementation uses slightly more
space per node, but is simpler. Also the C++ implementation uses user-
provided callbacks to return bits to it and is designed to throw
std::logic error if the bits given for a node change over time. This is
not a good idea, because it can happen inside the destructor of a
Patricia tree.
--
A.G.McDowell
.