Radix and ternary trees

Questions 1 to 5 of 7

1. 1. Under the rule in the radix tree lesson, which nodes must stay in the tree?

   Pick every answer that is true.

   A node with one child and no word endingThe rootA node where a word endsA node with two or more childrenA node whose label is longer than three letters
2. 2. On the EFF list of 7,772 words, which statements are true?

   Pick every answer that is true.

   The radix tree stores fewer letters than the plain trieThe radix tree has 11,384 nodesThe radix tree saves 55.6 percent of the lettersThe plain trie has 25,638 nodes, and the radix tree saves 14,254 of them
3. 3. A radix tree holds car. What happens when you insert cat?

   The edge car is split at ca, which becomes a node with two children, r and tcat is added as a second edge from the root, so the root has two edges that start with cThe label car is replaced by cat, so car can no longer be foundcar stays whole and cat becomes a plain chain of single-letter nodes under the root
4. 4. On the five words cat, car, card, care and dog, the ternary search tree has exactly one node fewer than the array trie. Why?

   The TST drops the last letter of every wordEach TST node holds three letters, so it needs one node fewer per wordThe array trie counts every word twice, once for the insert and once for the end flagThe array trie has one extra node for the empty prefix at the root, and the TST has no root letter
5. 5. True or false: a ternary search tree node has three links whatever the alphabet size, so its memory does not grow with the alphabet.

   False, because a TST node needs one slot for each letter in the alphabetTrue, because each node keeps a left, mid and right link, and that count does not depend on how many letters exist