آموزش انواع عملیات در درخت قرمز سیاه

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

عملیات درج در درخت قرمز-سیاه

قوانین زیر برای درج در درخت قرمز-سیاه استفاده می‌شود:

1. اگر درخت خالی است، یک گره جدید به عنوان گره ریشه با رنگ سیاه ایجاد می‌کنیم.
2. اگر درخت خالی نباشد، یک گره جدید به عنوان گره برگ با رنگ قرمز ایجاد می‌کنیم.
3. اگر والد گره جدید سیاه است، از آن خارج شوید.
4. اگر والد گره جدید قرمز باشد، باید رنگ گره کناری گره جدید را بررسی کنیم.
   • اگر رنگ مشکی باشد، چرخش و رنگ‌آمیزی دوباره را انجام می‌دهیم.
   • اگر رنگ قرمز باشد، گره را دوباره رنگ می‌کنیم؛ همچنین بررسی خواهیم کرد که آیا والد والد گره جدید، گره ریشه است یا خیر. اگر گره ریشه نباشد، گره را دوباره رنگ کرده و دوباره بررسی می‌کنیم.

مثال

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

10، 18، 7، 15، 16، 30

1. مرحله 1: در ابتدا، درخت خالی است، بنابراین یک گره جدید با مقدار 10 ایجاد می کنیم. این اولین گره درخت است، بنابراین گره ریشه آن خواهد بود. همانطور که قبلاً گفتیم، گره ریشه باید سیاه باشد که در زیر نشان داده شده است:
2. مرحله 2: گره بعدی 18 است. از آنجایی که 18 بزرگتر از 10 است، همانطور که در زیر نشان داده شده است در سمت راست 10 قرار می گیرد.
   قانون دوم درخت قرمز سیاه را می‌دانیم که اگر درخت خالی نباشد، گره تازه ایجاد شده رنگ قرمز خواهد داشت بنابراین، گره 18 دارای رنگ قرمز است، همانطور که در شکل زیر نشان داده شده است:
   اکنون قانون سوم درخت قرمز-سیاه را بررسی می کنیم، یعنی اینکه آیا والد گره جدید سیاه است یا خیر. در شکل بالا، والد گره سیاه است بنابراین، این درخت، یک درخت قرمز-سیاه است.
3. مرحله 3: اکنون گره جدیدی با مقدار 7 با رنگ قرمز ایجاد می‌کنیم. از آنجایی که 7 کمتر از 10 است، همانطور که در زیر نشان داده شده است، در سمت چپ 10 قرار می‌گیرد:اکنون قانون سوم درخت قرمز-سیاه را بررسی می کنیم، یعنی اینکه آیا والد گره جدید سیاه است یا خیر. همانطور که مشاهده می‌کنیم، والد گره 7 سیاه رنگ است و از ویژگی های درخت قرمز-مشکی تبعیت می‌کند.
4. مرحله 4: عنصر بعدی 15 است و 15 بزرگتر از 10 اما کمتر از 18 است، بنابراین گره جدید در سمت چپ گره 18 ایجاد می‌شود. رنگ گره 15 قرمز خواهد بود زیرا درخت خالی نیست.
   درخت فوق ویژگی درخت قرمز-سیاه را نقض می‌کند زیرا دارای یک رابطه والد-فرزند قرمز-قرمز است. اکنون باید قوانینی را برای ساختن درخت قرمز-مشکی اعمال کنیم. قانون 4 می‌گوید که اگر والد گره جدید قرمز باشد، باید رنگ گره کناری والد گره جدید را بررسی کنیم. گره جدید گره 15 است. والد گره جدید گره 18 است و گره کناری آن، گره 7 است. از آنجایی که رنگ گره 7 قرمز است، قانون 4a را اعمال می‌کنیم. قانون 4a می‌گوید که ما باید هم گره والد و هم گره کناری والد را دوباره رنگ کنیم بنابراین، هر دو گره یعنی 7 و 18، همانطور که در شکل زیر نشان داده شده است، دوباره رنگ می‌شوند:همچنین باید بررسی کنیم که آیا والد والد گره جدید، گره ریشه است یا خیر. همانطور که در شکل بالا مشاهده می‌کنیم، والد والد گره جدید، گره ریشه است بنابراین نیازی به رنگ آمیزی مجدد آن نیست.
