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

{{جعبه اطلاعات ساختمان داده
|نام                    = درخت سرخ-سیاه متمایل به چپ
|تصویر                  = Left-leaning red–black tree.png
|نوع                    = درخت
|مخترع                  = [[رابرت سجویک]]
|سال اختراع             = ۲۰۰۸
|میانگین فضا            = O(n)
|فضا در بدترین حالت     = O(n)
|میانگین جستجو          = O(log n)
|جستجو در بدترین حالت   = O(log n)
|میانگین درج            = O(log n)
|درج در بدترین حالت     = O(log n)
|میانگین حذف            = O(log n)
|حذف در بدترین حالت     = O(log n)
}}

'''درخت سرخ-سیاه متمایل به چپ''' یکی از انواع درخت‌های متعادل‌کننده است. این درخت از زیرشاخه‌های '''[[درخت سرخ-سیاه]]''' است. در این درخت گره سرخ تنها می‌تواند فرزند سمت چپ باشد، به همین دلیل به آن درخت سرخ-سیاه متمایل به چپ می‌گویند.

== ویژگی‌ها ==
درخت سرخ-سیاه متمایل به چپ یک [[درخت جستجوی دودویی]] است که ویژگی‌های زیر را دارد:
# گره می‌تواند رنگ سرخ یا رنگ سیاه داشته باشد.
# ریشه همیشه رنگ سیاه دارد.
# برگ‌ها (که همیشه گره تهی هستند) رنگ سیاه دارند.
# همه مسیرها از هر گره به همه نوادگانش به تعداد یکسان گره سیاه دارد.

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

== متعادل بودن درخت سرخ-سیاه متمایل به چپ ==
'''قضیه'''  در درخت سرخ-سیاه با n راس روابط زیر برقرار است:
*<math>
h \leq 2*log(n+1).
</math>
*<math>
bh \leq log(n+1).
</math>
*<math>
h \leq 2*bh.
</math>

طبق قضیه بالا ارتفاع درخت سرخ-سیاه از مرتبه <math>log(n)</math> است. در نتیجه تمام اعمال اصلی در آن از مرتبه <math>log(n)</math> انجام می‌شود.

== منابع ==
{{پانویس}}
* {{یادکرد
|فصل=Chapter 13
|نویسنده=Charles E. Leiserson, Ronald L. Rivest, Thomas H. Cormen and Clifford Stein
|کتاب=[[مقدمه‌ای بر الگوریتم‌ها]]
|ویرایش=2nd Edition 
|ناشر=MIT Press and McGraw-Hill
|صفحه=273-301
|سال=2001
|شابک=0-262-03293-7}}
{{پایان چپ‌چین}}
[[رده:جستجوی درخت‌ها]]
[[رده:ساختار درختی]]

* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.282 Robert Sedgewick. Left-leaning Red–Black Trees]. [http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf لینک مستقیم به پرونده].