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

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

ویژگی‌ها

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

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

ارتفاع درخت

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

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

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

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

• $h\le 2*log(n+1).$
• $bh\le log(n+1).$
• $h\le 2*bh.$

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

منابع

• الگو:یادکرد

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