5. مرحله 5: عنصر بعدی 16 است. چون 16 بزرگتر از 10 است اما کمتر از 18 و بزرگتر از 15 است، گره 16 در سمت راست گره 15 قرار می‌گیرد. درخت خالی نیست. گره 16 قرمز خواهد بود، همانطور که در شکل زیر نشان داده شده است:در شکل بالا مشاهده می‌کنیم که این درخت خصوصیت والد-فرزندی را نقض می‌کند زیرا دارای یک رابطه والد-فرزند قرمز-قرمز است. برای ساختن درخت قرمز-مشکی باید قوانینی را اعمال کنیم. از آنجایی که والد گره جدید قرمز است و والد گره جدید، گره کناری ندارد، بنابراین قانون 4a اعمال خواهد شد. قانون 4a می‌گوید که برخی از چرخش‌ها و رنگ‌آمیزی مجدد باید روی درخت انجام شود. از آنجایی که گره 16 سمت راست گره 15 است و والد گره 15 گره 18 است، گره 15 در سمت چپ گره 18 است. در اینجا ما یک رابطه LR داریم بنابراین باید دو چرخش انجام دهیم. ابتدا چرخش چپ و سپس چرخش راست را انجام می‌دهیم. چرخش چپ روی گره‌های 15 و 16 انجام می‌شود، جایی که گره 16 به سمت بالا حرکت می‌کند و گره 15 به سمت پایین حرکت می‌کند. هنگامی که چرخش چپ انجام شد، درخت مانند شکل زیر به نظر می‌رسد:در شکل بالا مشاهده می کنیم که یک رابطه LL وجود دارد. درخت فوق دارای تضاد قرمز-قرمز است بنابراین چرخش راست را انجام می‌دهیم. وقتی چرخش راست را انجام می‌دهیم، عنصر میانه گره ریشه خواهد بود. همانطور که در شکل زیر نشان داده شده است، پس از انجام چرخش سمت راست، گره 16 به گره ریشه تبدیل می‌شود و گره‌های 15 و 18 به ترتیب فرزند چپ و فرزند راست خواهند بود:پس از چرخش، گره 16 و گره 18 دوباره رنگ می‌شوند. رنگ گره 16 قرمز است بنابراین به سیاه و رنگ گره 18 سیاه می‌شود پس همانطور که در شکل زیر نشان داده شده است، به رنگ قرمز تغییر می‌کند:مرحله 6: عنصر بعدی 30 است. گره 30 در سمت راست گره 18 درج می‌شود. چون درخت خالی نیست، رنگ گره 30 قرمز خواهد بود:
6. رنگ والد و گره کناری والد گره جدید قرمز است بنابراین قانون 4b اعمال می شود. در قانون 4b، ما فقط باید رنگ‌آمیزی مجدد انجام دهیم یعنی هیچ چرخشی لازم نیست. رنگ والد (گره 18) و گره کناری والد (گره 15) سیاه می‌شود، همانطور که در تصویر زیر نشان داده شده است:همچنین باید والد والد گره جدید را بررسی کنیم که آیا گره ریشه است یا نه. والد والد گره جدید، یعنی گره 30، گره 16 است و گره 16 یک گره ریشه نیست بنابراین گره 16 را دوباره رنگ می‌کنیم و به رنگ قرمز تغییر می‌کنیم. والد گره 16 گره 10 است و قرمز نیست، بنابراین تضاد قرمز-قرمز وجود ندارد. درخت نهایی به شکل زیر خواهد بود:

عملیات حذف

