Re: proper deletion algorithm for Patricia trie

On 2005-08-11 22:11:44 -0700, "A.G.McDowell" <mcdowella@xxxxxxxxxxxx> said:

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.

I actually did find your site during my search, which is where I got the idea for copying the bit offset around. The reason deletion was not working properly was rather dumb. The variant I had coded used no NULL links. The result is that eventually you will end up trying to delete a node which has more than one link pointing up the tree to it, which effectively makes deletion impossible to implement in a sane fashion. One I changed my implementation to handle null links, the property of only one up pointing link to each node was restored, and deletion works properly now.

Peter

.

Relevant Pages

  • Re: hacker challenge - traverse a list
    ... Here is a little challenge - print the contents of a binary tree ... I assume there are no up links, otherwise the algorithm is trivial. ... space hence unbounded number of bits in a pointer? ... Left branch *not* leaf, rotate: ...
    (comp.programming)
  • Re: question of style
    ... end of the day the quality of the code depends more on the quality of ... or the equivalent null pointer exceptions in Java, C, or whatever? ... But you have implemented a mutable tree. ...     def get: ...
    (comp.lang.python)
  • Re: Help me come up with a few and simple programming challenges
    ... >Dave Vandervies wrote: ... >> language, I'd probably pass around a pointer to the list's head pointer ... >(define (sublist tree lo hi) ...
    (comp.lang.scheme)
  • Re: Reading XML stream using unmanaged c++
    ... You don't need a back pointer to implement tree structures. ... but a back pointer is a handy thing to have when using a DOM node. ... XML is metadata, but an XML document is an XML metadata structure with actual data ...
    (microsoft.public.vc.mfc)
  • Re: Disable File Deletion on WMX?
    ... I was able to do disable file deletion with this pointer on where to ... Under Network Sharing & Security, ... Share this folder on the network ...
    (microsoft.public.windows.mediacenter)