سلام
از ویژگی هی درخت RB :
رنگ ریشه سیاه است. رنگ برگ ها هم سیاه است(تعریف برگ در RB متفاوت است مثلا در این درخت۱و۸و۲۲ برگ نیستند بلکه برگ نود های nill نودهای موجود در درخت هستند مثلا نود ۸دو برگ دارد و نود ۹ یک برگ و ...پیش فرض این برگ ها ترسیم نمی شوندبرای راحتی حل بهتر است برگ ها را ترسیم کنیم البته طبق تعریف با رنگ سیاه).ویژگی دیگر اگر نودی قرمز باشد فرزندان ان سیاه است و(مهم)برای هر نوداگر از ان نود به سمت هر یک از برگ های موجود در زیردختانش حرکت کنیم تعداد نود سیاه یکسانی پیمایش می شود.
در درخت مطر ح شده اگر از گره ۹ به زیردرخت راستش حرکت کنیم فقط یک برگ که سیاه دیده می شود. پس با حرکت در زیر درخت چپ هم باید تا رسیدن به هریک از برگ هم یک نود سیاه پیمایش شود در زیردرخت چپ ۹ دو برگ نود۸ وجود دارد پس نود ۸ حتما قرمز باید باشد تا در زیردرخت چپ تا رسیدن به یک برگ یک نود سیاه پیمایش شود مثل زیردرخت راستش. درنتیجه ۹ هم سیاه است(چون ۸ قرمز است و۹ اگر قرمز باشد ویژگی اگر نودی قرمز باشد فرزندان ان سیاه است را نقض می کند)پس تا اینجا ۸ حتما قرمز و ۹ هم حتما سیاه است.همین روند برای نود های ۱۴ و ۲۲ هم برقرار است با حرکت در چپ ۱۴ یک نود سیاه پیمایش می شود پس باحرکت در راست ۱۴ هم تا رسیدن به برگ های ۲۲ باید یک نود سیاه دیده شود پس ۲۲ قرمز در نتیجه ۱۴ سیاه باید باشد.فقط حالت های ۶ و ۱ باقی مانده است.اگر در راست ۶ حرکت کنیم تا رسیدن به هر برگ دو نود سیاه دیده می شود پس باید ۱ هم سیاه باشد تا در چپ ۶ هم تا رسیدن به برگ های ۱ دو تا نود سیاه پیمایش شود.اگر در راست ۱۳(ریشه) حرکت کنیم تا هر برگ دو تا سیاه دیده میشود پس ۶ باید قرمز باشد تا در چپ ۱۳ هم دو تود سیاه دیده شود.خود ۱۳ هم چون ریشه است سیاه است پس نود های ۱و۹و۱۳و۱۴ سیاه و ۶ و۸و۲۲ قرمزانددر نتیجه فقط یک حالت برای رنگ امیزی این درخت وجود دارد یعنی گزینه ۲