(۱۱ فروردین ۱۳۹۵ ۰۸:۱۷ ق.ظ)shirin0101 نوشته شده توسط:  سلام
این جمله پوران گفته درست هست...
درخت قرمز سیاه با ۱۲۸ گره حداقل یک گره قرمز دارد
چطوری میشه درختش ؟ چجوری کلا باید تشخیص بدیم ؟ مثلا درخت که پر باشه خب میشه صفر تا گره قرمز ولی با ۱۲۸ تا چجوری میشههه فهمید؟
تشکر

سلام.
بهترین درختی که ۱۲۸ گره ای باشه و کمترین گره قرمز رو داشته باشه-->میشه یک درخت پر ۱۲۷ گره ای باشه،که یک گره به عنوان فرزند یکی از گره های سطح آخرش در نظر میگیریم.که میشه ۱۲۸ گره.
در این صورت همه مسیر ها از یک گره به برگ،دارای تعداد گره سیاه یکسانند،غیر مسیرهایی که شامل اون گره اضافه شده هستند.اون گره اضافه شده اگه قرمز باشه،همه چی درست میشه و تمام مسیرهایی که از یک گره به برگ ها میرسند،شامل تعداد گره سیاه یکسانی میشند.
پس درختی قرمز سیاه با ۱۲۸ گره،حداقل یک گره قرمز داره.
واسه سادگی میتونید درختی با ۸ گره رو امتحان کنید.(یک درخت پر ۷ گره ای سیاه بکشید،و یک گره به درخت اضافه کنید،که اون گره حتما باید قرمز باشه تا درخت قرمز سیاه بشه)

سلام از کاربر IranianWizard بابت جواب دادن به سوالات تشکر میکنم
من برای جواب دادن به این سوال برای خودم اینطوری مثال میزنم (مثل گفته IranianWizard) که تو این عکس اون گره آخر که قرار رنگ آمیزی بشه باید چه رنگی بگیره که خاصیت درخت قرمز و سیاه پابرجا بمونه؟
خاصیت درخت قرمز و سیاه یک درخت جست و جوی دودویی
که از هر گره ای به سمت زیرگره ها حرکت کنیم به تعداد برابر گره سیاه وجود داشته باشه