درخت سرخ-سیاه متمایل به چپ
درخت سرخ-سیاه متمایل به چپ یکی از انواع درخت‌های متعادل‌کننده است. این درخت از زیرشاخه‌های درخت سرخ-سیاه است. در این درخت گره سرخ تنها می‌تواند فرزند سمت چپ باشد، به همین دلیل به آن درخت سرخ-سیاه متمایل به چپ می‌گویند.
| درخت سرخ-سیاه متمایل به چپ | ||
|---|---|---|
| نوع | درخت | |
| سال اختراع شدن | ۲۰۰۸ | |
| اختراع شده توسط | رابرت سجویک | |
| پیچیدگی زمانی بر حسب نماد اوی بزرگ | ||
| میانگین | بدترین حالت | |
| فضا | 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 راس روابط زیر برقرار است:
طبق قضیه بالا ارتفاع درخت سرخ-سیاه از مرتبه است. در نتیجه تمام اعمال اصلی در آن از مرتبه انجام می‌شود.
منابع
- Charles E. Leiserson, Ronald L. Rivest, Thomas H. Cormen and Clifford Stein (۲۰۰۱)، «Chapter ۱۳»، مقدمه‌ای بر الگوریتم‌ها (ویراست ۲nd Edition)، MIT Press and McGraw-Hill، ص. ۲۷۳-۳۰۱، شابک ۰-۲۶۲-۰۳۲۹۳-۷
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.