The following figure shows red-black tree (RBT) in which a s…
The following figure shows red-black tree (RBT) in which a square denotes a black node, a circle denotes a red node, and the NIL nodes are omitted. The number inside a circle/square is the key value of the corresponding node. The label (upper-case letter) next to a node is a pointer pointing to the memory location of the corresponding node. You should use the label when referring to a node. (a) Suppose that we want to insert 33 into the RBT in the figure. We first allocate memory for a tree node O and set its color to red and its key to 33. Then we insert it into tree T as if inserting into a binary search tree (BST). After BST insertion (before RBT insertion fixup), the parent of O is (b) Suppose that we want to insert 33 into the RBT in the figure. We first allocate memory for a tree node O and set its color to red and its key to 33. Then we insert it into tree T as if inserting into a binary search tree (BST). After BST insertion (before RBT insertion fixup), is O the left child of its parent or the right child of its parent? Write LEFT or RIGHT. (c) Suppose that we want to insert 33 into the RBT in the figure. We first allocate memory for a tree node O and set its color to red and its key to 33. Then we insert it into tree T as if inserting into a binary search tree (BST). After BST insertion (before RBT insertion fixup), which property of the RBT is violated? Select 0 if none of the properties is violated. (d) Suppose that we want to insert 33 into the RBT in the figure. We first allocate memory for a tree node O and set its color to red and its key to 33. Then we insert it into tree T as if inserting into a binary search tree (BST). Then we perform insertion fixup if necessary. In the resulting RBT, what is the parent of node E? (e) Suppose that we want to insert 33 into the RBT in the figure. We first allocate memory for a tree node O and set its color to red and its key to 33. Then we insert it into tree T as if inserting into a binary search tree (BST). Then we perform insertion fixup if necessary. In the resulting RBT, what is the color of node J? (f) Suppose that we want to insert 33 into the RBT in the figure. We first allocate memory for a tree node O and set its color to red and its key to 33. Then we insert it into tree T as if inserting into a binary search tree (BST). Then we perform insertion fixup if necessary. In the resulting RBT, what is the left child of node O? (g) Suppose that we want to insert 33 into the RBT in the figure. We first allocate memory for a tree node O and set its color to red and its key to 33. Then we insert it into tree T as if inserting into a binary search tree (BST). Then we perform insertion fixup if necessary. In the resulting RBT, what is the right child of node O? (h) Suppose that we want to delete node C (with key=60) from the RBT in the figure. In the resulting RBT, what is the right child of node A? (i) Suppose that we want to delete node C (with key=60) from the RBT in the figure. In the resulting RBT, what is the color of node M? Write either BLACK or RED. (j) Suppose that we want to delete node C (with key=60) from the RBT in the figure. In the resulting RBT, what is the left child of node M? (k) Suppose that we want to delete node C (with key=60) from the RBT in the figure. In the resulting RBT, what is the right child of node M? (l) Suppose that we want to delete node C (with key=60) from the RBT in the figure. In the resulting RBT, what is the color of node F? Write either BLACK or RED. (m) Suppose that we want to delete node C (with key=60) from the RBT in the figure. In the resulting RBT, what is the color of node N? Write either BLACK or RED. (n) Suppose that we want to delete node C (with key=60) from the RBT in the figure. In the resulting RBT, what is the color of node G? Write either BLACK or RED.