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

فهرست عناوین اصلی در این پاورپوینت

فهرست عناوین اصلی در این پاورپوینت

● ساختمان داده ها

درختان جستجوی دودویی
● درخت جستجوی دودویی
● درخت جستجوی دودویی:جستجو
● درخت جستجوی دودویی: مثالی از جستجو
● آنالیز درخت جستجوی دودویی
● درج در درخت جستجوی دودویی
● آنالیز عمل درج
● ارتفاع درخت جستجوی دودویی
● Binary Search Trees: Height
● TreeSort:
● Binary Search Trees: Deletion
● حالت سوم حذف
● ادامه ی حالت سوم حذف
● مراحل حذف:
● مراحل حذف
● کد حذف
● ادامه ی کد حذف

عبارات مهم استفاده شده در این مطلب

عبارات مهم استفاده شده در این مطلب

درخت جستجوی, درخت جستجوی دودویی, جستجوی دودویی, سمت چپ, سمت راست, نودهای سمت, ارتفاع درخت, بدترین حالت, درخت سمت, درج درخت جستجوی, درج درخت, فرزند سمت, نود انتهایی, درج درخت جستجوی دودویی, نودهای درخت,

نوع زبان: فارسی حجم: 0.35 مگا بایت
نوع فایل: اسلاید پاورپوینت تعداد اسلایدها: 34 صفحه
سطح مطلب: نامشخص پسوند فایل: ppt
گروه موضوعی:  زمان استخراج مطلب: 2019/06/07 11:19:47

لینک دانلود رایگان لینک دانلود کمکی

اسلایدهای پاورپوینت مرتبط در پایین صفحه

توجه: این مطلب در تاریخ 2019/06/07 11:19:47 به صورت خودکار از فضای وب آشکار توسط موتور جستجوی پاورپوینت جمع آوری شده است و در صورت اعلام عدم رضایت تهیه کننده ی آن، طبق قوانین سایت از روی وب گاه حذف خواهد شد. این مطلب از وب سایت زیر استخراج شده است و مسئولیت انتشار آن با منبع اصلی است.

http://dir.ilam.ac.ir/mozafar/ds/f18/Lec16-ds.ppt

در صورتی که محتوای فایل ارائه شده با عنوان مطلب سازگار نبود یا مطلب مذکور خلاف قوانین کشور بود لطفا در بخش دیدگاه (در پایین صفحه) به ما اطلاع دهید تا بعد از بررسی در کوتاه ترین زمان نسبت به حدف با اصلاح آن اقدام نماییم. جهت جستجوی پاورپوینت های بیشتر بر روی اینجا کلیک کنید.

عبارات پرتکرار و مهم در این اسلاید عبارتند از: درخت جستجوی, درخت جستجوی دودویی, جستجوی دودویی, سمت چپ, سمت راست, نودهای سمت, ارتفاع درخت, بدترین حالت, درخت سمت, درج درخت جستجوی, درج درخت, فرزند سمت, نود انتهایی, درج درخت جستجوی دودویی, نودهای درخت,

مشاهده محتوای متنیِ این اسلاید ppt

مشاهده محتوای متنیِ این اسلاید ppt