حال بیایید بررسی کنیم که چگونه یک گره خاص را از درخت قرمز-سیاه حذف کنیم. قوانین زیر برای حذف گره خاص از درخت استفاده می‌شود:

مرحله 1

ابتدا قوانین BST را برای حذف اجرا می‌کنیم.

مرحله 2

حالت اول

اگر گره قرمز باشد که قرار است حذف شود، آن را حذف می‌کنیم. بیایید مورد 1 را از طریق یک مثال درک کنیم. فرض کنید می خواهیم گره 18 را از درخت زیر حذف کنیم:

در ابتدا آدرس گره ریشه را داریم. ابتدا BST را برای جستجوی گره اعمال می‌کنیم. از آنجایی که 18 بزرگتر از 10 و 16 است، 18 فرزند سمت راست گره 16 است. گره 18 یک گره برگ و قرمز است بنابراین از درخت حذف می‌شود. اگر بخواهیم گره داخلی را که دارای یک فرزند است حذف کنیم، ابتدا مقدار گره داخلی را با مقدار گره فرزند جایگزین می‌کنیم و سپس گره فرزند را حذف می‌کنیم. برای مثال درخت بالا را در نظر بگیرید و فرض کنید می‌خواهیم گره 16 را حذف کنیم:

ما نمی‌توانیم گره داخلی را حذف کنیم. ما فقط می‌توانیم مقدار آن گره را با مقدار دیگری جایگزین کنیم. گره 16 در سمت راست گره ریشه قرار دارد و فقط یک فرزند دارد، یعنی گره 18، بنابراین گره 16 با مقدار 18 جایگزین می‌شود، اما رنگ گره ثابت می‌ماند، یعنی سیاه. در پایان گره 18 (گره برگ) از درخت حذف می‌شود.

اگر بخواهیم گره داخلی که دو گره فرزند دارد را حذف کنیم، در این مورد باید تصمیم بگیریم که از کدام قسمت مقدار گره داخلی (چه زیردرخت چپ یا راست) را جایگزین کنیم. ما دو راه داریم:

• گره قبلی در پیمایش Inorder: بزرگترین مقدار موجود در زیردرخت سمت چپ را جایگزین می‌کنیم.
• گره بعدی در پیمایش Inorder: کوچکترین مقدار را در زیردرخت سمت راست جایگزین می‌کنیم.

فرض کنید می‌خواهیم گره 16 را از درخت زیر حذف کنیم:

گره 16 در سمت راست گره ریشه قرار دارد. در این صورت از گره بعدی در پیمایش Inorder استفاده خواهیم کرد. مقدار 30 کوچک‌ترین مقدار در زیردرخت سمت راست است، بنابراین مقدار 16 را با 30 جایگزین می‌کنیم، اما گره ثابت باقی می‌ماند، یعنی قرمز. پس از جایگزینی، گره برگ، یعنی 30، از درخت حذف می‌شود. از آن جایی که گره 30 یک گره برگ است و به رنگ قرمز است، باید آن را حذف کنیم (نیازی به انجام چرخش یا رنگ‌آمیزی مجدد نداریم).

حالت دوم

اگر گره ریشه نیز سیاه مضاعف است، سیاه مضاعف را بردارید و آن را تک سیاه کنید.

حالت سوم

اگر خواهر یا برادر سیاه مضاعف و فرزندانش سیاه باشند.

1. گره سیاه مضاعف را بردارید.
2. رنگ گره را به گره والد (P) اضافه کنید.
   • اگر رنگ P قرمز باشد، سیاه می‌شود.
   • اگر رنگ P سیاه باشد، سیاه مضاعف می‌شود.
3. رنگ گره کناری گره سیاه مضاعف به قرمز تغییر می‌کند.
4. اگر وضعیت سیاه مضاعف ایجاد شود موارد دیگر را اعمال خواهیم کرد.

