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 In order to enforce the above rule, the labels are generalized: Each node is labeled with a string (multiple characters) (The label used to be a single character) Converting a standard trie to a compressed tree Redundant node: Node v is not the root node, and Node v has 1 child node Example: 0 ,v 1 ), (v 1 ,v 2 ), ...,
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment