Insert the nodes 40 and 80 in the red and black tree in Figure 3a, one after the other.
computer science
Description
(a)
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.
(b)
(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.
