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

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

اسلاید 1: Red-Black Treesساختمان داده ها و الگوريتم ها

اسلاید 2: Red-Black Trees (RBT)درختهاي قرمز و سياه (Red/Black Trees) نوعي درخت جستجوي دودويي (Binary Search Tree) است که هر گره آن علاوه بر فيلدهاي ديگر، يک بيت رنگ نيز داردبيت رنگ دوحالته (قرمز يا سياه) استهدف از اين بيت، تضمين توازن نسبي درخت استدر درخت جستجوي دودويي، عمليات جستجو ، افزودن و حذف گره هزينه اي متناسب با عمق درخت دارند. عمق درخت متوازن با N گره از مرتبه O(log N) است.عمق درخت نامتوازن با N ‌ گره از مرتبه O(N) ‌است.

اسلاید 3: Red-black Tree(RBT)RBT = BST + 1 color bitبقيه مشخصات همانند BST استارث بري Inheritancekey, left, right, p.هر گره درخت دقيقا دو فرزند دارد به جاي فرزند نداشته، null استفاده مي کنيمتمام برگهاي تهي ( فرزنداني که وجود ندارند،) به رنگ سياه هستندبراي مشخص نمودن برگهاي تهي ، يک گره کمکي nil مي سازيم و از آن به جاي تمام فرزندان تهي درخت استفاده مي کنيم.مشابه گره first ‌ در ليستهاي پيوندي

اسلاید 4: Red-black Propertiesهر گره درخت يا سياه است يا قرمزريشه درخت سياه استهر گره تهي(null) سياه استاگر گرهي قرمز باشد، هر دو فرزند آن سياه هستندهمه مسيرهايي که از يک گره شروع شده و به برگ مي رسند، دقيقا داراي تعداد مساوي گره سياه هستند.

اسلاید 5: مثال RBT26173047385041null[T]توجه: هر گره درخت دقيقا دو فرزند دارد؛ به جاي فرزند نداشته، null استفاده مي کنيم

اسلاید 6: ارتفاع (عمق) درخت RBTارتفاع گره h(x) : ارتفاع يک گره برابر با طول بزرگترين مسير گره به برگهاي درخت است.ارتفاع سياه گره x bh(x) : تعداد گرههاي سياه در هر يک از مسيرهايي است که از اين گره شروع مي شوند و به برگ null(T) ختم مي شوندبرگ null(T) جزء مسير محسوب مي شودخود گره x جزء مسير محسوب نمي شودارتفاع سياه يک درخت RBT برابر با ارتفاع سياه ريشه آن است

اسلاید 7: Height of a RBT26173047385041null[T]h=4bh=2h=3bh=2h=2bh=1h=2bh=1h=1bh=1h=1bh=1h=1bh=1h: ارتفاعbh:ارتفاع سياهbh(x) ≤ h(x) ≤ 2 bh(x)طول بلندترين مسير از يک گره به برگي از درخت، حداکثر دو برابر طول کوتاهترين مسير از همان گره به برگهاي درخت است.

اسلاید 8: لم1 : ارتفاع درخت RBTلم1: طول بزرگترين مسير از يک گره به برگ حداکثر دو برابر طول کوتاهترين مسير است:اثبات:تعداد گرههاي‌ سياه روي مسيرهاي که از گره x‌شروع شده و به برگي مي رسند برابر bh(x) است ( خاصيت 5)اگر طول کوتاهترين مسير را با s(x)‌نشان دهيم، bh(x) <= s(x)بنابر خاصيت چهارم، روي مسيرهاي مذکور گرههاي قرمز متوالي وجود ندارند و همه مسيرها هم به گره سياه تمام مي شوند. بنابراين روي بلندترين مسير، ترتيب گرههاي قرمز و سياه حداکثر يک در ميان و به تعداد مساوي است: h(x) <= 2bh(x)درنهايت h(x) <= 2s(x)

اسلاید 9: تعداد گرههاي RBTلم 2: تعداد گرههاي داخلي درختچه واقع در گره x ‌حداقل برابر است با:2bh(x)–1.اثبات ( با استفاده از استقرا رياضي)اگر h(x)=0 ‌، آنگاه x‌برگ است.‌ و ارتفاع سياه آن نيز صفر است. در نتيجه تعداد گرههاي درختچه برابر 20 -1 = 0 استاگر h(x) =h>0 ‌ و فرض کنيم ارتفاع سياه گره x‌برابر bh(x) = b باشد:هر کدام از فرزندان x ارتفاعي برابر با h-1 خواهند داشت. اگر فرزند درخت قرمز باشد، ارتفاع سياه آن b و در غير اين صورت b-1 ‌خواهد بودبنابر فرض استقرا هر درختچه شروع شده از فرزند x حداقل-1 2bh(x) -1 گره خواهد داشد و درنتيجه، درختچه واقع در x حداقل 2(2bh(x)-1 -1 ) + 1‌گره خواهد داشت 2 (2bh(x) – 1 – 1)+1= 2bh(x) – 1 تعداد گرههاي درختچه واقع در x

