Question 1

A binary search tree that is highly unbalanced is called a ________________ tree.

Accepted Answer

A binary search tree that is highly unbalanced is called a degenerate tree.

Question 2

In the worst case, a general binary search tree could require __________________ comparisons to find an element.

Accepted Answer

If the elements of a binary search tree are inserted in increasing or decreasing order, then finding an element will require a number of comparisons that is linear in the number of elements.

Question 3

In a binary search tree, the elements in the right subtree of the root are always larger than the element stored at the root.

Accepted Answer

The right subtree of the root may contain elements that are equal to the root.

Question 4

When removing an element from a binary search tree that has a single child, _____________________ will ensure that the resulting tree is still a binary search tree.

Accepted Answer

Replacing the element with its only child will guarantee that the resulting tree is a binary search tree.

Question 5

When removing an element from a binary search tree that has two children, _______________________ will ensure that the resulting tree is still a binary search tree.

Accepted Answer

Replacing it with its inorder successor will ensure that the resulting tree is a binary search tree.

Question 6

In a binary search tree, the elements in the right subtree of the root are __________________ the root element.

Accepted Answer

The elements in the right subtree of the root are greater than or equal to the root element.

Question 7

Finding an element in a binary search tree always requires O(log₂ n) comparisons.

Accepted Answer

In a degenerate binary search tree, finding an element may require O(n) comparisons in the worst case.

Question 8

In a maxheap, the largest element in the structure is always ______________________ .

Accepted Answer

In a heap, the root is always the largest element in the tree.

Question 9

A binary search tree is always a full tree.

Accepted Answer

A binary search tree is not necessarily a full tree.

Question 10

A ____________________ is a complete binary tree in which each element is greater than or equal to both of its children.

Accepted Answer

A heap is a complete binary tree in which each element is greater than or equal to both of its children.

Question 11

When removing an element from a binary search tree that is a leaf, ______________ will ensure that the resulting tree is still a binary search tree.

Accepted Answer

If the element that we wish to remove is a leaf, then simply deleting it will ensure that the resulting tree is still a binary search tree.

Question 12

A _____________________ is a tree whose elements are organized to facilitate finding a particular element when needed.

Accepted Answer

A search tree is a tree whose elements are organized to facilitate finding a particular element when needed.

Question 13

If a binary search tree becomes unbalanced after an element is added, it is sometimes possible to efficiently rebalance the tree by ___________________ .

Accepted Answer

Left and right rotations are useful in rebalancing a tree.

Question 14

When adding a new element to a binary search tree, the element is added as a(n) ______________.

Accepted Answer

An element added to a binary search tree is added as a leaf.

Question 15

Finding an element in a balanced binary search tree that contains n elements requires _____________________ comparisons.

Accepted Answer

If the search tree is balanced, then finding an element only requires a number of comparisons logarithmic in the number of elements contained in the tree.

Question 16

In a binary search tree, the elements in the left subtree of the root are __________________ the root element.

Accepted Answer

The elements in the left subtree of the root are less than the root element.

Question 17

In a binary search tree, a new element is always added as a leaf.

Accepted Answer

The new element will always be added as a leaf in a binary search tree.

Question 18

When removing an element from a binary search tree, we must always ______________________.

Accepted Answer

When removing an element from a binary search tree, it is important that the resulting tree is a binary search tree.

Question 19

In a balanced binary search tree, adding an element always requires approximately O(log₂ n) steps.

Accepted Answer

Adding an element to a binary search tree requires as many steps as finding an element. Since adding finding an element in a balanced binary search tree always requires O(log₂ n) steps, adding an element does as well.

Question 20

Which of the following is always true when adding an element to a heap?

Accepted Answer

When adding an element to a heap, it can end up anywhere in the tree.

Quiz 15: Heaps and Priority Queues