Clicker Questions - 24-Heaps-Etc
Clicker Questions
All of the questions below pertain to the tree below. For each pair of questions, ignore the previous questions – in other words, each pair of questions pertain to this tree and not to the results of previous AVL tree operations.
Question 1: If I insert 72 into the tree, what type of rebalancing operation will I do (answer “zigzig” or “zigzag”)?
Answer
When I insert 72, I get:
Node 80 is imbalanced, and the imbalance goes left-right. So it's zigzag.
Question 2: About which node will I perform the rotation(s)?
Answer
To fix, I rotate twice about the grandchild of the imbalanced node. That's node 72. Here's the result:
Question 3: If I insert 99 into the tree, what type of rebalancing operation will I do (answer “zigzig” or “zigzag”)?
Answer
When I insert 99, I get:
Node 94 is imbalanced, and the imbalance goes right-right. So it's zigzig.
Question 4: About which node will I perform the rotation(s)?
Answer
To fix, I rotate once about the child of the imbalanced node. That's node 97. Here's the result:
Question 5: If I insert 19 into the tree, what type of rebalancing operation will I do (answer “zigzig” or “zigzag”)?
Answer
When I insert 19, I get:
Node 18 is imbalanced, and the imbalance goes right-left. So it's zigzag.
Question 6: About which node will I perform the rotation(s)?
Answer
To fix, I rotate twice about the grandchild of the imbalanced node. That's node 45. Here's the result:
Question 7: If I delete 94 into the tree, what type of rebalancing operation will I do (answer “zigzig” or “zigzag”)?
Answer
When I delete 94, I replace it with node 97. The result is:
Node 90 is imbalanced, and the imbalance goes left-left. So it's zigzig.
Question 8: About which node will I perform the rotation(s)?
Answer
To fix, I rotate once about the child of the imbalanced node. That's node 82. Here's the result:
Question 9: If I delete 87 into the tree, what type of rebalancing operation will I do (answer “zigzig” or “zigzag”)?
Answer
When I delete 87, I get:
Node 82 is imbalanced, and the imbalance goes left-left. So it's zigzig.
Question 10: About which node will I perform the rotation(s)?
Answer
To fix, I rotate once about the child of the imbalanced node. That's node 80. Here's the result:
Question 11: If I delete 18 into the tree, what type of rebalancing operation will I do (answer “zigzig” or “zigzag”)?
Answer
When I delete 18, I replace it with the largest node in its left subtree -- 12 -- and then delete node 12. Here's the result:
Node 12 is imbalanced, and this case where the two subtrees of the child (58) are the same height. You treat this as zigzig.
Question 12: About which node will I perform the rotation(s)?
Answer
To fix, I rotate once about the child of the imbalanced node. That's node 58. Here's the result: