درخت ای قرمز سیاه

[meisam12]

لطفا در باره درج در درخت های قرمز سیاه توضیح دهید

[meisam12]

کسی از دوستان نظری ندارد؟

[FastCode]

مقاله ی ویکیپدیا رو خوندید؟
اگر خوندید و چیزی دستگیرتون نشده پیشنهاد میکنم RBTree.cs از source code ه mono رو بخونید, C#‎ ه
https://github.com/mosa/Mono-Class-Libraries/blob/master/mcs/class/System/System.Collections.Generic/RBTree.cs

[aliabbasidehmiani]

لطفا در باره درج در درخت های قرمز سیاه توضیح دهید

درج در درخت قرمز و سیاه
هنگام اضافه کردن در درخت قرمز-سیاه 5 حالت وجود دارد


گره جدید N ریشهٔ درخت باشد . در این حالت با تغییر رنگ به سیاه( بخاطر ویژگی ریشه باید سیاه باشد)و در هرمسیر باید یگ گره سیاه وجود داشته باشد اعتبار درخت را حفظ می‌کند .
اگر گره والد سیاه باشد هیج کدام از دو ویژگی (هردو فرزند قرمز، سیاه هستند و تعداد راه‌های از هر مسیر به برگ دارای تعداد یکسان گره سیاه دارند( مورد تهدید واقع نمی‌شوند ولی فقط وجود دوگره قرمز اعتبار درخت را زیر سوال می‌برد
گر هردو گره والد و عمو قرمز باشد، هردو به رنگ سیاه در می‌آیند و پدر آنها قرمز در می‌آید.(برابر ویژگی ۴). گره قرمز جدید دارای والد سیاه است . تا آن زمان که هر راه از والد /عمو که به طور قطع از پدر بزرگ نیز عبور می‌کند همچنان معتبر می‌باشد . با این وجود G(پدر والد و عمو و پدربزرگ N) باید بررسی شود که آیا ریشه‌است یا خیر(تا به رنگ سیاه درآید( ویژگی ۲) این کار را می‌توان با یک متد بازگشتی انجام داد . حتی می‌توان آن را به صورت یک حلقه نوشت که البته ثابت می‌شود این حلقه دارای تعداد مشخصی انجام عملیات چرخش است.





گر والد (p) قرمز باشد ولی عمو سیاه باشد همچنان گره جدید سمت راست p است و p فرزند سمت چپ G است . در این حالت، یک دوران به چپ که نقش گره جدید N را با والدش ؛ P تغییر می‌دهد، قابلیت اجرا پیدا می‌کند که در آن والد قبلی با فرزندش جابجا می‌شود سپس والد قبلی که اکنون دوباره برچسب گذاری شده با ویژگی همه مسیرها دارای تعدا مساوی گره سیاه هستند؛ سر و کار دارد . چون بر طبق ویژگی 4 (هر دو فرزند گره قرمز سیاه هستند) همچنان مورد تهدید بی اعتبارشدن درخت همراه است . دوران باعث می‌گردد تا در بعضی از مسیرها (از جمله مسیری که از زیر درخت برچسب گذاری شدهٔ 1)عبور می نماید از گره جدیدی که قبلاً مطرح نبوده است، عبور می‌کند ولی چون این گره مانند گره قبلی قرمز است، ویژگی 4 با دوران اعتبار درخت را از بین نمی‌برد .

به همین ترتیب اگر والد (p) قرمز باشد ولی عمو سیاه باشد همچنان گره جدید سمت چپ p است و p فرزند سمت راست G است . در این حالت، یک دوران به راست روی والد(p) انجام می شود.



والد قرمز است ولی عمو سیاه می‌باشد و گره جدید N فرزند چپ والد P است و P فرزند چپ پدربزرگ(G)است . در این حالت رو ی پدر بزرگ(g) دوران به راست اجرا می‌گردد .درختی که نتیجه می‌شود دارای والد ی به نام P برای هردو گره G و N است .G، به عنوان ریشه، سیاه است و این تا آن زمان که فرزندش قرمز باشد پابرجاست .با تغییر رینگ P و G درخت نهایی حاصل می‌گردد که همه ی ویژگی‌های فوق از جمله تعداد مساوی گره سیاه در هر مسیر ( به این شکل که تمامی مسیر هایی که از این سه گره عبور می‌کند که قبلاً از G عبور می‌کرده و اکنون از P عبور می‌کند ) پابرجاست .

به همین ترتیب اگر والد قرمز است ولی عمو سیاه می‌باشد و گره جدید N فرزند راست والد P است و P فرزند راست پدربزرگ(G)است . در این حالت رو ی پدر بزرگ(g) دوران به چپ اجرا می‌گردد .