تالار گفتمان مانشت

سلام

حداقل و حداکثر تعداد گره های قرمز در یک درخت قرمز-سیاه با ۵۱۱ گره دقیقا" چند است ؟

من اینطوری حل کردم که اگه حداقل تعداد گره های قرمز و بخواد چون با ۵۱۱ گره میشه یک درخت کامل ساخت پس ۰ عدد گره قرمز میتونه داشته باشه ولی برای حداکثر تعداد گره قرمز ارتفاع درخت ۸ میشه و تعداد سطح ۹ هستش ریشه که طبق قاعده درخت قرمز-سیاه باید سیاه باشه میمونه بقیه سطح ها که یکی در میون قرمز و سیاه درنظر میگیریم پس حداکثر تو سطح دوم ۲ تا گره قرمز ، سطح چهارم 8 تا ... الی سطح هفتم ۱۲۸ تا پس در مجموع حداکثر : ۲+۸+۳۲+۱۲۸ = ۱۷۰ گره قرمز داریم ، درست حل کردم ؟

لطفا" اگه غلط هستش یا ایده دیگه ای برای حل دارین بگید .

مرسی

سلام و وقت بخیر ...
کاملا درسته ....

با ۵۱۱ نود میتوان یک درخت کاملا متوازن با ۹ سطح رسم کرد - درختی کاملا پر ( ریشه را سطح یک فرض میکنیم ) ... خوب طبق قانون درخت RB ریشه ( سطح اول ) و گره های فرضی ( فرزند های برگ ها ) را باید به رنگ مشکی در آوریم حال سراغ خواسته سوال میرویم ..

همون جور که جناب عالی ذکر کردید میشه باقی مانده گره های درخت را مشکی کرد و همه قوانین RB نیز محفوظ است پس برای حالت حداقل ، ۰ گره قرمز داریم ( همه گره های را مشکی میکنیم ) ...
برای حالت حداکثر ، چون قانون RB میگه همه فرزند های یک گره قرمز باید مشکی باشن ، باید از بیشترین سطح ممکن از انتهای درخت ، یعنی سطح انتهایی ( سطح 9 ) شروع کرده و همه گره های این سطح را قرمز کنیم ، سپس سطح بالایی مشکی و به همین ترتیب به سمت ریشه حرکت میکنیم ، کلیه گره های سطح 9 ، 7 ، 5 ، 3 را میتوان به رنگ قرمز تبدیل کرد ، پس در حالت کلی با توجه به این که حداکثر تعداد گره در سطح [tex]n[/tex] ام درخت پر برابر با [tex]2^{n-1}[/tex] است مجموع گره های قرمز برابر با [tex]2^2+2^4+2^6+2^8=340[/tex] است
برای راحتی به نظرم این گونه سوالا ، یک شاخه از ریشه تا برگ بکش و همه مراحل رو روش انجام بده و بعد ببین هر سطح چند تا گره میتونه داشته باشه و همه رو با هم جمع کن ...

(12 فروردین 1396 11:17 ب.ظ)alireza01 نوشته شده توسط: [ -> ]سلام و وقت بخیر ...
کاملا درسته ....

با ۵۱۲ نود میتوان یک درخت کاملا متوازن با ۹ سطح رسم کرد - درختی کاملا پر ( ریشه را سطح یک فرض میکنیم ) ... خوب طبق قانون درخت RB ریشه ( سطح اول ) و گره های فرضی ( فرزند های برگ ها ) را باید به رنگ مشکی در آوریم حال سراغ خواسته سوال میرویم ..

همون جور که جناب عالی ذکر کردید میشه باقی مانده گره های درخت را مشکی کرد و همه قوانین RB نیز محفوظ است پس برای حالت حداقل ، ۰ گره قرمز داریم ( همه گره های را مشکی میکنیم ) ...
برای حالت حداکثر ، چون قانون RB میگه همه فرزند های یک گره قرمز باید مشکی باشن میتوان یک سطح در میان همه گره ها را قرمز کنیم ، یعنی ابتدا فرزند های ریشه ( که ۲ تا هست ) قرمز و به همین ترتیب همه نود های سطح های ۴ ، ۶ و ۸ را میتوان قرمز کرد پس در حالت کلی با توجه به این که حداکثر تعداد گره در سطح [tex]n[/tex] ام درخت پر برابر با [tex]2^{n-1}[/tex] است مجموع گره های قرمز برابر با [tex]2^1+2^3+2^5+2^7=170[/tex] است که به درستی عنوان کردید .
برای راحتی به نظرم این گونه سوالا ، یک شاخه از ریشه تا برگ بکش و همه مراحل رو روش انجام بده و بعد ببین هر سطح چند تا گره میتونه داشته باشه و همه رو با هم جمع کن ...