بیایید این مورد را از طریق یک مثال بررسی کنیم. فرض کنید می‌خواهیم گره 15 را در درخت زیر حذف کنیم.

ما نمی‌توانیم به سادگی گره 15 را از درخت حذف کنیم زیرا گره 15 سیاه است. گره 15 دو فرزند دارد که NIL هستند بنابراین مقدار 15 را با مقدار NIL جایگزین می‌کنیم. از آن جایی که گره 15 و گره NIL سیاه هستند، همانطور که در شکل زیر نشان داده شده است، گره پس از جایگزینی سیاه مضاعف می‌شود:

در درخت فوق مشاهده می‌کنیم که گره کناری گره سیاه مضاعف، سیاه است و فرزندانش NIL هستند که آن هم سیاه است. از آنجایی که گره کناری گره سیاه مضاعف و فرزندانش مشکی هستند، نمی‌تواند رنگ سیاه خود را به هیچ کدام بدهد. حال گره والد سیاه مضاعف، قرمز است بنابراین گره سیاه مضاعف رنگ سیاه خود را به گره والد خود می‌دهد. همانطور که در شکل زیر نشان داده شده است، رنگ گره 16 به سیاه تغییر می‌کند، در حالی که رنگ گره NIL به یک سیاه تبدیل می‌شود.

پس از افزودن رنگ به گره والد خود، رنگ گره کناری گره سیاه مضاعف، یعنی گره 18، به قرمز تغییر می‌کند، همانطور که در شکل زیر نشان داده شده است.

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

حالت چهارم

اگر خواهر یا برادر گره سیاه مضاعف، قرمز باشد:

• رنگ پدر و مادر و گره کناری‌اش را عوض کنید.
• گره والد را در جهت سیاه مضاعف بچرخانید.
• حالت‌ها را دوباره بررسی کنید.

بیایید این مورد را از طریق یک مثال بررسی کنیم. فرض کنید می‌خواهیم گره 15 را در درخت زیر حذف کنیم:

در ابتدا، 15 با مقدار NIL جایگزین می‌شود. پس از جایگزینی، گره سیاه مضاعف می‌‍شود. از آنجایی که گره کناری گره سیاه مضاعف، قرمز است، بنابراین رنگ گره 20 به قرمز و رنگ گره 30 به سیاه تغییر می‌کند. هنگامی که تعویض رنگ انجام شد، چرخش به سمت سیاه مضاعف انجام می‌شود. همانطور که در شکل زیر نشان داده شده است، گره 30 به سمت بالا حرکت می‌کند و گره 20 به سمت پایین حرکت می‌کند:

در درخت فوق مشاهده می‌کنیم که وضعیت سیاه مضاعف همچنان در درخت وجود دارد. این حالت 3 است که در آن گره‌های کناری سیاه مضاعف، سیاه و فرزندانش نیز سیاه هستند. ابتدا سیاه مضاعف را از گره حذف می‌کنیم و رنگ سیاه را به گره اصلی آن اضافه می‌کنیم. در پایان، رنگ گره کناری سیاه مضاعف، یعنی گره 25، همانطور که در شکل زیر نشان داده شده است، به قرمز تغییر می‌کند.

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

حالت پنجم

اگر گره کناری گره سیاه مضاعف سیاه باشد، فرزند گره کناری که از سیاه مضاعف دور است سیاه است، اما فرزند نزدیک به سیاه مضاعف قرمز است.

• رنگ گره کناری گره سیاه مضاعف و فرزند گره کناری را که به گره سیاه مضاعف نزدیک‌تر است را عوض کنید.
• گره کناری را در خلاف جهت گره سیاه مضاعف بچرخانید.
• حالت 6 را اعمال کنید.

فرض کنید می‌خواهیم گره 1 را در درخت زیر حذف کنیم.

