Ch.28 - Balanced Search Trees Test Bank Docx

Chapter 28 - Balanced Search Trees

True/False (14)

1. Every node in a balanced binary tree has subtrees whose heights differ by no more than 1.
2. The balance of a binary search tree is not affected when you only add or remove a node.
3. A node is balanced if it is the root of a balanced tree.
4. In an AVL tree, if the method getHeightDifference returns -1, the left subtree is taller than the right subtree.
5. A 2-3 tree tends to be shorter than a binary search tree.
6. A 2-3 tree is completely balanced.
7. In a 2-3 tree, the last node that splits is a leaf that already contains two entries.
8. A 2-4 tree is completely balanced.
9. Adding an entry to a 2-3 tree is more efficient than adding an entry to a 2-4 tree.
10. When adding a new entry to 2-4 tree, you split any 4-node as soon as you encounter it during the search for the new entry’s position in the tree.
11. The root of every red-black tree is red.
12. In a red-black tree, every red node has a black parent.
13. In a red-black tree, a red node cannot have red children.
14. In a red-black tree, adding an entry to a red-black tree results in a new red leaf.

Short Answer (6)

1. Starting with the following AVL tree, show the resultant tree after adding a node with the value 7.
   

Step 1: insert node causing an unbalanced tree


Step 2: after a left rotation on node 6, the node whose subtrees became unbalanced

1. Starting with the following AVL tree, show the resultant tree after adding a node with the value 3.
   

Step1: Insert node causing an unbalanced tree.

Step2: after a left rotation on node 43, the node whose subtrees became unbalanced

1. Add the following values to an initially empty 2-3 three. Show each step.
   16, 7, 21

1. What tree results when you add 19 to the following 2-4 tree?
   

1. What tree results when you add 12 to the following 2-4 tree?
   

1. What tree results when you add 31 to the following 2-4 tree?
   

Multiple Choice (28) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. A node that is the root of a balanced tree is called a(n) _____ node.
   1. balanced
   2. master
   3. search
   4. AVL
2. The balance of a binary search tree may be compromised when
   1. a new node is added
   2. a node is removed
   3. both a & b
   4. none of the above
3. A node is balanced if its two subtrees differ by no more than
   1. 1
   2. 0
   3. 2
   4. none of the above
4. If the numbers 23, 16, and 34 are added to an empty binary search tree in that order, in order to rebalance it, you need a(n)
   1. right rotation
   2. left rotation
   3. no rotation
   4. reheap rotation
5. If the numbers 5, 13, and 23 are added to an empty binary search tree in that order, in order to rebalance it, you need a(n)
   1. left rotation
   2. right rotation
   3. no rotation
   4. reheap rotation
6. When there is an addition to a node’s left subtree that creates an unbalanced search tree, you can correct it with a(n)
   1. right rotation
   2. left rotation
   3. reheap
   4. sift up
7. When there is an addition to a node’s right subtree that creates an unbalanced search tree, you can correct it with a(n)
   1. left rotation
   2. right rotation
   3. reheap
   4. sift up
8. What type of rotation do you need to rebalance an AVL tree if the addition that unbalanced the tree occurred in the left subtree of node N, the unbalanced node’s left child?
   1. right rotation
   2. left rotation
   3. right-left rotation
   4. left-right rotation
9. What type of rotation do you need to rebalance an AVL tree if the addition that unbalanced the tree occurred in the right subtree of node N, the unbalanced node’s left child?
   1. left-right rotation
   2. right-left rotation
   3. left rotation
   4. right rotation
10. What type of rotation do you need to rebalance an AVL tree if the addition that unbalanced the tree occurred in the left subtree of node N, the unbalanced node’s right child?
    1. right-left rotation
    2. left-right rotation
    3. right rotation
    4. left rotation
11. What type of rotation do you need to rebalance an AVL tree if the addition that unbalanced the tree occurred in the right subtree of node N, the unbalanced node’s right child?
    1. right rotation
    2. left rotation
    3. right-left rotation
    4. left-right rotation
12. In an AVL tree, if the method getHeightDifference returns a value greater than 1,
    1. the left subtree is taller than the right subtree
    2. the right subtree is taller than the left subtree
    3. the tree is balanced
    4. the tree is unstable
13. In an AVL tree, if the method getHeightDifference returns a value less than -1,
    1. the right subtree is taller than the left subtree
    2. the left subtree is taller than the right subtree
    3. the tree is balanced
    4. the tree is unstable
14. In a 2-3 tree, a 2-node contains
    1. one data item and two children
    2. two data items and one child
    3. two data items and three children
    4. three data items and two children
15. In a 2-3 tree, a 3-node contains
    1. two data items and three children
    2. three data items and two children
    3. one data item and two children
    4. two data items and one child
16. A 2-4 tree is a general search tree whose interior nodes must have
    1. either 2, 3, or 4 children
    2. either 2 or 4 children
    3. either 2, 3 or 4 data values
    4. no 3-nodes
17. When adding a new entry to 2-4 tree,
    1. you split any 4-node as soon as you encounter it during the search for the new entry’s position in the tree
    2. you split any 4-node on the way back up the search tree
    3. as soon as it is created
    4. when there is a collision
18. In general, which statement is true?
    1. 2-4 trees are shorter than 2-3 trees
    2. 2-4 trees are shorter than AVL trees
    3. 2-3 tree are shorter than AVL trees
    4. all of the above
19. In general, searching a 2-3 tree has an efficiency of
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n log n)
20. In general, searching a 2-4 tree has an efficiency of
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n log n)
21. In general, searching an AVL tree has an efficiency of
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n log n)
22. A binary tree that is equivalent to a 2-4 tree is called a(n)
    1. red-black tree
    2. AVL tree
    3. 2-3 tree
    4. 4-2 tree
23. Which of the following properties is true for a red-black tree?
    1. the root is black
    2. every path from the root to a leaf contains the same number of black nodes
    3. any children of a red node are black
    4. all of the above
24. Which of the following properties is true for a red-black tree?
    1. a red node cannot have red children
    2. the tree is always balanced
    3. the root is red
    4. all of the above
25. Which of the following properties is true for a red-black tree?
    1. every red node has a black parent
    2. the root is red
    3. red nodes cannot have black children
    4. all of the above
26. In a red-black tree, adding an entry to a red-black tree results in
    1. a new red leaf
    2. a new black leaf
    3. a rotation
    4. a node split
27. In a red-black tree, a 4-node consists of
    1. a black node and two red children
    2. a red node and two black children
    3. a black node and two black children
    4. a black node, one black child and one red child
28. Which search tree does the package java.util use to implement the methods in the interface SortedMap<K, V>?
    1. a red-black tree
    2. a 2-4 tree
    3. a 2-3 tree
    4. a binary search tree