proper deletion algorithm for Patricia trie

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.

Since the tree is being used to store IP addresses, I have a fixed length array for storing the path taken to the matching node. For case 3 I copy the skip value from the matching node to the previous node in the path (which points to the matching node). I then replace the matched node with the node that points to it, and adjust pointers. The pointer adjustments are where I think I am missing a case.

I haven't found a Patricia delete algorithm online, or in my books, though I would expect it to be similar to deletion in a trie without the path compression. Hints or pointers to any relevant papers would be appreciated.

Thanks in advance,

Peter


.

Relevant Pages

  • Re: Reading in a file into a Linked List - Segmentation Fault
    ... > Victor Bazarov wrote: ... >> Here you store that address. ... >> which in itself can take all fun out of studying pointers. ... So, it's not storing _values_, it's storing ...
    (comp.lang.cpp)
  • Re: C++ Implementation of Lisp
    ... But you're complaining that storing your type by value is onerous, ... Your heavyweight object is the ... value-oriented container library, BY DESIGN. ... problem to smart pointers. ...
    (comp.lang.lisp)
  • Re: RWList pass by reference -probkem
    ... If you do a simple change and store pointers instead of just ... Changing from storing values to storing pointers is never *a simple change*. ... RWListIter works, ... If something is passed by reference, then nothing is copied at all. ...
    (comp.lang.cpp)
  • Re: Inheritance design issue - solved
    ... This also makes my question a pretty useless one, ... storing the 'derived' pointers as 'base' pointers, I would do exactly what I ... So now I came up with having a common base class to ...
    (comp.lang.cpp)