ساختمان داده ها درختان جستجوی دودویی give qualifications of instructors dap teaching computer architecture at berkeley since ۱۹۷۷ co athor of textbook used in class best known for being one of pioneers of risc currently author of article on future of microprocessors in sciam sept ۱۹۹۵ ry took ۱۵۲ as student taed ۱۵۲ instructor in ۱۵۲ undergrad and grad work at berkeley joined nextgen to design fact ۸ x۸۶ microprocessors one of architects of ultrasparc fastest sparc mper shipping this fall درخت جستجوی دودویی درخت جستجوی دودویی درخت دودویی صفر نود یا بیشتر اگر نود هر نود دارای یک کلید یکتا است. کلید تمام نودهای زیر درخت سمت چپ نود، ازخود نود کمتر است. کلید تمام نودهای زیر درخت سمت راست نود، ازخود نود بیشتر است. زیر درختهای سمت چپ و راست نیز درخت جستجوی دودویی هستند. درخت جستجوی دودویی ۳ ۵ ۲ ۴ کلیدهای یکتا نودهای سمت چپ کمتر از ریشه نودهای سمت راست بیشتر از ریشه زیر درختهای سمت چپ و راست نیز درخت جستجوی دودویی هستند. ۶ ۸ ۶۵ ۷ کلیدهای یکتا نودهای سمت چپ کمتر از ریشه نودهای سمت راست بیشتر از ریشه زیر درختهای سمت چپ و راست نیز درخت جستجوی دودویی هستند. درخت جستجوی دودویی ۲ ۱۵ ۱۲ ۲۵ ۱۸ ۲۲ درخت جستجوی دودویی نیست. فرزند سمت راست ۲۵ ازخودش کمتر است. کلیدهای یکتا نودهای سمت چپ کمتر از ریشه نودهای سمت راست بیشتر از ریشه زیر درختهای سمت چپ و راست درخت جستجوی دودویی نیستند. درخت جستجوی دودویی دقت کنید که شرط کامل بودن در تعریف درخت جستجوی دودویی حضور ندارد. لذا، پیاده سازی لینک پیوندی بهتر است. تعریف بازگشتی درخت جستجوی دودویی الگوریتمهای بازگشتی درخت جستجوی دودویی جستجو جستجو از خواص درخت جستجوی دودویی استفاده کنید. از ریشه شروع کن اگر ریشه برابر صفر بود، پیغام بده که درخت خالی است. در غیر این صورت x را با ریشه مقایسه کن. اگر x با کلید ریشه برابر بود، نود را برگردان. اگر x از کلید ریشه کمتر بود، زیر درخت سمت چپ را بگرد. در غیر این صورت زیر درخت سمت راست را بگرد. درخت جستجوی دودویی مثالی از جستجو ۳ ۵ ۲ ۴ ۱۵ ۱۵ را پیدا کن. ریشه خالی است نه ۱۵ را با مقدار ریشه ۳ مقایسه کن ۱۵ ۳ لذا زیر درخت سمت چپ را بگرد. ۱۵ را با ۵ مقایسه کن ۱۵ ۵ لذا زیر درخت سمت راست را بگرد. ۱۵ را با ۱۵ مقایسه کن ۱۵ ۱۵ نود جاری را بر گردان آنالیز درخت جستجوی دودویی در ریشه یک مقایسه انجام می دهیم root یا root با توجه به نتیجه به یکی از فرزندان می رویم یک مقایسه انجام می دهیم. حداکثر به اندازه ارتفاع درخت این کار را انجام می دهیم لذا، پیچیدگی زمانی جستجو، وابسته به شکل درخت است. خطی o n متوازن o log ۲ n درج در درخت جستجوی دودویی قوانین الحاق باید شرایط زیر را برآورده کند کلید یکتا فرزند سمت راست پدر فرزند سمت چپ پدر نودهای میانی نیز باید شرایط فوق را برآورده کنند. یکتا بودن را چگونه چک کنیم به همه نودها نگاه کنیم درج در درخت جستجوی دودویی نیازی نیست که به تمام نودها نگاه کنیم از این حقیقت استفاده می کنیم که قبل از الحاق نود جدید، درخت از نوع جستجوی دودویی است. لذا کافیست دنبال نود جدید در درخت بگردیم. ۳ ۵ ۲ ۴ ۱۵ add ۱۵ search for ۱۵ ۱۵ ۳ ۱۵ ۳ left ۱۵ ۵ ۱۵ ۵ right ۱۵ ۱۵ ۱۵ ۱۵ not unique درج در درخت جستجوی دودویی جستجوی نود جدید نه تنها مساله یکتا بودن را حل می کند، بلکه ما را به جای درست نود جدید رهنمون می سازد. ۳ ۵ ۲ ۴ add ۱۵ search for ۱۵ ۱۵ ۳ ۱۵ ۳ left ۱۵ ۵ ۱۵ ۵ right no right child so not present add ۱۵ as right child of ۵ ۱۵ آنالیز عمل درج عمده کار تابع الحاق، پیاده سازی عمل جستجو است. وابسته به شکل درخت است. خود عمل الحاق دارای هزینه ثابت است. لذا، هزینه کل وابسته به پیچیدگی عمل جستجو است. در بدترین حالت o n در حالت میانگین o log۲n ارتفاع درخت جستجوی دودویی در بدترین حالت ارتفاع درخت باینری برابر n است. درخت خطی ۳ ۵ ۲ ۴ مسائل درخت جستجوی دودویی از لحاظ پیچیدگی وابسته به ارتفاع درخت هستند که در بدترین حالت o n هست. اگر داده ها مرتب یا نیمه مرتب باشند، درخت خطی خواهد گردید. ارتفاع درخت جستجوی دودویی insert ۳ ۴ ۶ ۵ ۸ ۳ root ۴ ۶ ۵ ۸ binary search trees height اگر الحاقها به صورت تصادفی انجام گردند، ارتفاع درخت برابر o log n خواهد بود. در حالت عمومی الحاقها تصادفی هستند، لذا اغلب ارتفاع برابر o log n خواهد شد. راههای وجود دارد که ارتفاعo log n را گارانتی نمود. باید توابع الحاق و حذف را دستکاری نمود تا درخت متعادل شود. treesort نودهای درخت جستجوی دودویی دارای نظم خاصی هستند. تمام نودهای سمت چپ از ریشه کوچکتر و تمام نودهای سمت راست از آن بزرگتر هستند. این مطلب برای تمام نودها صادق است. لذا، می توان از پیمایش lvr برای تولید یک لیست مرتب استفاده کرد. ۳ ۵ ۲ ۴ ۱۵ ۳۵ ۵ lvr ordering ۲ ۵ ۱۵ ۳ ۳۵ ۴ ۵ treesort آنالیز treesort باید یک درخت جستجوی دودویی با سایز n بسازیم. به n الحاق نیاز داریم. بهترین حالت درخت متعادل o n log ۲ n بدترین حالت درخت خطی o n۲ سپس lvr را اجرا می کنیم. همیشهo n است. پس پیچیدگی treesort برابر است با بهترین حالت o n log ۲ n بدترین حالت o n۲ binary search trees deletion قوانین حذف باید شرایط زیر را برآورده کند کلید یکتا نیازی به چک کردن ندارد. چون قبل از عمل حذف کلیدها یکتا هستند. اما موارد زیر باید رعایت شوند فرزند سمت راست پدر فرزند سمت چپ پدر نودهای میانی نیز باید شرایط فوق را برآورده کنند. binary search trees deletion ۳ ۵ ۲ ۴ ۱۵ سه حالت ۱ حذف نود انتهایی ۱۵ نود انتهایی را حذف کن. اشاره گر پدر را برابر صفر قرار بده. ۳ ۵ ۲ ۴ binary search trees deletion ۲ نود غیر انتهایی، دارای یک فرزند ۵ لینک نود پدر را که به نود حذف شونده اشاره دارد را به فرزند نود حذف شونده اشاره دهید. ۳ ۵ ۲ ۴ ۳ ۵ ۲ ۴ binary search trees deletion ۳ ۵ ۲ ۴ ۳ نود غیر انتهایی دارای دو فرزند مقدار نود حذف شونده را با بزرگترین المان سمت چپ یا کوچکترین المان سمت راست جابجا کنید. نودی را که جابجا کرده …

کلمات کلیدی پرکاربرد در این اسلاید پاورپوینت: درخت جستجوی, درخت جستجوی دودویی, جستجوی دودویی, سمت چپ, سمت راست, نودهای سمت, ارتفاع درخت, بدترین حالت, درخت سمت, درج درخت جستجوی, درج درخت, فرزند سمت, نود انتهایی, درج درخت جستجوی دودویی, نودهای درخت,

این فایل پاورپوینت شامل 34  اسلاید و به زبان فارسی و حجم آن 0.35 مگا بایت است. نوع قالب فایل ppt بوده که با این لینک قابل دانلود است. این مطلب برگرفته از سایت زیر است و مسئولیت انتشار آن با منبع اصلی می باشد که در تاریخ 2019/06/07 11:19:47 استخراج شده است.

http://dir.ilam.ac.ir/mozafar/ds/f18/Lec16-ds.ppt

  • جهت آموزش های پاورپوینت بر روی اینجا کلیک کنید.
  • جهت دانلود رایگان قالب های حرفه ای پاورپوینت بر روی اینجا کلیک کنید.

رفتن به مشاهده اسلاید در بالای صفحه


پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *