I have partially implemented a Patricia Trie, it's still not complete since it lacks a delete/remove function which is used to remove nodes from the Trie, I have found this article describing the structure, which comes with an implementation in C++, there's a remove/delete function, but I can't figure out what's the idea behind the implementation.
How do I remove a node from the Trie and leave the Trie in a proper state?
I've implemented a PATRICIA in C recently. In order to remove a node, find the down-trie node which points backward up the trie to the victim (this may be the victim node itself.)
Once found, if the victim node is NOT the backward-referer, switch the victim with its referer. This puts the victim close to being a "leaf" node, and its backward reference will be to itself. The removal is very simple, then.