درخت‌های قرمز-سیاه: چگونه درخت‌های جستجوی خودمتوازن‌کننده ارتفاع لگاریتمی را تضمین می‌کنند

چرا درخت‌های جستجوی دودویی ساده کافی نیستند

همان‌طور که پیش‌تر در این مجموعه بحث شد، هر عملیات یک درخت جستجوی دودویی ساده در زمان O(h) اجرا می‌شود، جایی که h ارتفاع درخت است. مسئله این است که h می‌تواند تحت ترتیب‌های درج خاصی، مانند درج داده از‌قبل‌مرتب‌شده، تا Θ(n) رشد کند، که هر عملیات را به زمان خطی تنزل می‌دهد. یک Red-Black Tree (درخت قرمز-سیاه) این را با افزودن ساختار اضافه‌ای که از نظر ریاضی h = O(log n) را همیشه تضمین می‌کند، صرف‌نظر از ترتیب درج‌ها و حذف‌ها، حل می‌کند.

پنج ویژگی قرمز-سیاه

یک درخت قرمز-سیاه یک درخت جستجوی دودویی است، با استفاده از دقیقاً همان ساختار گره زیربنایی معرفی‌شده پیش‌تر در این مجموعه، با یک ویژگی اضافه به‌ازای هر گره: یک Color (رنگ)، قرمز یا سیاه. یک درخت جستجوی دودویی یک درخت قرمز-سیاه معتبر واجد شرایط می‌شود اگر و فقط اگر هر پنج ویژگی زیر را برآورده کند:

۱. هر گره یا قرمز است یا سیاه.
۲. ریشه همیشه سیاه است.
۳. هر برگ (نمایانده‌شده به‌عنوان NIL) سیاه است.
۴. اگر یک گره قرمز باشد، هر دو فرزندش سیاه‌اند.
   (هیچ دو گره قرمزی نمی‌توانند پیاپی روی هیچ مسیری ظاهر شوند.)
۵. برای هر گره، همه مسیرهای ساده از آن گره تا
   برگ‌های نوادگان تعداد یکسانی گره سیاه دارند.
   (این تعداد Black-Height (ارتفاع سیاه) گره نامیده می‌شود.)

چرا این ویژگی‌ها ارتفاع لگاریتمی را تضمین می‌کنند

ویژگی ۴ تضمین می‌کند هیچ مسیری نمی‌تواند دو گره قرمز پیاپی داشته باشد، و ویژگی ۵ تضمین می‌کند هر مسیر از یک گره مشخص دقیقاً همان تعداد گره سیاه دارد. با هم، این ویژگی‌ها محدود می‌کنند طولانی‌ترین مسیر چقدر می‌تواند نسبت به کوتاه‌ترین مسیر از ریشه طولانی‌تر باشد: طولانی‌ترین مسیر ممکن بین گره‌های قرمز و سیاه تناوب می‌کند، و حداکثر طول کوتاه‌ترین مسیر ممکن، که فقط از گره‌های سیاه تشکیل شده، را دو برابر می‌کند.

قضیه کلیدی: یک درخت قرمز-سیاه با n گره داخلی
حداکثر ارتفاع 2·log₂(n+1) دارد

طرح اثبات: زیردرخت ریشه‌دار در هر گره x حداقل
2^(bh(x)) - 1 گره داخلی دارد، جایی که bh(x) ارتفاع سیاه
x است. اعمال این در ریشه، ترکیب‌شده با این حقیقت که
حداقل نیمی از گره‌ها روی هر مسیر از ریشه به برگ
باید سیاه باشند (ویژگی ۴)، کران ارتفاع O(log n) را می‌دهد.

این تضمین ریاضی چیزی است که درخت‌های قرمز-سیاه را قابل‌اعتماد می‌کند: صرف‌نظر از هر توالی از درج‌ها و حذف‌هایی که رخ می‌دهد، ارتفاع درخت هرگز از O(log n) فراتر نمی‌رود، و اطمینان می‌دهد هر عملیات درخت-جستجو که پیش‌تر در این مجموعه بحث شد — جستجو، حداقل، حداکثر، جانشین، درج، و حذف — در زمان O(log n) تضمین‌شده اجرا شود.

چرخش‌ها: بازساختاردهی همراه با حفظ ترتیب

