ساختمان داده ها و الگوريتم ها (Red-Black Trees)

صفحه 1:
Ret-Olack Trees ساختمان داده ها و الگوریتم ها 

صفحه 2:
Ret-Okack Trees (ROT) © درختهاي قرمز و سياه ‎O83 Ge i (Red/Black Mreev)‏ جستجوي دودويي ‎Gul (Diy Grack Prep)‏ 48 98 28 آن علاوه بر فيلدهاي دیگر» یک بیت رنگ نیز دارد بیت رنگ دوحالته (قرمز یا سیام) است ‎٩‏ هدف از اين بیت» تضمین توازن نسبي درخت است - در درخت جستجوي دودويي» عملیات جستجو » افزودن و حذف گره هزینه اي متناسب با عمق درخت دارند. ‏- عمق درخت متوازن با () گره از مرتبه (0 ,)0 است. ‏- عمق درخت فامتوازن با () گره از مرتبه (2)60) است. 

صفحه 3:
Redback Tree(ROT) ROT = OG + color bit & ‏بقيه مشخصات همانند 8)845) است‎ © - ارث بري مه ‎whey, bef, right, 7 —‏ ۶ هر گره درخت دقیقا دو فرزند دارد ‎me‏ به جاي فرزند نداشته» ديج استفاده مي كنيم ‎٩‏ تمام برگهاي تهي ( فرزنداني که وجود ندارنده) به رنگ سیاه ‏- براي مشخص نمودن برگهاي تهي » یک گره كمکي ایب مي سازیم و از ‏آن به جاي تمام فرزندان تهي درخت استفاده مي کنیم. #مشابه گره بو در ليستهاي پيوندي 

صفحه 4:
4. هر گره درخت یا سیاه است یا قرمز 2 ريشه درخت سياه است ©. هر كره تهي(ادج) سياه است اگر گرهي قرمز باشد» هر دو فرزند آن سياه 5 ©. همه مسيرهايي كه از يى كره شروع شده وابه برك مي رسندء دقيقا داراي تعداد مساوي گره سياه هستند. 

صفحه 5:
توجه: هر گره درخت دقیقا دو فرزند دارد؛ به جاي فرزند نداشته. 12111 استفاده مي 

صفحه 6:
ROT 4 53 (jae) eli! © ارتفاع كره ‎B(x)‏ : ارتفاع یک گره برابر با طول بزرگترین مسیر گره به برگهاي درخت است, © ارتفاع سياه گره )رد : تعداد گرههاي سیاه در هر یک از مسيرهايي است که از این گره شروع مي شوند و به برگ ()ل ختم متي ‎age‏ ‏- برك ()اج جزء مسیر محسوب مي شود - خود كّره » جزء مسير محسوب نمي شود ‎٩‏ ارتفاع سیاه یک درخت /16) برابر با ارتفاع سیاه ريشه آن است 

