In this task, you are to insert certain nodes into predefined red-black trees. Please use the given algorithm for inserting nodes into a red-black tree. Draw your interim result each time after insertion, and after each iteration of the while loop in FixColorsAfterInsertion and, where appropriate, after the last colouring of the root.
(i) Insert the nodes 40 and 80 in the red and black tree in Figure 3a, one after the other.
(ii) Insert nodes 41 and 65 in the red and black tree in Figure 3b, in order.
(i) Insert nodes 39 and 32 in the splay tree in Figure 3c, in order. Use the given algorithm for inserting nodes into a splay tree. Draw your interim result each time after inserting the node, as well as after each Zig-Zig, Zig-Zag, and Zig-Operation.
(ii) Delete node 42 from the splay tree in Figure 3d. Use the given algorithm for deleting nodes from a splay tree. Draw your interim result after each of every Zig-Zig, Zig-Zag, and Zig operation performed, as well as after deleting the node and splitting the tree, and after merging the two subtrees.