(۱۹ بهمن ۱۳۹۳ ۰۲:۳۵ ب.ظ)navid_itboy نوشته شده توسط: (19 بهمن ۱۳۹۳ ۰۲:۲۵ ب.ظ)hamedmohsenee نوشته شده توسط: بزارین تحلیل ایدین نصیری شرق رو توی ۶۰۰ مساله ببینیم:
البته قبلش باید قانونای حاکم بر درخت قرمز سیاهو بدونی:
نصیری شرق برای ۱۲۸ نود نوشته:
درختی که تمام گره های آن سیاه است باید تمام مسیرهای از ریشه تا برگ آن هم طول بوده و درنتیجه کامل است.از سوی دیگر می دانیم تعداد گره های یک درخت کامل برابر ۲ به توان k منهای یک است و ۱۲۸=۲به توان ۷
این الان یعنی چی؟؟؟؟جالبه چیزیو به چیز دیگری ربط دادین...من خودم حس میکنم ۱۰ نمیشه چون ۱۰ حداقل تعداد گره سیاهه اگر ۱۰۲۳ نود داشته باشیم با توجه به فرمول n=2^bh-1 که bh همون black node ها هسن .اما ۰ هم با این توضیحات قانع کننده نیس......
یکی از مفاهیم قرمز سیاه سیاه ارتفاع هر درخته که تعداد نودهای سیاه اون نوده تا رسیدن به یک برگ و در هر مسیر از اون نود تا یک برگ باید برابر باشن.
می دونیم د.د.ج که متوازنه و ۱۰۲۳ تا گره داره حتما یه درخت کامله.الان اگر بخوایم از ریشه به هرکدوم از برگها بریم مسیرها تماما یک اندازه ان و هنگام رنگ آمیزی دیگه هیچ نیازی نخواهد بود که نود قرمزی اضافه کنیم تا سیاه ارتفاع ریشه رو جور کنیم.توی فرایند رنگ امیزی هر نودی رو که قرمز کنیم سیاه ارتفاع ریشه درخت به هم خواهد ریخت
به هنظر من اگر نحوه رنگ امیزی قرمزسیاهو مطالعه کنیم متوجه خواهیم شد
