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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
درخت سرخ-سیاه متمایل به چپ
نوع درخت
سال اختراع شدن ۲۰۰۸
اختراع شده توسط رابرت سجویک
پیچیدگی زمانی
بر حسب نماد اوی بزرگ
میانگین بدترین حالت
فضا 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) انجام می‌شود.

منابع[ویرایش]