اسلاید 10: حد ارتفاع RBTلم1: طول بزرگترين مسير از يک گره به برگ حداکثر دو برابر طول کوتاهترين مسير است h(x) <= 2bh(x)لم 2: تعداد گرههاي داخلي درختچه واقع در گره x ‌حداقل برابر است با:2bh(x)–1.لم 3: حداکثر ارتفاع يک درخت RBT با n گره، برابر است با: 2 log (n+1)اثباتلم دوم: , n  2bh – 1 لم اول: bh h/2  n  2h/2 – 1  h  2 lg(n + 1).

اسلاید 11: عمليات روي RBTهمانند BST ، تمام عمليات با O (log n)‌قابل انجام هستندعمليات جستجو که نياز به تغيير درخت ندارند دقيقا مثل BST انجام مي گيرندعمليات حذف نمودن و افزودن گره به کارهاي بيشتري براي حفظ خاصيت RBT نيازمند هستند

اسلاید 12: Left RotationABαβγ…P(x)AαBβγ…P(x)

اسلاید 13: Left RotationABαβγ…P(x)AαBβγ…P(x)

اسلاید 14: Left RotationABαβγγBy…… Left Rotation Right Rotation αβAx

اسلاید 15: Left Rotation Example

اسلاید 16: Insert a node211141715584Insert (4)Tree color violation

