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

درخت سرخ-سیاه متمایل به چپ
گونه	درخت
سال اختراع	۲۰۰۸
مخترع	رابرت سجویک
زمان اجرای الگوریتم بر پایه نماد O بزرگ
الگوریتم میانگین بدترین حالت فضا O(n) O(n) جستجو O(log n) O(log n) درج O(log n) O(log n) حذف O(log n) O(log n)

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

ویژگی‌ها

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

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

ارتفاع درخت

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

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

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

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

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

طبق قضیه بالا ارتفاع درخت سرخ-سیاه از مرتبه $log(n)$ است. در نتیجه تمام اعمال اصلی در آن از مرتبه $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. لینک مستقیم به پرونده.