8: Scapegoat Trees Recall that a scapegoat node is a node v-u.parent where 2*size(u) > 3*size(u.parent) 1. 2. 3. In a scapegoat tree, is size(u) 2*size(v)) then explain how many operations (insertion/deletions) have affected v's subtree since the last time the subtree containing v was rebuilt. 9: 2-4 and Red-Black Trees 1. Draw an interesting example of a 2-4 tree. 2. Explain what happens in a 2-4 tree when an insertion causes a node to have more than 4 children. 3. Explain what happens in a 2-4 tree when a deletion causes a node to have only one child 4. Draw a red-black tree that corresponds to your 2-4 tree 5. Explain the relationship between the red-black tree properties and the 2-4 tree properties. 10: Heap:s 10.1 Binary Heaps These questions are about complete binary heaps represented using the Eytzinger Method 1. 2. 3. Draw an example of a complete binary heap with key values. Illustrate how your example's values map into an array using the Eytzinger Method. Consider a binary heap represented using the Eytzinger Method. Give the formulas for the parent, left child, and right child of the value stored at position i. When we perform a DeleteMin (remove()) operation on a heap, where do we get the value to replace the root, and what do we do with it? 4. 5. Explain or illustrate the insertion algorithm for a heap 6. Explain the operation of HeapSort 10.2 Randomized Meldable Heaps 1. 2. Draw two examples of heaps (not necessarily complete) and show how to meld (merge) them Explain how the add(x), and remove() operations can be done using the meld() operation. 8: Scapegoat Trees Recall that a scapegoat node is a node v-u.parent where 2*size(u) > 3*size(u.parent) 1. 2. 3. In a scapegoat tree, is size(u) 2*size(v)) then explain how many operations (insertion/deletions) have affected v's subtree since the last time the subtree containing v was rebuilt. 9: 2-4 and Red-Black Trees 1. Draw an interesting example of a 2-4 tree. 2. Explain what happens in a 2-4 tree when an insertion causes a node to have more than 4 children. 3. Explain what happens in a 2-4 tree when a deletion causes a node to have only one child 4. Draw a red-black tree that corresponds to your 2-4 tree 5. Explain the relationship between the red-black tree properties and the 2-4 tree properties. 10: Heap:s 10.1 Binary Heaps These questions are about complete binary heaps represented using the Eytzinger Method 1. 2. 3. Draw an example of a complete binary heap with key values. Illustrate how your example's values map into an array using the Eytzinger Method. Consider a binary heap represented using the Eytzinger Method. Give the formulas for the parent, left child, and right child of the value stored at position i. When we perform a DeleteMin (remove()) operation on a heap, where do we get the value to replace the root, and what do we do with it? 4. 5. Explain or illustrate the insertion algorithm for a heap 6. Explain the operation of HeapSort 10.2 Randomized Meldable Heaps 1. 2. Draw two examples of heaps (not necessarily complete) and show how to meld (merge) them Explain how the add(x), and remove() operations can be done using the meld() operation
