تعداد رنگ کردن درخت قرمز سیاه
سلام .
ابتدا مروری به خواص ۴ گانه درخت های Red-Black داریم .
۱- ریشه درخت سیاه است ( معمولا )
۲- برگ های فرضی که برای سمت چپ و راست هر برگ از درخت رسم میکنیم همه سیاه رنگ هستند
۳- تعداد نود های سیاه از ریشه به برگ های فرضی همه یکسان است
۴- فرزند هر گره قرمز سیاه رنگ است .
در درخت مفروض باید کوتاه ترین فاصله تا ریشه را انتخاب کرده و کل آن مسیر را به رنگ مشکلی تبدیل کنیم ( یعنی ابتدا به زیر درخت سمت چپ ریشه ( با راس ۴ ) نگاه میکنیم آن را مشکلی میکنیم . خوب فرزند فرضی سمت راست آن را ( که مشکلی است ) رسم میکنیم . خوب اکنون باید برای همه مسیر ها تعداد نود های مشکی تا برگ فرضی برابر سه باشد . که با رنگ آمیزی و رعایت نکات بالا نود ۷ به رنگ قرمز تبدیل میشود .
در زیر درخت سمت راست نود ۲۰ قرمز میشود و حتما فرزند هایش ( ۱۴ و ۲۶ ) مشکلی میشوند ، برای زیر درخت سمت راست نود ۲۰ دیگر مشکلی نداریم اما اگر بخواهیم نود ۱۱ را مشکلی کنیم با مشکل مواجه میشویم و حتما باید آن را قرمز کنیم . اگر قرمز کنیم برای این زیر درخت هم مساله حل میشود . که در نهایت به نظرم همین یه درخت ممکن است و گزینه ۲ صحیح است .
(۰۲ فروردین ۱۳۹۶ ۱۲:۳۸ ق.ظ)alireza01 نوشته شده توسط: سلام .سلام
ابتدا مروری به خواص ۴ گانه درخت های Red-Black داریم .
۱- ریشه درخت سیاه است ( معمولا )
۲- برگ های فرضی که برای سمت چپ و راست هر برگ از درخت رسم میکنیم همه سیاه رنگ هستند
۳- تعداد نود های سیاه از ریشه به برگ های فرضی همه یکسان است
۴- فرزند هر گره قرمز سیاه رنگ است .
در درخت مفروض باید کوتاه ترین فاصله تا ریشه را انتخاب کرده و کل آن مسیر را به رنگ مشکلی تبدیل کنیم ( یعنی ابتدا به زیر درخت سمت چپ ریشه ( با راس ۴ ) نگاه میکنیم آن را مشکلی میکنیم . خوب فرزند فرضی سمت راست آن را ( که مشکلی است ) رسم میکنیم . خوب اکنون باید برای همه مسیر ها تعداد نود های مشکی تا برگ فرضی برابر سه باشد . که با رنگ آمیزی و رعایت نکات بالا نود ۷ به رنگ قرمز تبدیل میشود .
در زیر درخت سمت راست نود ۲۰ قرمز میشود و حتما فرزند هایش ( ۱۴ و ۲۶ ) مشکلی میشوند ، برای زیر درخت سمت راست نود ۲۰ دیگر مشکلی نداریم اما اگر بخواهیم نود ۱۱ را مشکلی کنیم با مشکل مواجه میشویم و حتما باید آن را قرمز کنیم . اگر قرمز کنیم برای این زیر درخت هم مساله حل میشود .
من دیگر نتوانستم درختی رو رنگ آمیزی کنم که با توضیحات درخت RB بشه رسمش کرد برای این درخت داده شده که ممکنه اطلاعاتم برای حل این سوال کافی نباشه . اگر اساتید محترم همچون آقای جویباری ، بهنام ، منصور و دیگر اساتید محترم نظری دارند خوشحال میشوم از شنیدن آن
دوست گرامی اگر منظور شما ار کوتاه ترین فاصله تا ریشه کوتاه ترین فاصله از برگ ها به ریشه باشدو مشکی کردن کل ان مسیر... به نظر این روش کلیت ندارد در همین درخت اگر درخت ما فقط ۳ راس اول را داشته باشد یعنی ریشه و ۴ و۲۰ هر دوی مسیر های ۴ و ۲۰ یکسان انند با انتخاب هر یک و سیاه کردن ان دیگری هم سیاه باید باشد و این درحالی است که قرمز هم می تواند باشد(دیگری را هم قرمز می کند).هر چند به نظر در این تست درست جواب می دهد.
ویژگی سوم RB را که عنوان کردید حالت کلی تر ان به صورت زیر است:
برای هر گره داخلی X با حرکت در زیر درختان چپ و راست ان تا رسیدن به برگ ها تعداد نود سیاه (بجز X)یکسانی پیمایش می شود.
یک نمونه تست مشابه ب کمک این ویژگی (از پایین به بالا)در لینک زیر حل شده است.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۲ فروردین ۱۳۹۶ ۰۳:۴۴ ق.ظ)msour44 نوشته شده توسط: سلام
دوست گرامی اگر منظور شما ار کوتاه ترین فاصله تا ریشه کوتاه ترین فاصله از برگ ها به ریشه باشدو مشکی کردن کل ان مسیر... به نظر این روش کلیت ندارد در همین درخت اگر درخت ما فقط ۳ راس اول را داشته باشد یعنی ریشه و ۴ و۲۰ هر دوی مسیر های ۴ و ۲۰ یکسان انند با انتخاب هر یک و سیاه کردن ان دیگری هم سیاه باید باشد و این درحالی است که قرمز هم می تواند باشد(دیگری را هم قرمز می کند).هر چند به نظر در این تست درست جواب می دهد.
ویژگی سوم RB را که عنوان کردید حالت کلی تر ان به صورت زیر است:
برای هر گره داخلی X با حرکت در زیر درختان چپ و راست ان تا رسیدن به برگ ها تعداد نود سیاه (بجز X)یکسانی پیمایش می شود.
یک نمونه تست مشابه ب کمک این ویژگی (از پایین به بالا)در لینک زیر حل شده است.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام و درود بر شما استاد گرامی .
منظور من از کوتاه ترین فاصله تا ریشه و ... باقی داستان در این مثال کذایی بود و نگفتم این روش کلیت دارد و حرف شما در این باره کاملا منطقی است ، در مورد ذکر حالت کلی ویژگی ذکر شده ممنونم از توضیح خوبتون و تستی که حل کردید رو حتما بررسی میکنم ...
(۰۲ فروردین ۱۳۹۶ ۱۱:۳۷ ق.ظ)alireza01 نوشته شده توسط:سلام دوست گرامی . من سزاوار واژه پر معنی استاد نیستم بیشتر این عنوان مناسب دوستان گرامی اقایان جویباری و بهنام و سایر دوستانی که بدون هیچ چشم داشتی دائم در حال اموزش و کمک به امثال من هستند می باشد.(02 فروردین ۱۳۹۶ ۰۳:۴۴ ق.ظ)msour44 نوشته شده توسط: سلام
دوست گرامی اگر منظور شما ار کوتاه ترین فاصله تا ریشه کوتاه ترین فاصله از برگ ها به ریشه باشدو مشکی کردن کل ان مسیر... به نظر این روش کلیت ندارد در همین درخت اگر درخت ما فقط ۳ راس اول را داشته باشد یعنی ریشه و ۴ و۲۰ هر دوی مسیر های ۴ و ۲۰ یکسان انند با انتخاب هر یک و سیاه کردن ان دیگری هم سیاه باید باشد و این درحالی است که قرمز هم می تواند باشد(دیگری را هم قرمز می کند).هر چند به نظر در این تست درست جواب می دهد.
ویژگی سوم RB را که عنوان کردید حالت کلی تر ان به صورت زیر است:
برای هر گره داخلی X با حرکت در زیر درختان چپ و راست ان تا رسیدن به برگ ها تعداد نود سیاه (بجز X)یکسانی پیمایش می شود.
یک نمونه تست مشابه ب کمک این ویژگی (از پایین به بالا)در لینک زیر حل شده است.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام و درود بر شما استاد گرامی .
منظور من از کوتاه ترین فاصله تا ریشه و ... باقی داستان در این مثال کذایی بود و نگفتم این روش کلیت دارد و حرف شما در این باره کاملا منطقی است ، در مورد ذکر حالت کلی ویژگی ذکر شده ممنونم از توضیح خوبتون و تستی که حل کردید رو حتما بررسی میکنم ...
مرسی ار راهنماییتون