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

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

دانشجویان و کاربران گرامی سایت یوفایل : فایلی که اکنون معرف حضور شماست فایل پاورپوینت درس ساختمان داده ها مبحث درخت ها می باشد. این فایل شامل 118 اسلاید بسیار سودمند و با ارزش با کیفیت بسیار عالی و در قالب فرم 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 گره :

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