====== درخت قرمز-سیاه ======


یک درخت قرمز-سیاه، یک درخت جستجوی دودویی است که دارای خواص زیر است:

  - هیچ راسی دارای یک برگ نیست.
  - هر راس یا با رنگ سیاه یا با رنگ قرمز رنگ شده است.
  - هر  برگ(برگ‌ها راس‌های $Nil$  هستند که روی آن‌ها عددی نوشته نشده است.) سیاه است.
  - اگر راسی قرمز بود هر دو بچه‌ی آن سیاه هستند.
  - تمام مسیر‌ها از یک راس به برگ‌های زیری آن دارای تعداد یکسانی راس سیاه هستند.

ثابت کنید هر درخت دودویی با $n$ ‌راس  حداکثر دارای ارتفاع $2log(n+1)$  است. 

<پاسخ>



</پاسخ>


  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]