صفحه 7:
ارتفاع :۲ © ارتفاع سیامیبا ه ۵ >( >( © طول بلندترین مسیر از یک گره به برگي از درخت» حداکثر دو برابر طول کوتاهترین مسیر از همان گره به برگهاي درخت است. 

صفحه 8:
لم0 : ارتفاع درخت ۴/) ‎2d‏ طول بزرگترین مسیر از یک گره به برگ حداکثر دو برابر طول کوتاهترین مسیر است: اثبات: ‎٩‏ تعداد گرههاي سیاه روي مسيرهاي که از گره بشروع شده و به برگي مي رسند برابر (7۷ است ( خاصیت 9) ‏اگر طول کوتاهترین مسیر را با (مم)جنشان دهیم» ‎(xe)‏ =< معط ‏© بنابر خاصیت چهارم» روي مسيرهاي مذکور گرههاي قرمز متوالي وجود ندارند و همه مسیرها هم به گره سپاه تمام مي شوند. ‏بنابراین روي بلندترین مسیر» ترتیب گرههاي قرمز و سیاه حداکثر ‏یک در میان و به تعداد مساوي است: 917 > ( ‎(ac) <= Gof) ules a © 

صفحه 9:
تعداد گرههاي 4۲۳ ۶ لم 0: تعداد گرههاي داخلي درختچه واقع در گره »« حداقل برابر است با:0-. ۶ اثبات ( با استفاده از استقرا ریاضی) - اگر ۰۳-0 آنگاه بببرگ است. و ارتفاع سیاه آن نیز صفر است. در نتيجه تعداد گرههاي درختچه برابر 00 - < 0 است - اگر 200 (! و فرض کنیم ارتفاع سیاه گره بربرابر 9 < ۲ باشد: © هر کدام از فرزندان « ارتفاعي برابر با 4 خواهند داشت. لگر فرزند درخت قرمز باشده ارتفاع سياه آن ما و در غير اين صورت را خواهد بود © بنابر فرض استقرا هر درختجه شروع شده از فرزند »د حداقل-) 1004© كره خواهد داشد و درنتیجه؛ درختچه واقع در « حدلقل ‎oS + (OHM QO‏ خواهد داشت 60-۶ 02+( -0۸-۱) 0 < تعداد گر ههاودرختچه ولقم در « 

صفحه 10:
‎٩‏ لم0: طول بزرگترین مسیر از یک گره به برگ حداکثر دو برابر طول ‎fe) <= G(s OLS‏ ‎al ©‏ 0: تعداد گرههاي داخلي درختچه واقع در گره ب« حداقل برابر است با:0-0/©. ‏* لم 9: حداکثر ارتفاع یک درخت 0369/۳ با ب گره» برابر است با: © ‎by (wtd)‏ ‏© اثبات - لم دوم: ‎w= O*-,‏ - لم اول: 0 - 46© < ‎٠‏ جه ول < بر « (مجج)ا 6 عاد 

صفحه 11:
* هانند ‎BOM‏ ۰ تمام عملیات با (جبمر) (قابل انجام هستند 9 عملیات جستجو که نیاز به تغیبر درخت ندارند ‎GTP ie lids‏ انجام مي كيرند © عمليات حذف نمودن و افزودن كره به كارهاي بيشتري براي حفظ خاصيت 8607) نیازمند هستند 

صفحه 12:


صفحه 13:


صفحه 14:


صفحه 15:


صفحه 16:


صفحه 17:
P cob] = REO tea robr{p{z]] — OL ‏(ر لبم‎ - 0 cobrlrhdall] — REO 7< Ppl] PIX-OP Color ‏ماس‎ 

صفحه 18:
[[عاماكه حدم ‎teu 2 — Az]‏ ‎LEPT-ROTOTE(T, 2)‏ ‎vvbr{pf{z]] — BLOCK‏ ‎cobrlphplell] — REO‏ ‎RIGLP-ROTOTE(T,‏ PIX-OP Color ‏ماس‎ 

صفحه 19:
0 مرب و ‎fou 2‏ )2 ۱۵۳۱۵۸۵۱۵۵ - [[تا میم 0 - [[2آامآ میم ‎RIGLP-ROTOTE(T,‏ ‎PIX-OP Color ‏ماس‎ 

صفحه 20:
[[عاماكه حدم ‎teu 2 — Az]‏ ‎LEPT-ROTOTE(T, 2)‏ ‎vvbr{pf{z]] — BLOCK‏ ‎cobrlphplell] — REO‏ ‎RIGLP-ROTOTE(T,‏ PIX-OP Color ‏ماس‎ 

صفحه 21:


صفحه 22:


صفحه 23:


صفحه 24:


صفحه 25:


صفحه 26:


صفحه 27:


صفحه 28:


صفحه 29:


صفحه 30:


صفحه 31:


صفحه 32:


صفحه 33:
* اگر رر (گره حذف شده) سیاه باشد» در حالات زیر خاصیت ‎ROT‏ ‏نقض مي شود:( د كرهي است كه قبلا فرزند رم بوده است. اكر بر فرزندي نداشته باشد» « گره اب درخت است.) - ,و ريشه درختبودم و فرزند جایگرین‌شده قرمز لستهر > ريشه جدید» قرمز شده است(نقض)) - ()م<(م قرمز است (مع)م, »« > هر دو قرمزند ( نقض 4) - هر مسيري که قبلا شامل گره رو بوده حالا یک گره سياه كمتر از بقیه دارد( نقض 9) حل: فرشم کنیم گرمبر ذاراي یکن نشنان: سیاه اضافی اسث - خاصیت ) نقض مي شود - با یک سري عملیات باسازي و تغیبر رنگ خواص مورد نظر تامین مي شوند 

صفحه 34:
‎٩‏ انتقال گره بر به سطوح بالاتر تا جايي که: ‏- »« گرهی‌قرمز و سیاه باشد > مشخصه قرمز آن‌حذفمي‌شود ‏- بسه ‎Ady‏ برسد > مشخصه سیام لضافي‌حذفمي‌شود ‏- > همچنان‌سیاه و سیاه باشد > با چرخش‌هایمناسبمکان‌آندر درخت بادلثر برود 

صفحه 35:
© گرم حذفشده و« گرهي‌لستکه قبلافرزند بر بودم لستٍ لگر مر فرزنديندلشته باشدء ,, كره إ» درختلستٍ RB-DELETE-FIXUP(T, x) while x # root[T] and color[x]= BLACK do if x = left[p[x]] then w « right[p[x]] //Four different cases else (same as then clause with "right" and "left" exchanged) color[x] « BLACK 

صفحه 36:
۱ T, x) kde x # rool? | od oobrf] = BLOCK bP x = Ap] trea W — rihdp[x]] PB ‏]مارم‎ ۷ 2 0 1 و۵ // ‎BLOCK‏ — ۷۷ ]اند مسا ‎obra] ۰ REO Howe A‏ ‎Case 1‏ // — رم ‎LEED-ROTONE (DM,‏ Ww — righty>] 2 ۶ ۵ ۵ 8ه 9 و « و 

صفحه 37:
اصلاح را نگ - ادامه ۵ ‏,)مه‎ x) (Contd.) /* xis still /eft{pLx]] */ ‏إخاط ]حا ع‎ W] = CLOCK ord cobrfrigh{ W]] = CLOCK ‏]سا ما‎ — REO 1 Cree © x= pfx] // phe P ovbrfrighf W]] = ۲ ‏إن ]خط اجا مدا‎ [ — CLOCK = //Owe 9 ‏]با‎ ۷۷ - 0 ۸9 RIGLP-ROTONE(T, w) UCrwse 9 ‏وم0// [لحاصراك يست را‎ ‏[[حآا اس إلا )جامد‎ // & pobr|pfa]] — LOOK 1 Cuse & cobr{righh W]] — BLOCK 1 Cruse & LEED-ROTONE (P, plod) 1 Orwe ©: x— rol? ] 1 Case P eb (sexe oF fea chee Wik “right” cad “EPI” exckeced) ‏جاده .هت‎ — CLOCK 

