Question: A red - black tree ( RBT ) T is shown in the following figure, where the nil nodes are not shown. Suppose that we

A red-black tree (RBT) T is shown in the following figure, where the nil nodes are not shown.
Suppose that we want to insert 28 into the tree in the figure. We first allocate memory for a tree node P and set its color to red and its key to 28. We then insert it into tree T as if inserting into a binary search tree (BST).
1. After the insertion of node P with key 28 into the BST, the parent of P is?
2. After the insertion of node P with key 28 into the BST, is P the left child or the right child of its parent?
3. After the insertion of node P with key 28 into the BST, the RBT property being violated is?
4. We need to perform insertion fixup when necessary, so that the resulting tree is still a red-black tree. In the resulting red-black tree, what is the parent of P?
5. In the resulting red-black tree, what is the color of P?
6. In the resulting red-black tree, what is the left child of P?
7. In the resulting red-black tree, what is the right child of P?
8. In the resulting red-black tree, is P the left child or the right child of its parent?
 A red-black tree (RBT) T is shown in the following figure,

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!