Question

9. The tree below is a RBT. 14 12 20 16 15 25 (a) (4 points) Insert 27. (b) (4 points) Insert 29 (c) (4 points) Remove 20. (d

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Initially the tree looks like:

0014 0012 0020 0016 0022 0015 0025

a) insert 27.

27 greater than root (14), 20, 22 and 25, so 27 becomes the right child of node 25 and colored red.

now both node 25 and node 27 are red.

0014 0012 0020 0016 0022 0015 0025 0027

Both parent and child are red. Node 27 is a right child and its parent 25 is also right child, so it can be solved by single left

rotation from node 22 and switch color of node 22 and node 25.

Now, the tree looks like:

0014 0012 0020 0016 0025 0015 0022 0027

b) Insert 29.

as 29 is the largest node yet in the tree, so it becomes the right child of node 27 as shown below.

0014 0012 0020 0016 0025 0015 0022 0027 0028

both node 29 and 27 are red, and uncle of node 29 i.e node 22 is also red.

so make both uncle and parent of node 29 black and make its grand parent node 25 red, as shown below.

0014 0012 0020 0016 0025 0015 0022 0027 0028

now node 25 is red and is a right child of its parent node 20 which is also red and is also a red node, this can be simple fixed by single left rotation from root node.and switching color of node 14 and 20.

now the tree looks like,

0020 0014 0025 0012 0016 0022 0027 0015 0028

c) remove 20.

node to be deleted is the root, now it has two children so find the largest node in the left subtree (here it is node 16).

copy value of largest node in the left subtree to the node to be deleted and remove node whose value is copied, i.e node 16.

now the tree looks like

0016 0014 0025 0012 0015 0022 0027 0028

d) remove 16

its the same case as above, node to be deleted is root and it has two children.

find the largest node in the left subtree and copy its value to the node to be deleted, and remove the node whose value is copied and coloring child of deleted node black.

now the tree looks like,

0015 0014 0025 NULL 0012 0022 0027 0028

Double black node has black sibling and 2 black nephews. Push up black level.

finally the tree looks like,

0015 0014 0025 0012 0022 0027 0028

Add a comment
Know the answer?
Add Answer to:
9. The tree below is a RBT. 14 12 20 16 15 25 (a) (4 points) Insert 27. (b) (4 points) Insert 29 ...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT