I am trying to consolidate my understanding of the difference between a patricia trie (radix tree with r = 2) and a binary trie. As far as I can see the implementation of a binary trie and a patricia trie (radix tree with r = 2) are identical?
Just for context, I understand fully how to implement radix trees and have written classes and tests for said implementations, I just don't understand how the implementations for a patricia trie (radix tree with r = 2) is different from a binary trie.
I have 2 separate guesses that I would like feedback on regarding the difference:
- In a patricia trie (radix tree with r = 2) a node branch can have an edge key that is inside the set
K = {0,1}with values inside the setV = {null, node<pointer>}(due the binary radix constraint); if there is a parent that only has single children descendants all the way down to the leaf (singly-linked list shaped subtree), the final edge pointing to a leaf node (which is also a word terminator node) can be a series of bits (e.g.10010). This makes sense to me when writing this now because this would offer an explanation to what makes this a radix tree (a compression has been applied). - No compression difference between a binary trie and patricia trie (radix tree with r = 2). The only difference is that word termination nodes have value attributes holding an entire string of an added word. This could make sense because the difference may be that a binary trie only stores characters of inserted word by edges whereas patricia stores words at the terminator nodes as well as the edges. The problem with this guess is that how exactly is the patricia trie an optimised version compared to the binary trie? We have simply added to our space complexity.
I feel there are subtle details I am missing that could help me fully grasp the differences with confidence. I would appreciate any help!