ابتدا مقدار 1 را با مقدار NIL جایگزین می‌کنیم. گره سیاه مضاعف می‌شود زیرا هر دو گره، یعنی 1 و NIL سیاه هستند. حالت 3 را به‌وجود می‌آورد که نشان می‌دهد گره کناری گره سیاه مضاعف، سیاه است و فرزندانش نیز سیاه هستند. ابتدا سیاه مضاعف گره NIL را حذف می‌کنیم. از آنجایی که والد سیاه مضاعف، سیاه است، هنگامی که رنگ سیاه به گره والد اضافه می‌شود، سیاه مضاعف می‌شود. پس از افزودن رنگ، رنگ گره کناری سیاه مضاعف مطابق شکل زیر به قرمز تغییر می‌کند:

می‌توانیم در تصویر بالا مشاهده کنیم که مشکل سیاه مضاعف هنوز در درخت وجود دارد بنابراین، حالات را مجدداً اعمال خواهیم کرد. حالت 5 را اعمال می‌کنیم زیرا گره کناری گره 7 گره 30 است که سیاه است، فرزند گره 30 که از گره 5 فاصله دارد سیاه است و فرزند گره 30 که نزدیک گره 5 است قرمز است. در این حالت ابتدا رنگ گره 30 و گره 25 را عوض می‌کنیم تا رنگ گره 30 به قرمز و رنگ گره 25 به مشکی تغییر کند.

هنگامی که تعویض رنگ گره‌ها کامل شد، باید کناری گره سیاه مضاعف را در جهت مخالف گره سیاه مضاعف بچرخانیم. در این چرخش، گره 30 به سمت پایین حرکت می‌کند در حالی که گره 25 به سمت بالا حرکت می‌کند، همانطور که در زیر نشان داده شده است:

همانطور که در درخت فوق مشاهده می‌کنیم، آن وضعیت سیاه دوگانه هنوز وجود دارد. بنابراین، ما باید مورد 6 را بررسی کنیم. ابتدا ببینیم حالت ششم چیست.

حالت ششم

اگر گره کناری گره سیاه مضاعف، سیاه باشد و فرزند دورش قرمز باشد:

• رنگ والد و گره کناری آن را عوض کنید.
• والد را به سمت گره سیاه مضاعف بچرخانید.
• گره سیاه مضاعف را حذف کنید.
• رنگ قرمز را به مشکی تغییر دهید.

ما مورد 6 را در مثال بالا برای حل وضعیت سیاه مضاعف اعمال می‌کنیم. در مثال بالا، گره 5 سیاه مضاعف است و گره کناری گره 7 گره 25 است که سیاه است. فرزند دور گره کناری گره سیاه مضاعف گره 30 است که رنگ قرمز دارد. ابتدا رنگ های والد و گره کناری اش را عوض می‌نیم. والد گره 7 گره 10 است و گره کناری اش گره 25 است. رنگ هر دو گره سیاه است بنابراین هیچ جابجایی رخ نمی‌دهد. در مرحله دوم باید والد را در جهت مشکی دوتایی بچرخانیم. پس از چرخش، گره 25 به سمت بالا حرکت می‌کند، در حالی که گره 10 به سمت پایین حرکت می‌کند. همانطور که در شکل زیر نشان داده شده است، پس از انجام چرخش، درخت به شکل زیر خواهد بود:

در مرحله بعد سیاهی مضاعف را از گره 7 حذف می‌کنیم و گره 7 رنگ سیاه خود را به فرزند دور یعنی گره 30 می‌دهد بنابراین رنگ گره 30 مانند شکل زیر به سیاه تبدیل می‌شود:

جمع‌بندی

در این مقاله به بررسی عملیات‌های درخت قرمز-سیاه پرداختیم. برای آشنایی بیشتر با این نوع درخت، پیشنهاد می‌کنیم به صفحه مربوط به آن مراجعه کنید.

مطالب مرتبط

همه مقالات

الگوریتم ساده با جواب، نمونه و مثال الگوریتم ساده

آموزش کامل مرتب سازی درجی

آی تی یا برنامه نویسی

درخت AVL