Deck 12: Self-Balancing Search Trees

Question 1

If a binary search tree were full and contained n items, the expected performance would be O(n).

Answer 1

False

Question 2

A tree that is self- __________ attempts to achieve a balance so that the height of each left subtree and right subtree are equal or nearly equal.

Answer 2

balancing

Question 3

The cost of insertion in an extremely unbalanced binary search tree can be as high as O(__________).

A) n
B) n log n
C) n²
D) n²log n

Answer 3

n

Question 4

The height of an AVL tree is defined as the number of nodes in the longest path from the root to a leaf node, including the root.

Question 5

In the context of a Left-Left AVL tree, the right subtree of a node has height k and the left subtree has height k + 2. The balance of the node is __________.

A) -2
B) -1
C) 2
D) k

Question 6

The remedy for a __________ (parent balance is +2, right child balance is +1) AVL tree is to rotate left around parent.

A) Left-Left
B) Right-Right
C) Left-Right
D) Right-Left

Question 7

The AVL_Tree class derives directly from the __________ class.

A) BTNode
B) Binary_Tree
C) Binary_Search_Tree
D) BST_With_Rotate

Question 8

Which of the following lines completes the first (non-recursive) case of the AVL_Tree insert function?
If (local_root == NULL) {
Local_root = new AVLNode<Item_Type>(item);
__________
Return true;
}

A) increase = true;
B) increase = false;
C) decrease = true;
D) decrease = false;

Question 9

Complete the pseudocode for the first cut version of AVL_Tree function rebalance_right.
1. if the right subtree has __________ balance (Right-Left case)
2. Rotate right around the right subtree root.
3. Rotate left.

Question 10

The rotations performed by the rebalance_left member function of the AVL_Tree class will reduce the overall height of a tree by __________.

A) -1
B) 0
C) 1
D) 2

Question 11

When we remove an item from a left AVL subtree, the balance of the local root is decreased.

Question 12

Because each AVL subtree is allowed to be out of balance by ± __________, the tree may contain some holes.

A) 1
B) 2
C) 3
D) 4

Question 13

On the average, __________ comparisons are required to insert the nth item into an AVL tree.

A) 0.25
B) log² n
C) log² n + 0.25
D) n

Question 14

A Red-Black tree maintains the following invariants:
1. A node is either red or black.
2. The root is always __________.
3. A red node always has black children. (A NULL pointer is considered to refer to a black node.)
4. The number of black nodes in any path from the root to a leaf is the same.

Question 15

The algorithm for insertion into a Red-Black tree follows the same recursive search process used for all binary search trees to reach the insertion point.

Question 16

We begin deriving the Red_Black_Tree class from the __________ class.

A) AVL_Tree
B) BST_With_Rotate
C) Binary_Search_Tree
D) Binary_Tree

Question 17

In a Red-Black tree, we may remove a node only if it is a(n) __________ or if it has only one child.

Question 18

It can be shown that the upper limit of the height for a Red-Black tree is O(__________).

A) 1
B) log n
C) n
D) n log n

Question 19

A(n) __________ tree has the additional property that all of the leaves are at the lowest level.

Question 20

The number of items that a 2-3 tree of height h can hold is between 2^h - 1 (all 2-nodes) and __________ (all 3-nodes).

Question 21

A(n) __________-tree allows up to n children per node, where n may be a very large number.

Question 22

When comparing a Red-Black tree to a 2-3-4 tree, the 4-node is analogous to a (n) __________ node with two red children.

Question 23

The __________ of a B-tree is defined as the maximum number of children for a node.

Question 24

The insertion process for a B-tree is similar to that for a 2-3 or 2-3-4 tree, and each insertion is into a(n) __________.

Question 25

In a B+, tree the internal nodes contain only keys and pointers to children.