بله دقیقاً ، ممنون برای پاسخ

سلام
درباره این سوال نکته ای که ذهن را به خود مشغول می کند این است که در درخت قرمز سیاه نود برگ نداریم یا بهتر بگیم به اشاره گرهای تهی نود ها برگ گفته می شود یعنی برای برگ ها در RB نباید از واژه نود استفاده کرد پس زمانی که گفته می شود یک در خت قرمز سیاه با n نود باید یا بهتر است این n نود را تماما نود داخلی بگیریم .در این سوال هم بهتر است ۵۱۱ نود را نود داخلی بگیریم البته ۵۱۲ اشاره گر تهی(برگ ) هم خواهیم داشت.
با این توصیف حداقل نود های قرمز باز صفر می شود و حداکثر ۳۴۰(دو سطح اول را سیاه بعد سطح بعدی ر اقرمز وسطح بعدی سیاه و.... ) و ۱۷۱ نود داخلی هم سیاه رنگ خواهیم داشت که این همان حداقل نود های داخلی سیاه و حداکثر هم که ۵۱۱ است

(13 فروردین 1396 03:49 ب.ظ)msour44 نوشته شده توسط: [ -> ]سلام
درباره این سوال نکته ای که ذهن را به خود مشغول می کند این است که در درخت قرمز سیاه نود برگ نداریم یا بهتر بگیم به اشاره گرهای تهی نود ها برگ گفته می شود یعنی برای برگ ها در RB نباید از واژه نود استفاده کرد پس زمانی که گفته می شود یک در خت قرمز سیاه با n نود باید یا بهتر است این n نود را تماما نود داخلی بگیریم .در این سوال هم بهتر است ۵۱۱ نود را نود داخلی بگیریم البته ۵۱۲ اشاره گر تهی(برگ ) هم خواهیم داشت.
با این توصیف حداقل نود های قرمز باز صفر می شود و حداکثر ۳۴۰(دو سطح اول را سیاه بعد سطح بعدی ر اقرمز وسطح بعدی سیاه و.... ) و ۱۷۱ نود داخلی هم سیاه رنگ خواهیم داشت که این همان حداقل نود های داخلی سیاه و حداکثر هم که ۵۱۱ است

حق با شماست نباید برای دیدن ماکسیمم گره قرمز نباید از بالا نگاه کرد بلکه باید از بیشترین سطح ممکن ( از پایین به بالا ) رنگ آمیزی را آغاز کرد ، پاسخم را اصلاح کردم و ممنون از شما

(13 فروردین 1396 03:49 ب.ظ)msour44 نوشته شده توسط: [ -> ]سلام
درباره این سوال نکته ای که ذهن را به خود مشغول می کند این است که در درخت قرمز سیاه نود برگ نداریم یا بهتر بگیم به اشاره گرهای تهی نود ها برگ گفته می شود یعنی برای برگ ها در RB نباید از واژه نود استفاده کرد پس زمانی که گفته می شود یک در خت قرمز سیاه با n نود باید یا بهتر است این n نود را تماما نود داخلی بگیریم .در این سوال هم بهتر است ۵۱۱ نود را نود داخلی بگیریم البته ۵۱۲ اشاره گر تهی(برگ ) هم خواهیم داشت.
با این توصیف حداقل نود های قرمز باز صفر می شود و حداکثر ۳۴۰(دو سطح اول را سیاه بعد سطح بعدی ر اقرمز وسطح بعدی سیاه و.... ) و ۱۷۱ نود داخلی هم سیاه رنگ خواهیم داشت که این همان حداقل نود های داخلی سیاه و حداکثر هم که ۵۱۱ است

بله کتاب قدسی هم الان نگاه کردم که صحبت شما رو تایید میکنه پس همیشه تعداد عناصری که گفته میشه تعداد عناصر داخلی هستش نه کل گره ها