اسلاید 17: Insert a node211141715584FIX-UP Color violationzy=right(p(p(z))if color[y] = RED then color[p[z]] ← BLACKcolor[y] ← BLACKcolor[p[p[z]]] ← RED z ← p[p[z]]

اسلاید 18: Insert a node11141521FIX-UP Color violation5784zif z = right[p[z]] then z ← p[z]LEFT-ROTATE(T, z) color[p[z]] ← BLACKcolor[p[p[z]]] ← REDRIGHT-ROTATE(T, p[p[z]])

اسلاید 19: Insert a node11141521FIX-UP Color violation5784zif z = right[p[z]] then z ← p[z]LEFT-ROTATE(T, z) color[p[z]] ← BLACKcolor[p[p[z]]] ← REDRIGHT-ROTATE(T, p[p[z]])

اسلاید 20: Insert a node11141521FIX-UP Color violation5784zif z = right[p[z]] then z ← p[z]LEFT-ROTATE(T, z) color[p[z]] ← BLACKcolor[p[p[z]]] ← REDRIGHT-ROTATE(T, p[p[z]])

اسلاید 21: Delete a node21114171558Delete Node 7RB Tree Coloring violationz

اسلاید 22: Delete Node21114171558Delete Node z = 7zy = succssor(z)nilx

اسلاید 23: Delete Node21114171558zy = successor(z)nilxCopy Node 8 data to node 7

اسلاید 24: Delete Node2111418155znil8xIf color(y) = black, then fix-up color violation at x

اسلاید 25: Delete Node2111418155znilxگره x يا فرزند گره حذف شده است يا گره nil(T)

اسلاید 26: Delete Node21114171558Delete Node z = 2zy = succssor(z)nilx

اسلاید 27: Delete Node21114171558Delete Node z = 2zy = succssor(z)nilx

اسلاید 28: Delete Node5111417158Delete Node z = 2znily = succssor(z)5x

اسلاید 29: Delete Node5111417158Delete Node z = 5znilxy

اسلاید 30: Delete Node7111417158Delete Node z = 5znilxy

اسلاید 31: Delete Node7111417158Delete Node z = 5znilxy

اسلاید 32: Delete Node711141158Delete Node z = 5znilxyColor Violation

اسلاید 33: نقض شرايط RBTاگر y (گره حذف شده) سياه باشد، در حالات زير خاصيت RBT نقض مي شود:( x گرهي است که قبلا فرزند y بوده است. اگر y فرزندي نداشته باشد، x گره nil درخت است.)y ريشه درخت بوده و فرزند جایگزین شده قرمز است  x، ريشه جديد، قرمز شده است (نقض 1) p(y)=p(x) قرمز است  x ,p(x) هر دو قرمزند ( نقض 4)هر مسيري که قبلا شامل گره y بود، حالا يک گره سياه کمتر از بقيه دارد( نقض 5)حل: فرض مي کنيم گره x داراي يک نشان سياه اضافي استخاصيت 1 نقض مي شودبا يک سري عمليات باسازي و تغيير رنگ، خواص مورد نظر تامين مي شوند

اسلاید 34: اصلاح درختانتقال گره x به سطوح بالاتر تا جايي که:x گرهي قرمز و سياه باشد  مشخصه قرمز آن حذف مي شودx به ريشه برسد  مشخصه سياه اضافي حذف مي شودx همچنان سياه و سياه باشد  با چرخش هاي مناسب مکان آن در درخت بالاتر برود

اسلاید 35: Delete Nodey گره حذف شده و x گرهي است که قبلا فرزند y بوده است. اگر y فرزندي نداشته باشد، x گره nil درخت است.RB-DELETE-FIXUP(T, x)while x ≠ root[T] and color[x]= BLACKdo if x = left[p[x]]then w ← right[p[x]]//Four different caseselse (same as then clause with right and left exchanged)color[x] ← BLACK

اسلاید 36: اصلاح رنگ درخت بعد از حذف يک گرهRB-Delete-Fixup(T, x)while x  root[T ] and color[x] = BLACK do if x = left[p[x]] then w  right[p[x]] if color[w] = RED then color[w]  BLACK // Case 1 color[p[x]]  RED // Case 1 LEFT-ROTATE(T, p[x]) // Case 1 w  right[p[x]] // Case 1

اسلاید 37: RB-Delete-Fixup(T, x) (Contd.) /* x is still left[p[x]] */ if color[left[w]] = BLACK and color[right[w]] = BLACK then color[w]  RED // Case 2 x  p[x] // Case 2 else if color[right[w]] = BLACK then color[left[w]]  BLACK // Case 3 color[w]  RED // Case 3 RIGHT-ROTATE(T,w) // Case 3 w  right[p[x]] // Case 3 color[w]  color[p[x]] // Case 4 color[p[x]]  BLACK // Case 4 color[right[w]]  BLACK // Case 4 LEFT-ROTATE(T, p[x]) // Case 4 x  root[T ] // Case 4 else (same as then clause with “right” and “left” exchanged)color[x]  BLACKاصلاح رنگ - ادامه

اسلاید 38: حالت اول: w قرمز استفرزندان w سياه هستندرنگ w‌ ‌و p(x) را باهم عوض کن ( دقت کنيد: p(x) حتما سياه است! (چرا؟)) left rotate(T , p(x))برادر جديد x سياه است. زيرا يکي از فرزندان پيشين w استنهايتا گره x‌ داراي دو سياه و گره w داراي يک سياه استيکي از حالات 2- 4 اتفاق مي افتدBADCEBAxwDCExnew wp[x]

اسلاید 39: حالت دوم: w و فرزندانش سياه هستند w و فرزندانش سياه هستند از گره x و w يک سياه کم کرده و به پدر اين دو يک سياه اضافه کنحالا گره x‌ داراي يک سياه است و يک گره عادي استp(x) داراي يک مشخصه سياه اضافي است  الگوريتم را از x جديد، p(x) ادامه بده اگر p(x) قرمز بوده و از حالت اول به اين حالت آمده ايم رنگ p(x) را سياه کن  الگوريتم خاتمه پيدا مي کندBADCExwBADCEnew xccp[x]

اسلاید 40: حالت سوم: w و فرزند راست سياه هستند و فرزند چپ قرمز استw و فرزند راست سياه هستند و فرزند چپ قرمز استرنگ w‌ و فرزند چپ را باهم عوض کنright rotate(w)w سياه است و حالا فرزند راست آن قرمز است  چند تغيير رنگي ساده لازم است!BADCExwBACDccEnew wx

اسلاید 41: حالت چهارم: w سياه و فرزند راست آن قرمز استحالت چهارم: w سياه و فرزند راست آن قرمز استw را مشابه p(x) رنگ کنp(x) و فرزند راست w را سياه رنگ کنleft rotate p[x].سياه اضافي گره x را حذف کن  پايان الگوريتم! براي پايان الگوريتم ، x جديد به ريشه درخت اشاره مي کند!BADCEBAxwDCExcc’

اسلاید 42: آناليز الگوريتمحذف گره : O ( log n )تامين خاصيت رنگيتنها حالت دوم ممکن است تکرار شوددر هر تکرار گره x‌ يک سطح در درخت بالاتر مي رودحداکثر تکرار اين مرحله از الگوريتم ارتفاع درخت استهزينه نهايي O ( log n )

اسلاید 43: جمع بنديRBT درخت جستجوي دودويي با مشخصه اضافه “رنگ” استبا مديريت خواص RBT‌مي توان تمام عمليات درخت جستجوي دودويي را با هزينه O(log n) انجام داد که در آن n تعداد گرههاي درخت استعمليات حذف و اضافه کردن گره به درخت ممکن است سبب نقض خواص رنگي RBT شوند. در اين صورت بايد درخت را از نظر رنگي اصلاح کرد

اسلاید 44: تمرينالگوريتمي بنويسيد که يک درخت جستجوي دوديي رنگ شده را بگيرد و تعيين کند آيا اين درخت يک درخت سياه و قرمز است يا نه!آيا مي توانيد الگوريتمي در حالت کلي ارائه دهيد که هر درخت دلخواهي را به درخت RBT تبديل کند ؟مرتبه اجرايي الگوريتم شما چيست ؟