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

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

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