پاورپوینت درس ساختمان داده ها مبحث درخت ها

پاورپوینت درس ساختمان داده ها مبحث درخت ها

دانشجویان و کاربران گرامی سایت یوفایل : فایلی که اکنون معرف حضور شماست فایل پاورپوینت درس ساختمان داده ها مبحث درخت ها می باشد. این فایل شامل ۱۱۸ اسلاید بسیار سودمند و با ارزش با کیفیت بسیار عالی و در قالب فرم ppt تهیه شده است که هم اکنون در سایت یوفایل آماده دانلود می باشد. امیدواریم که سودمند بوده و مورد استفاده شما سروران گرامی واقع گردد. در صورت نیاز می توانید این پاورپوینت ارزشمند را با مناسب ترین قیمت از فروشگاه سایت یو فایل خریداری و دانلود نمایید.

پاورپوینت درس ساختمان داده ها مبحث درخت ها

آشنایی با قسمتی از متن اسلایدها:

Max Heap: Insertion Big Oh Analysis

الحاق:

نقطه شروع: یکی از برگها

نقطه انتها: حداکثر ریشه، ولی معمولا قبل از ریشه متوقف می شویم

حداکثر فاصله بین ریشه و برگها برابر log2(n+1) است.

لذا، پیچیدگی زمانی الحاق O(log n) است.

ساخت یک درخت heap با n عنصر از مرتبه O(nlog n) است.

جستجو در Heap:

به ریشه نگاه می کنیم.

اگر کوچکتر بود، به فرزندان سمت راست و چپ نگاه می کنیم.

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

ممکن است که تمام گره ها را ببینیم، لذا، در بدترین حالت، جستجو O(n) خواهد بود.

Heap فقط برای مسائلی خوب است که یک عنصر مشخص (مثل بزرگترین یا کوچکترین) مورد نظر باشد.

می خواهیم راه حلی پیدا کنیم که جستجوی آن برای هر آیتم O(logn) باشد.

البته در heap می توانیم تمام عناصر را تک تک حذف کنیم تا به یک لیست مرتب نزولی برسیم.

به این روش Heapsort گفته می شود.

درخت جستجوی دودویی:

درخت دودویی

صفر گره  یا بیشتر

اگر >0 گره :

• هر گره دارای یک کلید یکتا است.
• کلید تمام گره های زیر درخت سمت چپ گره ، ازخود گره کمتر است.
• کلید تمام گره های زیر درخت سمت راست گره ، ازخود گره بیشتر است.
• زیر درخت های سمت چپ و راست نیز درخت جستجوی دودویی هستند.

مطالعه بیشتر