Question 1

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

Accepted Answer

The answer of A Red-Black tree is a binary-tree equivalent...

Question 2

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

Accepted Answer

The answer of ____________________ trees expand on the idea of...

Question 3

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

Accepted Answer

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.E) C) and D)
F) A) and C)

Question 4

How would you rebalance a Left-Left tree?

Accepted Answer

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.E) C) and D)
F) B) and C) A

Question 5

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

Accepted Answer

A) True 
 B)False

Question 6

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 ____________________.

Accepted Answer

The answer of With respect to binary search tree, if...

Question 7

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

Accepted Answer

Question 8

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

Accepted Answer

A) True 
 B)False

Question 9

How would you rebalance a Right-Right tree?

Accepted Answer

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.E) B) and C)
F) A) and D)

Question 10

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

Accepted Answer

A) True 
 B)False

Question 11

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.

Accepted Answer

A) True 
 B)False  False

Question 12

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

Accepted Answer

A) True 
 B)False

Question 13

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

Accepted Answer

The answer of The ____________________ of a tree is the...

Question 14

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

Accepted Answer

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.E) C) and D)
F) A) and D)

Question 15

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

Accepted Answer

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

Question 16

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

Accepted Answer

A)   2-node
B)   3-node
C)   4-node
D)   5-nodeE) B) and D)
F) A) and B) B

Question 17

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

Accepted Answer

A) True 
 B)False

Question 18

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

Accepted Answer

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.E) All of the above
F) B) and C)

Question 19

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.

Accepted Answer

The answer of A(n) ____________________ contains two data fields, ordered...

Question 20

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

Accepted Answer

A)   hR - hL
B)   hR + hL
C)   (hR - hL)  *2
D)   hR * hLE) None of the above
F) All of the above

Exam 9: Self-Balancing Search Trees

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

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

How would you rebalance a Left-Left tree?

Correct Answer
verified
A

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

Correct Answer
verified

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 ____________________.

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

How would you rebalance a Right-Right tree?

Correct Answer
verified

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

Correct Answer
verified

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.

Correct Answer
verified
False

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

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified
B

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

Correct Answer
verified

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

Correct Answer
verified

Correct Answer
verified

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

Correct Answer
verified

Exam 9: Self-Balancing Search Trees

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

How would you rebalance a Left-Left tree?

Correct AnswerverifiedA

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

Correct AnswerverifiedShow Answer

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 ____________________.

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

How would you rebalance a Right-Right tree?

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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.

Correct AnswerverifiedFalse

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedB

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
A

Correct Answer
verified

Correct Answer
verified

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

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
False

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
B

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified