• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

برای این سؤال شما باید درخت قرمز-سیاه را با امکانات درج، حذف و چاپ پیاده‌سازی کنید. برای چاپ درخت قرمز-سیاه پیمایش زیر را روی آن انجام دهید که معادل پیمایش طی شده توسط الگوریتم $BFS$ است.

یک صف خالی در نظر بگیرید و ریشه‌ی درخت را به آن وارد کنید. پس از این تا وقتی که تمام رئوس درخت چاپ شوند، اولین رأس موجود در صف را گرفته و مقدار و رنگ آن را چاپ کنید. سپس بچه‌های چپ و راست آن را به ترتیب به انتهای صف اضافه کرده و آن رأس را از ابتدای صف حذف کنید. برای روشن‌تر شدن منظور به نمونه‌های ورودی و خروجی دقت کنید.

ورودی

در هر خط ورودی یکی از دستورهای زیر وارد می‌شود:

• $insert \ x$
• $delete \ x$
• $print$

تعداد دستورات به گونه‌ای است که تنها با درخت قرمز-سیاه قابل حل در زمان مشخص شده باشد.

خروجی

در هر خط خروجی نتیجه‌ی یک دستور $print$ چاپ می‌شود. برای چاپ هر رأس مقدار عدد درون آن را به همراه رنگ آن رأس در خروجی بنویسید. برای روشن‌تر شدن منظور به نمونه توجه کنید.

مثال

ورودی نمونه

insert 10
insert 30
insert 50
insert 70
insert 90
insert 110
insert 130
insert 20
insert 100
print
delete 50
print
insert 95
print
insert 105
insert 103
delete 130
print

خروجی نمونه

70b 30r 110r 10b 50b 90b 130b 20r 100r
70b 20r 110r 10b 30b 90b 130b 100r
70b 20r 110r 10b 30b 95b 130b 90r 100r
70b 20b 95b 10b 30b 90b 103r 100b 110b 105r