Deck 10: Trees

Question 1

A binary search tree is a binary tree with the added property that the left child is less than the parent, which is less than or equal to the ___________.

A) Left child
B) Right child
C) Middle child
D) None of the above

Answer 1

Right child

Question 2

The definition of a binary search tree is an extension of the definition of a ______________.

A) stack
B) queue
C) list
D) binary tree

Answer 2

binary tree

Question 3

Each BinaryTreeNode object maintains a reference to the element stored at that node as well as references to each of the node's __________.

A) children
B) siblings
C) ancestors
D) None of the above

Answer 3

children

Question 4

In removing an element from a binary search tree, another node must be ___________ to replace the node being removed.

A) duplicated
B) demoted
C) promoted
D) None of the above

Question 5

The leftmost node in a binary search tree will contain the __________ element, while the rightmost node will contain the __________ element.

A) Maximum, minimum
B) Minimum, maximum
C) Minimum, middle
D) None of the above

Question 6

One of the uses of trees is to provide _________ implementations of other collections.

A) efficient
B) easy
C) useful
D) None of the above

Question 7

If a binary search tree is not __________, it may be less efficient than a linear structure.

A) complete
B) empty
C) balanced
D) None of the above

Question 8

The height of the right subtree minus the height of the left subtree is called the ___________ of a node.

A) height
B) balance factor
C) order
D) None of the above

Question 9

The balance restriction on a red/black tree is somewhat less strict than that for AVL trees. However, in both cases, the find operation is order ______.

A) n
B) log n
C) n log n
D) None of the above

Question 10

The Java Collections API provides two implementations of balanced binary search trees, TreeSet and TreeMap, both of which use a ___________tree implementation.

A) AVL
B) red/black
C) binary search
D) None of the above

Question 11

A binary ______ tree is a binary tree with the added property that the left child is less than the parent, which is less than or equal to the right child.

Question 12

The definition of a binary search tree is an ______ of the definition of a binary tree.

Question 13

Each BinaryTreeNode object maintains a reference to the ______ stored at that node as well as references to each of the node's ______.

Question 14

In removing an element from a binary search tree, another node must be ______ to replace the node being removed.

Question 15

The ______ node in a binary search tree will contain the minimum element, while the ______ node will contain the maximum element.

Question 16

One of the uses of trees is to provide ______ implementations of other collections.

Question 17

If a binary search tree is not balanced, it may be less ______ than a linear structure.

Question 18

The height of the right subtree minus the height of the left subtree is called the ______ of a node.

Question 19

There are only two ways that a tree, or any subtree of a tree, can become ______: through the insertion of a node or through the deletion of a node.

Question 20

The balance restriction on a red/black tree is somewhat less strict than that for AVL trees. However, in both cases, the find operation is order ______.

Question 21

The Java Collections API provides two implementations of balanced binary search trees, ______ and ______, both of which use a red/black tree implementation.

Question 22

A binary search tree is a binary tree with the added property that the left child is greater than the parent, which is less than or equal to the right child.

Question 23

The definition of a binary search tree is an extension of the definition of a binary tree.

Question 24

Each BinaryTreeNode object maintains a reference to the element stored at that node as well as references to each of the node's children.

Question 25

In removing an element from a binary search tree, another node must be demoted to replace the node being removed.

Question 26

The leftmost node in a binary search tree will contain the minimum element, while the rightmost node will contain the maximum element.

Question 27

One of the uses of trees is to provide simpler implementations of other collections.

Question 28

If a binary search tree is not balanced, it may be less efficient than a linear structure.

Question 29

The height of the right subtree minus the height of the left subtree is called the balance factor of a node.

Question 30

There are only two ways that a tree, or any subtree of a tree, can become unbalanced: through the insertion of a node or through the deletion of a node.

Question 31

The balance restriction on a red/black tree is somewhat less strict than that for AVL trees. However, in both cases, the find operation is order n.

Question 32

What is the difference between a binary tree and a binary search tree?

Question 33

Why are we able to specify addElement and removeElement operations for a binary search tree but we were unable to do so for a binary tree?

Question 34

Assuming that the tree is balanced, what is the time complexity (order) of the addElement operation?

Question 35

Without the balance assumption, what is the time complexity (order) of the addElement operation?

Question 36

As stated in this chapter, a degenerate tree might actually be less efficient than a linked list. Why?

Question 37

Our removeElement operation uses the inorder successor as the replacement for a node with two children. What would be another reasonable choice for the replacement?

Question 38

The removeAllOccurences operation uses both the contains and removeElement operations. What is the resulting time complexity (order) for this operation?

Question 39

RemoveFirst and first were O(1) operations for our earlier implementation of an ordered list. Why are they less efficient for our BinarySearchTreeOrderedList?

Question 40

Why does the BinarySearchTreeOrderedList class have to define the iterator method? Why can it not just rely on the iterator method of its parent class like it does for size and isEmpty?

Question 41

What is the time complexity of the addElement operation after modifying to implement an AVL tree?

Question 42

What imbalance is fixed by a single right rotation?

Question 43

What imbalance is fixed by a leftright rotation?

Question 44

What is the balance factor of an AVL tree node?

Question 45

In our discussion of the process for rebalancing an AVL tree, we never discussed the possibility of the balance factor of a node being either +2 or -2 and the balance factor of one of its children being either +2 or -2. Why not?

Question 46

We noted that the balance restriction for a red/black tree is less strict than that of an AVL tree and yet we still claim that traversing the longest path in a red/black tree is still O(log n). Why?

Question 47

What is the difference between a TreeSet and a TreeMap?