صفحه 38:
حالت اول: رر, قرمز است Ke ON ۰ B y ‏و‎ ‏فرزندان الا سياه هستند‎ © ‏رنك بمو ()م را باهم عوض كن ( دقت كنيد: ()م حتما سياه است! (جرا؟)‎ - (tLe) P(x) ‏مر مياه‎ ‏برادر جديد سياه است. زيرا يكي از فرزندان بيشين رمد است‎ - ‎٩‏ نهایتا گره « داراي دو سیاه و گره ررر داراي یک سیاه است - يكي از حالات 0 4 اتفاق مي افتد 

صفحه 39:
دوم: رم و فرزندانش سیاه هستند new x 2 ‏تك‎ ‎SS ‎a 8 < ‏کم‎ ‎۷ 8 3 * یرو فرزندانش سیاه هستند 8 - از كره »و ءى يك سياه كم كرده و به يدر اين دو يك سياه اضافه كن - حالا كره « داراي يك سياه است و يك كره عادي است - ()م دا لیب کمشخصه سیام لضاقي‌لست> اللگوریتم را از « جديد؛ ()م ادلمه سدم © اگر («)م قرمز بوده و از حالت اول به این حالت آمده ایم ‎clea | p(x) By =‏ کن > الگوریتم خاتمه پیدا مي کند 

صفحه 40:
راست سیاه هستند و فرزند چپ قرمز است سرو فرزند رلستسیاه هنند و فسرزند چپقرمز است 12 رنك رمدو فرزند جب را باهم عوض كن rich! rotte(u) — - م سياه لستو حالف رزند راستآن‌قرمز لست چند تغییر رنگي‌ساده لازم لس 

صفحه 41:
م: رمه سياه و فرزند راست آن قرمز, است 2 5 8 © حالت جهارم: رس سياه و فرزند راست آن قرمز است - ربررا مشابه (م)م رنگکن - (م)م و فرزند رلسترر, را سیام رنگکن - دام دص خاصا. - سیاه اضافي گره »« را حذف کن > پایان الگوریتم! - براي يايان الكوريتم ‎ »‏ جدید به ريشه درخت اشاره مي كند! 

صفحه 42:
9حذف گره : (۰ )6 ‎٩‏ تامین خاصیت رنگي - تنها حالت دوم ممکن است تکرار شود - در هر تکرار گره « یک سطح در درخت بالاتر مي رود - حداکثر تکرار این مرحله از الگوریتم ارتفاع درخت است O (bry 7) giles Aaja @ 

صفحه 43:
‎e‏ ۲ در خنجستجويدودويی | مشخصه لضافه "رنگ‌لست ‎٩‏ با مدیریت خواص /309)مي توان تمام عملیات درخت جستجوي دودويي را با هزینه (ه ب)) انجام داد که در آن ب تعداد گرههاي درخت است ‏عملیات حذف و اضافه کردن گره به درخت ممکن است سبب نقض خواص رنككي “09001 شوند. در اين صورت بايد درخت را ‏از نظر رنكي اصلاح كرد 

صفحه 44:
‎٩‏ الگوريتمي بنویسید که یک درخت جستجوي دوديي رنگ شده را بكيرد و تعيين كند آيا اين درخت یک درخت سياه و قرمز است یا نهر ‏© آيا مي توانيد الگوريتمي در حالت كلي ارائه دهید که هر درخت دلخواهي را به درخت ۲69 تبدیل کند ؟مرتبه اجرايي الگوریتم ‏شما چیست ؟