This patent, filed in 1997, claims deletion of a node C in a Patricia tree by ``identifying a node B immediately preceding node C in the path to node C, and replacing the node C in the tree with node B.''
This isn't new. It's exactly how nodes are deleted from Patricia trees in the open-source BSD routing software (published around 1990, and described in Sklower's 1993 paper ``A tree-based routing table for Berkeley Unix''), for example, and in the radix_remove function in the Multi-threaded Routing Toolkit published in 1995.
Some specific quotes from the patent:
Patricia trees have one great disadvantage. Until now, to my knowledge, no one has discovered any reasonable method of deleting nodes in a Patricia tree.In fact, this deletion algorithm was published years before the patent application and is mentioned at several points in the literature.
Sedgewick and Knuth, for example, describe in detail the algorithms for building, searching and inserting nodes into a Patricia tree. However, the problem of deleting nodes is not even mentioned.False. Knuth doesn't mention fast deletion, but Sedgewick does.
In all instances known to me of the use of a Patricia tree, nodes are deleted by rebuilding the entire tree.Your ignorance does not justify a patent.
I have discovered that Patricia tree nodes may be deleted by always selecting as the replacing node the node immediately prior to the deletion node in the unique path to the deletion node. Once the replacing node is determined in this manner, the deletion node is easily removed by simple pointer adjustments of the affected surrounding nodes. Using my invention, nodes may be deleted in time consistent with node insertion time. This, in turn, means that it is now practicable to use Patricia trees in dynamic situations in which nodes are created and deleted frequently.This ``discovery'' is not new. The use of Patricia trees in ``dynamic situations'' such as routing tables was standard years before the patent.