Starting with an empty tree, draw the 2-3-4 tree that results after the following series of insertions, in this order:

T H E B I G D W A R F

(So each key in your tree should be a single letter, arranged according to alphabetical order.)

Show your work and clearly indicate the final 2-3-4 tree containing all of these letters.

Remember, in this class we do “pre-emptive splitting” for 2-3-4 insertion, splitting any 4-node along the insertion path. Look back in the notes if you aren’t sure what that means!

The following array represents a max-heap. Draw the tree visualization of this max-heap.

[ 80 78 68 74 26 43 63 67 27 8 ]

Starting with the array-based heap from the previous problem, give the array that results after performing the following three insertions, in this order:

insert(35)
insert(40)
insert(90)

Showing your work is required! You may want to draw some trees for your own scratch work, but we want the final answer as an array since that is how heaps are stored.

Starting with the following unsorted array, show the array that would result after performing a bottom-up heapify operation using bubble-down’s.

[ 15 98 43 31 94 76 ]

Again, you should show your work and then clearly indicate the final array.

For this problem and the next one, use the following hash function:

\[h(x) = \left\lfloor 5\sin(13x-7) + 5 \right\rfloor\]

Remember that the floor \(\lfloor x\rfloor\) just means rounding down. So for example, \[h(2024) = \lfloor 2.849\cdots \rfloor = 2\]

(This is actually not a good hash function but it should be easy for you to compute with a calculator or a very short program you write.)

The range of \(h(x)\) is integers from 0 up to 9, so it’s appropriate for a size-10 hash table.

Draw the resulting array after inserting the following numbers into a size-10 hash table, in this order, using separate chaining.

183, 520, 862, 67, 52, 197, 604, 388, 680