Patricia Trees Demystified, Part 2:
Deletions

Examples!: D10 (Simple case 1) --- D11(Case 2, requires swap) --- D 9(case 3, requires swap and pointer redirection)

Definition of Terms
Deletion Node: the node that holds the record to be deleted. The deletion Node is not always deleted, though its record always is. It is not always deleted because in some cases (cases 2 and 3) it is easier to replace the record contained in it, and delete the replacement record's node. Abbreviated as DNode.
Replacement Node: the node that holds the record that will replace the record to be deleted. Only needed in cases 2 and 3, the replacement node will be deleted after its record is swapped for the deletion node's record. Another way to describe the Replacement Node is it is the Deletion Node's Precedent along the search path. Abbreviated as RNode.
Pointer Node: the node that points to the Replacement Node. In case 2, this turn out to be the Replacement Node itself, and, as this is being deleted, is not a needed element. However, in case 3, the Pointer Node must have the link to the record from the Replacement Node follow the record as it moves to the Deletion Node. In this way, the Pointer Node will still point to the proper Record, (which is now in the Deletion Node, not the Replacement Node) as the Patricia tree requires.
Orphan: the orphan is the link that will be lost when a node is deleted. Some links are not necessary to be preserved, for example when a node that is being deleted has a link to itself, that link's target as well as its parent will disappear when the node is deleted. However, the link (the orphan) from a node that is being deleted that points to another node must be retained and reconnected in such a way as to retain the integrity of the tree.
Path: the path is the route followed as the tree is traversed. The Path from the parent node will be to the node to be deleted (abbreviated DPath.) The Path that leads directly to the Node that holds the record to be deleted is abbreviated RPath. The Path that leads to the Replacement Node from the Pointer Node is the Pointer Path, abbreviated PPath.
NotPath: the link that was not taken. It may link to self, or to other nodes.
Parent: the Parent is the direct ancestor (parent) of the node that will actually be deleted. That is, the node to physically be deleted will be the child of the Parent. The child that will be deleted will always be the Path link of the parent. Note that the Parent may (in case 2 or 3, in which the Replacement Node get physically deleted) actually be the Deletion Node. In Case 1, the Parent will be the parent of the Deletion Node.  
Swap: when records are swapped between the Deletion Node and the Replacement node, note that the checkbit for the Deletion Node remains the same as it was. The checkbit does not swap, only the records. Note also that the Deletion Record should be deleted before/when the Replacement node is physically deleted.

Five Steps to deleting a Record

Step One: Find a leaf
A leaf is found in the same way as with insert or search, when you either reach the Dummy, or the current checkbit is not less that the last checkbit.

If you are not yet at a leaf, you follow the search path as with insert: following the value of the test key at the current node's checkbit.

Step two: Ensure correct Record has been found.
Once at a leaf node, the test key must be checked against the node's Record to ensure that the correct Record has been found.
At this point, one returns one stage up the tree, returning that the proper record has been found, or is not present.

Step three: determine the deletion case
After returning from the leaf where you found the proper Record, there are three possible cases:
Case 1: Path = = self. The node with the record to be deleted has no children. This case is determined by the fact that Path = = self. Another way to tell is that the node at the end of Path at which you found the record has the same record as you do.
Case 2: NotPath = = self. The node with the record to be deleted is pointed to by you by Path, but your other child points to yourself. This means you have no "real" children, that all your links are upward branches. This case is most easily handled by replacement, where you are the Replacement Node. You will give your record to the Deletion Node, and the you will get physically deleted.
Case 3: Neither of the above cases fit. The node with the record to be deleted is pointed to you by Path, but you have real children pointed to by NotPath. These children must be kept in the tree after your deletion. Again, this case is most easily handled by replacement, where the Deletion Node will get your record, and you, the Replacement Node, will get physically deleted.

Step four: Handle orphan link, swap if needed..
Case 1: the Orphan is simply NotPath. Send that back up to Parent, with notice that you are ready to be deleted.
Case 2: the Orphan is simply Path. After swapping records with the Deletion Node, send Path back up to parent, with notice that you are ready to be deleted.
Case 3: the Orphan is NotPath. After swapping records with the Deletion Node, you need to find out who points to you (since in this case you don't point to yourself). Whoever this Pointer Node turns out to be, tell them they should now point to the Deletion Node, since that now holds your record. Then send NotPath back up to Parent, with notice that you are ready to be deleted.
You now return control back to the Parent.

Step five. Parent deletes child, adopts Orphan
Once control returns to the Parent, the Parent will delete the child node along Path, and reset that link to Orphan. The deletion process is now complete.

Examples!: D10 (Simple case 1) --- D11(Case 2, requires swap) --- D 9(case 3, requires swap and pointer redirection)