Computer Science Homework Help

CMSC 341 Homework 2

Instructions: In all cases where I ask for proof, I want drawings of examples, break down cases, and then examine each case through a picture. Only revert to equations once the picture makes sense.

1. Show that in an AVL tree, rotations fix insertion heights. Break it down into cases, draw trees and show that when their heights are imbalanced according to the AVL height rule, that a rotation will restore the height requirement at each level.

2. Show that the Red Black Tree insertion algorithm produces rebalanced trees. Remember that in a Red Black tree, the black-height of any given left subtree must be equal to the blackheight of the right subtree. Break it down into the following cases (which are the insertion cases for a RB-Tree):

(a) What if the uncle (the grandparent’s other child) is red? Then we have to recolor the parent and uncle black, and do not rotate.

(b) What if the uncle is black (or nullptr)? Then we have to ask: Do we zig? or Zig-Zag? i. If our node is just the left child of the left child, or right child of the right child of the grandparent, then zig (one rotation). ii. If our node is the left child of the right child or right child of the left child, then we need to zig-zag (two rotations).

3. Insert the following elements into an array which we will make into a min-heap in the ”canonical way.” Show where the element starts in the array, and then show (perhaps using arrows) which elements are swapped, and then rewrite the array to show what the state is after each insertion.

15, 3, 18, 19, 10, 2

4. Draw a leftist heap whose right subtree is of height is 5 but whose null path length is 1, and where the right subtree has more nodes than the left (stuff as many in there as you can). Give an example where the height of the left subtree is only 3.

• Count the root node in height (root is of height 1).

• The leftist heap does not need to be producable by the standard insertion algorithm for leftist heaps, it must simply follow the rule that the npl(current ⇒ lef t) ≥ npl(current ⇒ right) at each node.

• Calculate the NPL at each node and write it.

• Remember that a null pointer should be considered to have a npl of −1. This allows the algorithm to work.