زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۱۰:۵۰ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

۶۰۰ مساله | درخت قرمز سیاه | ۴۰/۴ | صفحه ۷۷

ارسال:
  

Happiness.72 پرسیده:

۶۰۰ مساله | درخت قرمز سیاه | ۴۰/۴ | صفحه ۷۷

درود و احترام

خود ۶۰۰ هم با رسم شکل گفته ولی فقط شکله Cool
طبق معمول زیاد از توضیح خبری نیست

نقل قول این ارسال در یک پاسخ

۴
ارسال:
  

msour44 پاسخ داده:

RE: 600 مساله | درخت قرمز سیاه | ۴۰/۴ | صفحه ۷۷

سلام
از ویژگی هی درخت RB :
رنگ ریشه سیاه است. رنگ برگ ها هم سیاه است(تعریف برگ در RB متفاوت است مثلا در این درخت۱و۸و۲۲ برگ نیستند بلکه برگ نود های nill نودهای موجود در درخت هستند مثلا نود ۸دو برگ دارد و نود ۹ یک برگ و ...پیش فرض این برگ ها ترسیم نمی شوندبرای راحتی حل بهتر است برگ ها را ترسیم کنیم البته طبق تعریف با رنگ سیاه).ویژگی دیگر اگر نودی قرمز باشد فرزندان ان سیاه است و(مهم)برای هر نوداگر از ان نود به سمت هر یک از برگ های موجود در زیردختانش حرکت کنیم تعداد نود سیاه یکسانی پیمایش می شود.
در درخت مطر ح شده اگر از گره ۹ به زیردرخت راستش حرکت کنیم فقط یک برگ که سیاه دیده می شود. پس با حرکت در زیر درخت چپ هم باید تا رسیدن به هریک از برگ هم یک نود سیاه پیمایش شود در زیردرخت چپ ۹ دو برگ نود۸ وجود دارد پس نود ۸ حتما قرمز باید باشد تا در زیردرخت چپ تا رسیدن به یک برگ یک نود سیاه پیمایش شود مثل زیردرخت راستش. درنتیجه ۹ هم سیاه است(چون ۸ قرمز است و۹ اگر قرمز باشد ویژگی اگر نودی قرمز باشد فرزندان ان سیاه است را نقض می کند)پس تا اینجا ۸ حتما قرمز و ۹ هم حتما سیاه است.همین روند برای نود های ۱۴ و ۲۲ هم برقرار است با حرکت در چپ ۱۴ یک نود سیاه پیمایش می شود پس باحرکت در راست ۱۴ هم تا رسیدن به برگ های ۲۲ باید یک نود سیاه دیده شود پس ۲۲ قرمز در نتیجه ۱۴ سیاه باید باشد.فقط حالت های ۶ و ۱ باقی مانده است.اگر در راست ۶ حرکت کنیم تا رسیدن به هر برگ دو نود سیاه دیده می شود پس باید ۱ هم سیاه باشد تا در چپ ۶ هم تا رسیدن به برگ های ۱ دو تا نود سیاه پیمایش شود.اگر در راست ۱۳(ریشه) حرکت کنیم تا هر برگ دو تا سیاه دیده میشود پس ۶ باید قرمز باشد تا در چپ ۱۳ هم دو تود سیاه دیده شود.خود ۱۳ هم چون ریشه است سیاه است پس نود های ۱و۹و۱۳و۱۴ سیاه و ۶ و۸و۲۲ قرمزانددر نتیجه فقط یک حالت برای رنگ امیزی این درخت وجود دارد یعنی گزینه ۲
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۳۴ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  سوال در مورد صفحه بندی در سیستم عامل Azadam ۱ ۱,۵۱۹ ۱۳ دى ۱۴۰۰ ۱۱:۰۴ ق.ظ
آخرین ارسال: Azadam
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۷ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۱ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  صفحه چند سطحی Flash1 ۰ ۱,۵۶۶ ۱۰ تیر ۱۳۹۹ ۰۵:۵۸ ب.ظ
آخرین ارسال: Flash1
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۱۹۹ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۳,۱۹۸ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close