6 TRIES AND ADAPTING DATA STRUCTURES

Question 1

What is a binary search tree?

Answer 1

A data structure that organizes data based on less-than or greater-than comparisons.

Question 2

What is the main problem addressed in the chapter?

Answer 2

Storing and searching strings in trees.

Question 3

What is a trie?

Answer 3

A data structure that branches on a single character of the string at each level.

Question 4

How do binary search trees store strings?

Answer 4

By sorting elements in alphabetical order.

Question 5

What is the cost of comparing strings in a binary search tree?

Answer 5

It scales with the length of the strings.

Question 6

What is the main advantage of using tries over binary search trees for strings?

Answer 6

Tries allow for more efficient searching by partitioning strings based on prefixes.

Question 7

What does each node in a trie represent?

Answer 7

A prefix of the string.

Question 8

How many branches can a trie node have for English words?

Answer 8

Up to 26 branches, one for each letter of the alphabet.

Question 9

What is an internal node in a trie?

Answer 9

A node with at least one child.

Question 10

What is a leaf node in a trie?

Answer 10

A node without any children.

Question 11

What indicator is used to determine if a trie node represents a valid entry?

Answer 11

A Boolean is_entry.

Question 12

True or False: Every node in a trie represents a valid entry.

Answer 12

False.

Question 13

What is the purpose of the root node in a trie?

Answer 13

It indicates the start of the string.

Question 14

How does searching in a trie differ from searching in a binary search tree?

Answer 14

In a trie, we choose branches based on the next letter in the string.

Question 15

Fill in the blank: A trie allows for _______ splits at each node.

Answer 15

many-way

Question 16

What does the trie data structure optimize for?

Answer 16

The additional structure in strings.

Question 17

What is the analogy used to describe a trie?

Answer 17

An ultimate real-world filing system.

Question 18

What does the term ‘partitioning function’ refer to in the context of tries?

Answer 18

It creates multi-way splits over the next character in the string.

Question 19

What is a major drawback of binary search trees when used for string data?

Answer 19

The cost of string comparisons is higher than that of numbers.

Question 20

What is the significance of the sequential nature of string comparisons?

Answer 20

We start at the first character and compare until a difference is found.

Question 21

What happens when a trie contains strings with overlapping prefixes?

Answer 21

Some internal nodes may not represent valid entries.

Question 22

How does a trie handle nodes with prefixes that are not valid entries?

Answer 22

It indicates this with a False value for is_entry.

Question 23

What is the role of the Trie object in relation to the root node?

Answer 23

It wraps the root node and manages additional bookkeeping.

Question 24

What is a characteristic of the branches in a trie?

Answer 24

They only create nodes for non-empty branches.

Question 25

What is the first step in the trie search process?

Answer 25

Check the first character for a match

Question 26

How does the trie search process differ at the second level?

Answer 26

Check the second character for a match

Question 27

What does the Trie wrapper function do?

Answer 27

Hides the reference to the root node and the initial counter

Question 28

What is the purpose of the index parameter in the recursive search function?

Answer 28

Tracks the position of the character being checked

Question 29

What does the TrieNodeSearch function check when the index equals the length of the target?

Answer 29

If current.is_entry is True

Question 30

What happens if the current node is not a valid entry at the end of the search?

Answer 30

Returns null

Question 31

What does the character mapping function do in the trie search?

Answer 31

Maps the character to the correct index in the array

Question 32

How can we determine if a string is not in the trie?

Answer 32

By hitting a dead end in the search

Question 33

True or False: The number of comparisons for a successful trie search depends on the number of strings stored in the trie.

Answer 33

False

Question 34

What is one key advantage of using a trie over a binary search tree?

Answer 34

Search cost is independent of the number of strings stored

Question 35

What happens during the insertion of a string into a trie?

Answer 35

Progress down the tree and create a subtree at a dead end

Question 36

What does the TrieInsert function do?

Answer 36

Calls the recursive search function with the root node

Question 37

What does the is_entry flag indicate in a trie node?

Answer 37

Whether the current node represents a valid entry

Question 38

What is the process for deleting a node from a trie?

Answer 38

Progress up the tree deleting nodes that are no longer needed

Question 39

What does the TrieDelete function start with?

Answer 39

The root node and the correct index

Question 40

What condition prevents a node from being deleted during the deletion process?

Answer 40

If it has at least one non-empty child or is an entry

Question 41

What does the TrieNodeDelete function return?

Answer 41

A Boolean indicating whether the current node can be safely deleted

Question 42

What is a key disadvantage of tries compared to binary search trees?

Answer 42

Higher memory usage due to storing multiple nodes for overlapping prefixes

Question 43

True or False: Deletion in a trie is proportional to the length of the target string.

Answer 43

True

Question 44

What is an example use case for a trie in a word processor?

Answer 44

Tracking words in a dictionary for spell-checking

Question 45

How do tries optimize the cost of operations?

Answer 45

By using the structure inherent in the data

Question 46

What type of data structures can benefit from using a trie, apart from words?

Answer 46

Structured labels like serial numbers or SKU codes

Question 47

Fill in the blank: The trie structure is particularly effective when the number of strings with _______ increases.

Answer 47

similar prefixes

Question 48

What is the main theme illustrated by the use of tries in data structures?

Answer 48

Using the structure inherent in data to improve algorithmic efficiency