Deck 9: Self-Balancing Search Trees

Question 1

Searches into an unbalanced binary search tree are O(log n) not O(n).

Answer 1

False

Question 2

If a node is balanced, insertion into its left subtree will cause it to become left-heavy, and its height will also increase by 2.

Answer 2

False

Question 3

All the leaves of a 2-3 node are at the lowest level.

Answer 3

True

Question 4

The easiest way to keep a tree balanced is to always add nodes to the left subtree.

Question 5

Red nodes do not affect a Red-Black tree's balance.

Question 6

The average cost of a search in a(n) ____________________ tree built from random values is 1.002 log₂n.

Question 7

The Java API has a(n) ____________________ class that implements a Red-Black tree.

Question 8

A(n) ____ tree is made up of nodes designated as 2-nodes and 3-nodes.

Question 9

A(n) ____________________ tree is one in which the root and the left subtree of the root are both left-heavy.

Question 10

With respect to binary search tree, if the right subtree has a height of k, its left subtree has a height of 2, its factor is ____________________.

Question 11

The ____________________ of a tree is the number of nodes in the longest path from the root node to a leaf node, including the root.

Question 12

A(n) ____________________ contains two data fields, ordered so that the first is less than the second, and references to three children: one child containing values less than the first data field, one child containing values between the two data fields, and one child containing values greater than the second data field.

Question 13

____________________ trees expand on the idea of 2-3 trees by adding the 4-node.

Question 14

A Red-Black tree is a binary-tree equivalent of a(n) ____________________ tree.

Question 15

A(n) ____________________ extends the idea behind the 2-3 and 2-3-4 trees by allowing a maximum of CAP data items in each node.

Question 16

____ were developed to store indexes to databases on disk storage.

A) 2-3 trees
B) 2-3-4 trees
C) Red-Black trees
D) B-trees

Question 17

Which of the following is the algorithm for Rotation Right (unbalanced search tree)?

A) Remember the value of root.left (temp = root.left).
Set root.left to the value of root.left.right.
Set temp.left to root.
Set root to right.
B) Remember the value of root.left (temp = root.right).
Set root.right to the value of root.right.left.
Set temp.right to root.
Set root to temp.
C) Remember the value of root.left (temp = root.left).
Set root.left to the value of root.left.right.
Set temp.left to root.
Set temp to root.
D) Remember the value of root.left (temp = root.left).
Set root.left to the value of root.left.right.
Set temp.right to root.
Set root to temp.

Question 18

How would you rebalance a Left-Left tree?

A) Rotate right around parent.
B) Rotate left around child, then rotate right around parent.
C) Rotate left around parent.
D) Rotate right around child, then rotate left around parent.

Question 19

How would you rebalance a Right-Right tree?

A) Rotate right around parent.
B) Rotate left around child, then rotate right around parent.
C) Rotate left around parent.
D) Rotate right around child, then rotate left around parent.

Question 20

Which of the following is the complete algorithm for insertion into an AVL tree?

A) 1. if the root is null
2. Create a new tree with the item at the root and return true.
else if the item is equal to root.data
3. The item is already in the tree; return false.
B) 1. if the root is null
2. Create a new tree with the item at the root and return true.
else if the item is equal to root.data 3. The item is already in the tree; return false. else if the item is greater than root.data 4. The processing is symmetric to Steps1 through 3. Note that balance is incremented if increase is true.
C) 1. if the root is null
2. Create a new tree with the item at the root and return true.
else if the item is equal to root.data
3. The item is already in the tree; return false.
else if the item is less than root.data
4. Recursively insert the item in the left subtree.
5.if the height of the left subtree has increased (increased is true)
6. Decrement balance.
7. if balance is zero, reset increase to false.
8. if balance is less than -1
9. Reset increase to false.
10. Perform a rebalanceLeft.
else if the item is greater than root.data
11. The processing is symmetric to Steps 4 through 10. Note that balance is incremented if increase is true.
D) 1. if the root is null
2. Create a new tree with the item at the root and return true.
else if the item is equal to root.data
3. The item is already in the tree; return false.
4. Recursively insert the item in the left subtree. else if the item is greater than root.data
5. The processing is symmetric to Steps 1 through 4. Note that balance is incremented if increase is true.

Question 21

The following is the algorithm for ____.

A) rotation right
B) rebalanceLeft (AVL tree)
C) rotation left
D) rebalanceRight (AVL tree)

Question 22

The height of a 2-3 tree is between ____.

A) O(log n) and n
B) O(1) and O(n)
C) O(n) and O(n²)
D) log₃n and log₂n

Question 23

A(n) ____ can be represented as either a black node with a left red child or a black node with a right red child.

A) 2-node
B) 3-node
C) 4-node
D) 5-node

Question 24

With respect to Red-Black trees, which of the following is correct?

A) Nodes are always black.
B) The root is always red.
C) A red node always has red children.
D) The number of black nodes in any path from the root to a leaf is the same.

Question 25

The formula ____ is used to calculate the balance for each node of a binary search tree.

A) h_R - h_L
B) h_R + h_L
C) (h_R - h_L) *2
D) h_R * h_L

Question 26

A skip-list provides performance that is comparable to a balanced binary search tree.

Question 27

All nodes in a skip-list have the same number of links.

Question 28

The level of a node in a skip-list is determined by a random process.