درخت سرخ-سیاه متمایل به چپ

درخت سرخ-سیاه متمایل به چپ یک درخت جستجوی دودویی است که ویژگی‌های زیر را دارد:

1. گره می‌تواند رنگ سرخ یا رنگ سیاه داشته باشد.
2. ریشه همیشه رنگ سیاه دارد.
3. برگ‌ها (که همیشه گره تهی هستند) رنگ سیاه دارند.
4. همه مسیرها از هر گره به همه نوادگانش به تعداد یکسان گره سیاه دارد.

درخت سرخ-سیاه متمایل به چپ دارای دو نوع ارتفاع است:

• ارتفاع معمولی: اندازه طولانی‌ترین مسیر از برگ‌ها تا ریشه که معمولاً با h نشان داده می‌شود.
• ارتفاع سیاه هر گره: ارتفاع سیاه برای گره x برابر است با تعداد گره‌های سیاه از گره x به نوادگان برگی‌اش با احتساب رنگ برگ و عدم احتساب رنگ خود x، که معمولاً با bh نشان داده می‌شود.

قضیه در درخت سرخ-سیاه با n راس روابط زیر برقرار است:

• ${\displaystyle h\leq 2*log(n+1).}$
• ${\displaystyle bh\leq log(n+1).}$
• ${\displaystyle h\leq 2*bh.}$

طبق قضیه بالا ارتفاع درخت سرخ-سیاه از مرتبه ${\displaystyle log(n)}$ است. در نتیجه تمام اعمال اصلی در آن از مرتبه ${\displaystyle log(n)}$ انجام می‌شود.

• Charles E. Leiserson, Ronald L. Rivest, Thomas H. Cormen and Clifford Stein (۲۰۰۱)، «Chapter ۱۳»، مقدمه‌ای بر الگوریتم‌ها (ویراست ۲nd Edition)، MIT Press and McGraw-Hill، ص. ۲۷۳-۳۰۱، شابک ۰-۲۶۲-۰۳۲۹۳-۷نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (رده) نگهداری یادکرد:متن اضافی (رده)

• Robert Sedgewick. Left-leaning Red–Black Trees. لینک مستقیم به پرونده.