Question

2.1. Insert 85 into the following red-black tree. Show all your steps. (Note that the leaves (nil) are not shown) 33 o = blac

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

2.1) Given Red - black Tree is

0033 0020 000 0007 0026 0050 0030 0070 000

Insert 85:

85 > 33, 60, 80 go to Right Subtree

85  < 90 go to Left Subtree

0033 0020 0050 0007 0025 0050 00:30 0070 0190 0085

Node and Parent are both Red.Uncle of node is Red Push Blackness down from grand Parent0033 0020 006 0007 0026 0050 0050 0070 0030 0085

Node and Parent are both Red.Node is Right child Parent is Right child so Perform Single Rotate Left

0060 0033 0080 0020 0050 0070 0090 0007 0026 0035

Root of the Tree is Red Color it Black

0051 0033 0080 0020 0050 0070 0090 0007 0026 0035

Which is Required Red/Black Tree after Insertion of 85

2.2) Given Red - black Tree is

0033 0020 000 0007 0026 0050 0080 0005 0015 0022 0030

Insert 23:

23 < 33 go to Left Subtree
23 > 20 go to Right Subtree   
23 < 26 go to Left Subtree
23 > 22 go to Right Subtree   

0033 0020 0060 000/ 0025 0050 0050 0005 0015 0022 0030 0023

Node and Parent are both Red.Uncle of node is Red Push Blackness down from grand Parent

0033 0020 0050 0007 0026 0050 0030 0005 0015 0022 0030 0023

Node and Parent are both Red.Node is Right child Parent is Left child so Perform Single Rotate Left

0033 0026 0060 0020 0030 0050 0080 0007 0022 0005 0015 0023

Node and Parent are both Red.Node is Left child Parent is Left child So Perform Single Rotate Right

0026 0020 0033 000了 0022 0030 0050 0005 0015 0023 0050 0050

Root of the Tree is Red Color it Black

0026 0020 0033 000r 0022 0030 0050 0005 0015 0023 0050 0080

Which is Required Red/Black Tree after Insertion of 23

Add a comment
Know the answer?
Add Answer to:
2.1. Insert 85 into the following red-black tree. Show all your steps. (Note that the leaves...
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