Radix and ternary trees

Questions 1 to 5 of 7

1. 1. A plain trie for the words car, card, care and cat has 7 nodes, counting the root. The radix tree for the same words keeps 6 nodes. Which node is merged away?

   carcaccat
2. 2. In the 50,000-word benchmark, the array trie uses 23,155,956 bytes and the ternary search tree uses 4,288,120 bytes. About how many times less memory does the ternary tree use?

   About 2 timesAbout 5.4 timesAbout 10 timesAbout 108 times
3. 3. Why does a radix tree keep a node that has only one child?

   It is a word end, so the tree must record that the word is storedThe root needs it to point to a childIt holds a letter that cannot be moved into an edge labelEvery node with one child is a branch by definition
4. 4. In a ternary search tree lookup, the letter you want is smaller than the letter in the current node. Which link does the lookup follow?

   eqlohiend
5. 5. A radix tree stores fewer letters than the plain trie for the same words, because the merged nodes drop their letters. Is that statement true?

   True, because the merged nodes drop their lettersFalse, because the letters move into the edge labels, and the label letters equal the plain node count minus the root