۰
subtitle
ارسال: #۱
  
۶۰۰ مساله | درخت قرمز سیاه | ۴۰/۴ | صفحه ۷۷
درود و احترام
خود ۶۰۰ هم با رسم شکل گفته ولی فقط شکله
طبق معمول زیاد از توضیح خبری نیست
خود ۶۰۰ هم با رسم شکل گفته ولی فقط شکله
طبق معمول زیاد از توضیح خبری نیست
۴
ارسال: #۲
  
RE: 600 مساله | درخت قرمز سیاه | ۴۰/۴ | صفحه ۷۷
سلام
از ویژگی هی درخت RB :
رنگ ریشه سیاه است. رنگ برگ ها هم سیاه است(تعریف برگ در RB متفاوت است مثلا در این درخت۱و۸و۲۲ برگ نیستند بلکه برگ نود های nill نودهای موجود در درخت هستند مثلا نود ۸دو برگ دارد و نود ۹ یک برگ و ...پیش فرض این برگ ها ترسیم نمی شوندبرای راحتی حل بهتر است برگ ها را ترسیم کنیم البته طبق تعریف با رنگ سیاه).ویژگی دیگر اگر نودی قرمز باشد فرزندان ان سیاه است و(مهم)برای هر نوداگر از ان نود به سمت هر یک از برگ های موجود در زیردختانش حرکت کنیم تعداد نود سیاه یکسانی پیمایش می شود.
در درخت مطر ح شده اگر از گره ۹ به زیردرخت راستش حرکت کنیم فقط یک برگ که سیاه دیده می شود. پس با حرکت در زیر درخت چپ هم باید تا رسیدن به هریک از برگ هم یک نود سیاه پیمایش شود در زیردرخت چپ ۹ دو برگ نود۸ وجود دارد پس نود ۸ حتما قرمز باید باشد تا در زیردرخت چپ تا رسیدن به یک برگ یک نود سیاه پیمایش شود مثل زیردرخت راستش. درنتیجه ۹ هم سیاه است(چون ۸ قرمز است و۹ اگر قرمز باشد ویژگی اگر نودی قرمز باشد فرزندان ان سیاه است را نقض می کند)پس تا اینجا ۸ حتما قرمز و ۹ هم حتما سیاه است.همین روند برای نود های ۱۴ و ۲۲ هم برقرار است با حرکت در چپ ۱۴ یک نود سیاه پیمایش می شود پس باحرکت در راست ۱۴ هم تا رسیدن به برگ های ۲۲ باید یک نود سیاه دیده شود پس ۲۲ قرمز در نتیجه ۱۴ سیاه باید باشد.فقط حالت های ۶ و ۱ باقی مانده است.اگر در راست ۶ حرکت کنیم تا رسیدن به هر برگ دو نود سیاه دیده می شود پس باید ۱ هم سیاه باشد تا در چپ ۶ هم تا رسیدن به برگ های ۱ دو تا نود سیاه پیمایش شود.اگر در راست ۱۳(ریشه) حرکت کنیم تا هر برگ دو تا سیاه دیده میشود پس ۶ باید قرمز باشد تا در چپ ۱۳ هم دو تود سیاه دیده شود.خود ۱۳ هم چون ریشه است سیاه است پس نود های ۱و۹و۱۳و۱۴ سیاه و ۶ و۸و۲۲ قرمزانددر نتیجه فقط یک حالت برای رنگ امیزی این درخت وجود دارد یعنی گزینه ۲
از ویژگی هی درخت 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?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close