Compressed Trie - Patricia/Radix tries

TODO
https://kukuruku.co/post/radix-trees/

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Text/trie02.html
A radix tree (also patricia trie or radix trie or compact prefix tree) is a space-optimized trie data structure where each node with only one child is merged with its child.
A compressed trie is a trie with one additional rule:

Each internal node has   ≥ 2   children

Such compacted trie is als known as:

Patricia tries or Radix tries

Converting a standard trie to a compressed tree

• Redundant node:
  

  An internal node v is redundant if Node v is not the root node,       and          Node v has 1 child node

Redundant chain of edges:

A chain of edges: (v0,v1), (v1,v2), ..., (vk−1,vk) is redundant if: Nodes   v1, v2, ..., vk−1   are redundant Nodes   v0   and   vk   are not redundant

Compression algorithm:

Replace: a redundant chain or edges   (v0,v1), (v1,v2), ..., (vk−1,vk)         by one edge: (v0 ,vk)            Replace: the label vk         by the label: v1 v2 ... vk

• • Before compression: After compression:

http://self-learning-java-tutorial.blogspot.com/2015/01/compressed-trie-radix-trie.html

Compressed trie is a trie with only one addition rule such that, every internal node must have≥ 2 children.  Compressed trie is also known as Radix trie (or) Patricia trie.

Trie shown in above figure converted to compressed trie like below.

https://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/tries.htm
http://www.sanfoundry.com/java-program-patricia-trie/
https://github.com/mlarocca/Algorithms/blob/master/PatriciaTrie.java
https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/trie/PatriciaTrie.html
http://grepcode.com/file/repo1.maven.org/maven2/com.groupbyinc/common-utils/23/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java#AbstractPatriciaTrie