دانلود پاورپوینت با موضوع ساختمان داده ها درختان جستجوی دودویی،
در قالب ppt و در 34 اسلاید، قابل ویرایش.
بخشی از متن پاورپوینت:
درخت جستجوي دودويي:
صفر نود يا بيشتر
اگر >0 نود:
هر نود داراي يک کليد يکتا است.
کليد تمام نودهاي زير درخت سمت چپ نود، ازخود نود کمتر است.
کليد تمام نودهاي زير درخت سمت راست نود، ازخود نود بيشتر است.
زير درختهاي سمت چپ و راست نيز درخت جستجوي دودويي هستند.
درخت جستجوی دودویی
درخت جستجوی دودویی
درخت جستجوی دودویی
دقت کنيد که شرط کامل بودن در تعريف درخت جستجوي دودويي حضور ندارد.
لذا، پياده سازي لينک پيوندي بهتر است.
تعريف بازگشتي درخت جستجوي دودويي = الگوريتمهاي بازگشتي
درخت جستجوی دودویی:جستجو
جستجو:
از خواص درخت جستجوي دودويي استفاده کنيد.
از ريشه شروع کن
اگر ريشه برابر صفر بود، پيغام بده که درخت خالي است.
در غير اين صورت:
x را با ريشه مقايسه کن.
اگر x با کليد ريشه برابر بود، نود را برگردان.
اگر x از کليد ريشه کمتر بود، زير درخت سمت چپ را بگرد.
در غير اين صورت زير درخت سمت راست را بگرد.
درخت جستجوی دودویی: مثالی از جستجو
آنالیز درخت جستجوی دودویی
در ريشه يک مقايسه انجام مي دهيم
> Root يا < Root
با توجه به نتيجه:
به يکي از فرزندان مي رويم
يک مقايسه انجام مي دهيم.
حداکثر به اندازه ارتفاع درخت اين کار را انجام مي دهيم:
لذا، پيچيدگي زماني جستجو، وابسته به شکل درخت است.
خطی: O(n)
متوازن: O (log 2 n)
درج در درخت جستجوی دودویی
قوانين – الحاق بايد شرايط زير را برآورده کند:
کليد يکتا
فرزند سمت راست < پدر
فرزند سمت چپ > پدر
نودهاي مياني نيز بايد شرايط فوق را برآورده کنند.
يکتا بودن را چگونه چک کنيم؟
به همه نودها نگاه کنيم؟
درج در درخت جستجوی دودویی
نيازي نيست که به تمام نودها نگاه کنيم
از اين حقيقت استفاده مي کنيم که قبل از الحاق نود جديد، درخت از نوع جستجوي دودويي است.
لذا کافيست دنبال نود جديد در درخت بگرديم.
درج در درخت جستجوی دودویی
جستجوي نود جديد نه تنها مساله يکتا بودن را حل مي کند، بلکه ما را به جاي درست نود جديد رهنمون مي سازد.
آنالیز عمل درج
عمده کار تابع الحاق، پياده سازي عمل جستجو است.
وابسته به شکل درخت است.
خود عمل الحاق داراي هزينه ثابت است.
لذا، هزينه کل وابسته به پيچيدگي عمل جستجو است.
در بدترين حالت: O(n)
در حالت ميانگين: O(log2n)
درخت جستجوي دودويي:
صفر نود يا بيشتر
اگر >0 نود:
هر نود داراي يک کليد يکتا است.
کليد تمام نودهاي زير درخت سمت چپ نود، ازخود نود کمتر است.
کليد تمام نودهاي زير درخت سمت راست نود، ازخود نود بيشتر است.
زير درختهاي سمت چپ و راست نيز درخت جستجوي دودويي هستند.
درخت جستجوی دودویی
درخت جستجوی دودویی
درخت جستجوی دودویی
دقت کنيد که شرط کامل بودن در تعريف درخت جستجوي دودويي حضور ندارد.
لذا، پياده سازي لينک پيوندي بهتر است.
تعريف بازگشتي درخت جستجوي دودويي = الگوريتمهاي بازگشتي
درخت جستجوی دودویی:جستجو
جستجو:
از خواص درخت جستجوي دودويي استفاده کنيد.
از ريشه شروع کن
اگر ريشه برابر صفر بود، پيغام بده که درخت خالي است.
در غير اين صورت:
x را با ريشه مقايسه کن.
اگر x با کليد ريشه برابر بود، نود را برگردان.
اگر x از کليد ريشه کمتر بود، زير درخت سمت چپ را بگرد.
در غير اين صورت زير درخت سمت راست را بگرد.
درخت جستجوی دودویی: مثالی از جستجو
آنالیز درخت جستجوی دودویی
در ريشه يک مقايسه انجام مي دهيم
> Root يا < Root
با توجه به نتيجه:
به يکي از فرزندان مي رويم
يک مقايسه انجام مي دهيم.
حداکثر به اندازه ارتفاع درخت اين کار را انجام مي دهيم:
لذا، پيچيدگي زماني جستجو، وابسته به شکل درخت است.
خطی: O(n)
متوازن: O (log 2 n)
درج در درخت جستجوی دودویی
قوانين – الحاق بايد شرايط زير را برآورده کند:
کليد يکتا
فرزند سمت راست < پدر
فرزند سمت چپ > پدر
نودهاي مياني نيز بايد شرايط فوق را برآورده کنند.
يکتا بودن را چگونه چک کنيم؟
به همه نودها نگاه کنيم؟
درج در درخت جستجوی دودویی
نيازي نيست که به تمام نودها نگاه کنيم
از اين حقيقت استفاده مي کنيم که قبل از الحاق نود جديد، درخت از نوع جستجوي دودويي است.
لذا کافيست دنبال نود جديد در درخت بگرديم.
درج در درخت جستجوی دودویی
جستجوي نود جديد نه تنها مساله يکتا بودن را حل مي کند، بلکه ما را به جاي درست نود جديد رهنمون مي سازد.
آنالیز عمل درج
عمده کار تابع الحاق، پياده سازي عمل جستجو است.
وابسته به شکل درخت است.
خود عمل الحاق داراي هزينه ثابت است.
لذا، هزينه کل وابسته به پيچيدگي عمل جستجو است.
در بدترين حالت: O(n)
در حالت ميانگين: O(log2n)
