Lesson test: Binary search trees

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Binary search trees

1.[2p]
The binary search tree property says that at every node $x$ ,

every key in the left subtree is smaller than $x$ and every key in the right subtree is larger

Correct

the left child is smaller than $x$ and the right child is larger

The answer is: every key in the left subtree is smaller than $x$ and every key in the right subtree is larger

the two subtrees hold the same number of keys

The answer is: every key in the left subtree is smaller than $x$ and every key in the right subtree is larger

the height of the two subtrees differs by at most one

The answer is: every key in the left subtree is smaller than $x$ and every key in the right subtree is larger

2.[3p]
Insert 41, 23, 67, 12, 35, 55, 88, 29 in that order. What is the height of the resulting tree, counting edges?

CorrectNot quite: 3

3.[2p]
Insert those same eight keys in ascending order instead. What is the height then?

CorrectNot quite: 7

4.[3p]
Deleting a node with two children works by

overwriting its key with its successor's, then deleting the successor node, which has no left child

Correct

splicing its parent directly onto its left child

The answer is: overwriting its key with its successor's, then deleting the successor node, which has no left child

rotating it down until it becomes a leaf

The answer is: overwriting its key with its successor's, then deleting the successor node, which has no left child

rebuilding the whole subtree beneath it

The answer is: overwriting its key with its successor's, then deleting the successor node, which has no left child

5.[1p]
An in-order traversal of a binary search tree emits its keys in ascending order.

True

Correct

False

The answer is: True

6.[3p]
For a million keys, an average successful search in a randomly built tree costs about $2 \ln n$ comparisons. How many is that?

CorrectNot quite: 27.6

7.[3p]
Which of these are reasons the degenerate linear tree matters in practice?

Select all that apply

Identifiers assigned by an incrementing counter arrive in ascending order

Correct

Rebuilding a tree from a sorted export inserts every key in order

Correct

An attacker who controls insertion order can force it deliberately

Correct

Random insertion order is guaranteed by hashing the keys first

The answer is: Identifiers assigned by an incrementing counter arrive in ascending order, Rebuilding a tree from a sorted export inserts every key in order, An attacker who controls insertion order can force it deliberately

8.[3p]
Match each operation to what it costs in a binary search tree of height $h$ holding $n$ keys.

Search for one key
Find the minimum
List every key in order
Insert a new key

$O (h)$
$O (h)$
$O (h)$
$Θ (n)$

Show the answer

Search for one key: $O (h)$ Find the minimum: $O (h)$ List every key in order: $Θ (n)$ Insert a new key: $O (h)$

9.[3p]
Why is quicksort's average comparison count also the expected sum of node depths in a random tree?

The first pivot is the root and each partition is a subtree, so the two counts are the same quantity

Correct

Both are approximately $n \log_{2} n$

The answer is: The first pivot is the root and each partition is a subtree, so the two counts are the same quantity

Both algorithms use randomisation

The answer is: The first pivot is the root and each partition is a subtree, so the two counts are the same quantity

Quicksort builds a tree internally

The answer is: The first pivot is the root and each partition is a subtree, so the two counts are the same quantity

1.[2p] The binary search tree property says that at every node x,

2.[3p] Insert 41, 23, 67, 12, 35, 55, 88, 29 in that order. What is the height of the resulting tree, counting edges?

3.[2p] Insert those same eight keys in ascending order instead. What is the height then?

4.[3p] Deleting a node with two children works by

5.[1p] An in-order traversal of a binary search tree emits its keys in ascending order.

6.[3p] For a million keys, an average successful search in a randomly built tree costs about 2lnn comparisons. How many is that?

7.[3p] Which of these are reasons the degenerate linear tree matters in practice?

8.[3p] Match each operation to what it costs in a binary search tree of height h holding n keys.

9.[3p] Why is quicksort's average comparison count also the expected sum of node depths in a random tree?

1.[2p]
The binary search tree property says that at every node $x$ ,

2.[3p]
Insert 41, 23, 67, 12, 35, 55, 88, 29 in that order. What is the height of the resulting tree, counting edges?

3.[2p]
Insert those same eight keys in ascending order instead. What is the height then?

4.[3p]
Deleting a node with two children works by

5.[1p]
An in-order traversal of a binary search tree emits its keys in ascending order.

6.[3p]
For a million keys, an average successful search in a randomly built tree costs about $2 \ln n$ comparisons. How many is that?

7.[3p]
Which of these are reasons the degenerate linear tree matters in practice?

8.[3p]
Match each operation to what it costs in a binary search tree of height $h$ holding $n$ keys.

9.[3p]
Why is quicksort's average comparison count also the expected sum of node depths in a random tree?