خرید ودانلود پاورپوینت تحقیق جستجوی دودویی

الگوریتم جستجوی دودویی (به انگلیسی: Binary Search)، تکنیکی است برای یافتن یک مقدار عددی از میان مجموعهای از اعداد مرتب. این متد محدودهٔ جستجو را در هر مرحله به نصف کاهش میدهد، بنابراین هدف مورد نظر یا به زودی پیدا میشود و یا مشخص میشود که مقدار مورد جستجو در فهرست وجود ندارد.

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

جستجوی دودویی نمونهای از الگوریتمهای تقسیم و غلبه (به انگلیسی: Divide and conquer) میباشد.

n تعداد گره ها در یک درخت دودویی کامل است و با استفاده از این فرمول می توان آنرا یافت n = 2^{h+1}-1 (در آن h عمق درخت است) N تعداد گره ها در یک درخت دودویی کامل است حداقل برابر n = 2^{h} و حداکثر برابرn = 2^{h+1}-1 ( h عمق درخت است) L تعدادی از گره های برگ در درخت دودویی کامل است و با استفاده از فرمول L = 2^h محاسبه می گردد.

N تعداد گره ها در یک درخت دودویی کامل نیز می تواند با استفاده فرمول n = 2L-1 محاسبه می شود.(L، تعدادی از گره های برگ در درخت است.)

تعدادی از لینک های تهی (فرزندان غایب از گره ها) در یک درخت دودویی کامل از n گره(n+1) تعداد n-L از گره های داخلی در یک درخت دودویی کامل از n گره (گره های غیر برگ) lfloor n/2 rfloor. برای هر درخت غیر تهی با گره های برگ n_0 و n_2 گره ها از درجه ۲ n_0 = n_2 + 1.

اثبات:

N = تعداد کل گره B = تعداد شاخه ها

n0, n1, n2 برای نشان دادن تعداد گره بدون فرزند، تنها یک فرزند و دو فرزند بود

B = n – 1 (از آنجا که تمام گره ها به جز گره ریشه از شاخه واحد)

B = n1 + 2*n2

n = n1+ 2*n2 + 1

n = n0 + n1 + n2

n1+ 2*n2 + 1 = n0 + n1 + n2 ==> n0 = n2 + 1