حفظ ویژگی‌های قرمز-سیاه در طول درج و حذف نیازمند یک عملیات ساختاری به نام Rotation (چرخش) است، که ساختار اشاره‌گر محلی درخت را تغییر می‌دهد، اما ویژگی درخت-جستجوی-دودویی که پیش‌تر در این مجموعه بحث شد را حفظ می‌کند.

LEFT-ROTATE(T, x):
  y = x.right
  x.right = y.left
  اگر y.left ≠ NIL:
      y.left.p = x
  y.p = x.p
  اگر x.p == NIL:
      T.root = y
  در غیر این صورت اگر x == x.p.left:
      x.p.left = y
  در غیر این صورت:
      x.p.right = y
  y.left = x
  x.p = y

پیش از LEFT-ROTATE(x):        پس از LEFT-ROTATE(x):
        x                              y
       / \                            / \
      a   y          -->             x   c
         / \                        / \
        b   c                      a   b

RIGHT-ROTATE دقیقاً تصویر آینه‌ای است. حیاتی است که یک چرخش در زمان O(1) اجرا می‌شود، چون فقط شامل به‌روزرسانی تعداد ثابتی اشاره‌گر است، و هرگز ویژگی درخت-جستجوی-دودویی را نقض نمی‌کند — ترتیب نسبی همه عناصر دقیقاً یکسان باقی می‌ماند، فقط شکل درخت تغییر می‌کند.

درج: رنگ کن، سپس اصلاح کن

درج به یک درخت قرمز-سیاه با رویه درج معمولی درخت-جستجوی-دودویی که پیش‌تر در این مجموعه پوشش داده شد شروع می‌شود، با گره جدید که ابتدا قرمز رنگ می‌شود. رنگ‌آمیزی گره جدید با قرمز یک انتخاب عمدی است: نمی‌تواند ویژگی ۵ (ویژگی ارتفاع سیاه) را نقض کند، چون یک گره قرمز چیزی به تعداد سیاه هیچ مسیری اضافه نمی‌کند، اما ممکن است ویژگی ۴ را نقض کند اگر والد گره جدید نیز قرمز باشد.

RB-INSERT-FIXUP(T, z):
  تا زمانی که z.p.color == RED:
      اگر z.p == z.p.p.left:
          y = z.p.p.right   // عموی z
          اگر y.color == RED:
              // حالت ۱: عمو قرمز است — دوباره‌رنگ کن و بالا برو
              z.p.color = BLACK
              y.color = BLACK
              z.p.p.color = RED
              z = z.p.p
          در غیر این صورت:
              اگر z == z.p.right:
                  // حالت ۲: عمو سیاه است، z فرزند راست است
                  z = z.p
                  LEFT-ROTATE(T, z)
              // حالت ۳: عمو سیاه است، z فرزند چپ است
              z.p.color = BLACK
              z.p.p.color = RED
              RIGHT-ROTATE(T, z.p.p)
      در غیر این صورت:
          (حالت‌های متقارن، با چپ و راست جابه‌جا)
  T.root.color = BLACK

رویه اصلاح سه حالت متمایز بر اساس رنگ عموی گره تازه‌درج‌شده را مدیریت می‌کند. وقتی عمو قرمز است، نقض می‌تواند صرفاً با دوباره‌رنگ‌کردن و بالابردن مسئله به‌سمت ریشه حل شود. وقتی عمو سیاه است، یک یا دو چرخش ترکیب‌شده با دوباره‌رنگ‌کردن به‌طور دائمی نقض را حل می‌کنند بدون نیاز به ادامه به‌سمت بالا. از آنجا که هر تکرار یا پایان می‌یابد یا یک سطح بالا می‌رود، و چرخش‌ها حداکثر دو بار رخ می‌دهند، کل رویه اصلاح در زمان O(log n) اجرا می‌شود، که با ارتفاع درخت مطابقت دارد.

حذف: جزئی‌ترین عملیات

حذف از همان رویکرد پایه مبتنی بر transplant درخت-جستجوی-دودویی معمولی که پیش‌تر در این مجموعه بحث شد پیروی می‌کند، اما نیازمند مدیریت دقیق است وقتی یک گره سیاه حذف شود، چون این می‌تواند ویژگی ارتفاع سیاه را برای مسیرهایی که از آن عبور می‌کردند نقض کند.

این تکنیک یک Extra