11.2 Application of Trees

Question 1

A binary search tree is a binary tree with the following properties:

Answer 1

• Each vertex has a value called a key.
• The left subtree of a vertex contains only vertices with keys less than the vertex’s key.
• The right subtree of a vertex contains only vertices with keys greater than the vertex’s key.
• The left and right subtree must also be a binary search tree.

Question 2

A binary search tree is a binary tree with the following properties:

Answer 2

• Each vertex has a value called a key.
• The left subtree of a vertex contains only vertices with keys less than the vertex’s key.
• The right subtree of a vertex contains only vertices with keys greater than the vertex’s key.
• The left and right subtree must also be a binary search tree.

Question 3

Decision Trees

Answer 3

A rooted tree in which each internal vertex corresponds to a decision, with a subtree at these
vertices for each possible outcome of the decision

Question 4

Decision Trees

Answer 4

A rooted tree in which each internal vertex corresponds to a decision, with a subtree at these
vertices for each possible outcome of the decision

Question 5

Dec. Tree Theorem 1

Answer 5

A sorting algorithm based on binary comparisons requires at least [log n!] comparisons.

Question 6

Dec. Tree Corollary 1

Answer 6

The number of comparisons used by a sorting algorithm to sort n elements based on binary comparisons
is Ω(n log n).

Question 7

Dec. Tree Theorem 2

Answer 7

The average number of comparisons used by a sorting algorithm to sort n elements based on binary
comparisons is Ω(n log n).

Question 8

Dec. Tree Theorem 2

Answer 8

The average number of comparisons used by a sorting algorithm to sort n elements based on binary
comparisons is Ω(n log n).

Question 9

Prefix Codes

Answer 9

encode letters so that the bit string for a letter never occurs as the first part of the bit
string for another letter.

Question 10

Prefix Codes

Answer 10

encode letters so that the bit string for a letter never occurs as the first part of the bit
string for another letter.

Question 11

Huffman Coding

Answer 11

An algorithm that takes as input the frequencies of symbols in a string and produces an output a
prefix code that encodes the string using the fewest possible bits, among all possible binary prefix
codes for these symbols.