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

توجه : این فایل به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل ساختمان داده ها و الگوریتم ها (Red-Black Trees) 48 اسلاید در PowerPoint دارای ۴۸ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

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

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

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی پاورپوینت کامل ساختمان داده ها و الگوریتم ها (Red-Black Trees) 48 اسلاید در PowerPoint،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از مطالب داخلی اسلاید ها

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

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

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

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

اسلاید ۷: 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)طول بلندترین مسیر از یک گره به برگی از درخت، حداکثر دو برابر طول کوتاهترین مسیر از همان گره به برگهای درخت است.

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

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

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

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

اسلاید ۱۲: Left RotationAB…P(x)AB…P(x)

اسلاید ۱۳: Left RotationAB…P(x)AB…P(x)