وب سايت دودويی

وب سايت دودويی

در این قسمت از فیلم آموزش ++C نحوه جستجو در آرایه توضیح داده شده است . یکی از بیشترین اعمالی که در کامپیوتر استفاده می شود ، عمل جستجو است ، جستجو در آرایه های نامرتب به صورت ترتیبی و در آرایه های مرتب شده از جستجوی دودویی یا باینری استفاده می کنیم .

جستجوی ترتیبی :

در این روش عنصری را که می خواهیم پیدا کنیم را با هریک از عناصر آرایه مقایسه می کنیم اگر برابر بودند جستجو تمام می شود وگرنه جستجو با عنصر بعدی انجام می شود . این روند تا انتها ادامه پیدا می کند تا به جواب برسیم و اگر به جواب نرسیدیم در خروجی پیغام ” عنصر مورد نطر پیدا نشد ” را نمایش می دهیم .

الگوریتم جستجوی دودویی ( Binary Search Algorithm ) :

جستجوی دودویی در آرایه مرتب شده انجام می شود ، پس اولین نکته این است که باید اول آرایه را مرتب کنیم و بعد جستجوی دودویی را در آن انجام دهیم . در جستجوی دودویی عنصر مورد نظر با عنصر وسط آرایه مقایسه می شود ، اگر با این عنصر برابر بود جستجو تمام می شود و گرنه اگر عنصر مورد جستجو از عنصر وسط آرایه بزرگتر یا کوچک تر بود ، آرایه به دو بخش تفسیم می شود :

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

سورس کد جستجوی دودویی در C++ :

این الگوریتم در فیلم آموزش ++C آموزش داده شده است و برای توضیحات بیش تر می توانید به آن مراجعه کنید .

جستجوی دودویی در حالت ۴ و ۵ متغیر mid

یکی از روش های جستجو در ساختمان داده جستجوی‌دودویی یا binary search می باشد؛ در این نوشته الگوریتم جستجوی‌باینری را با 4 و 5 متغیر MID برای شما حل می کنیم.

جستجوی دودویی در حالت 4 و 5 متغیر mid

جستجوی باینری با 4 متغیر MID

شکل جستجوی دودویی با 4 متغیر MID به شکل زیر می باشد:

مرتبه زمانی جستجوی دودویی با 4 متغیر MID به شکل زیر می باشد:

کد جستجوی دودویی با 4 متغیر MID به شکل زیر می باشد:

جستجوی باینری با 5 متغیر MID

شکل جستجوی دودویی با 5 متغیر MID به شکل زیر می باشد:

مرتبه زمانی جستجوی دودویی با 5 متغیر MID به شکل زیر می باشد:

کد جستجوی دودویی با 5 متغیر MID به شکل زیر می باشد:

نظرات خود را در ارتباط با این برنامه برای ما بنویسید.

ارسال پاسخ

دیدگاهتان را بنویسید لغو پاسخ

پیشنهاد می شود این نوشته ها را نیز بخوانید

دانلود یک لیست از تصاویر با کمک فایل متنی در پایتون

مشکل CORS policy با apiها در جنگو

مشکل نخواندن اطلاعات تابع file_get_contents بعد از استفاده از CDN

فریم ورک next js چیست؟

دیگر مطالب برنامه نویسی را از دست نمی دهید

با وارد کردن ایمیل خود از مقالات، آموزش ها و مطالب ما با خبر شوید. ایمیل شما برای هیچ منظور دیگری استفاده نخواهد شد زیرا ما خود از اسپم وب سايت دودويی بیزاریم.

وبسایت آموزشی camelCase، یک وبسایت آموزش برنامه نویسی به زبان فارسی می وب سايت دودويی باشد که به انتشار مقاله ی آموزشی، کتاب مرجع، آموزش ویدیویی، دوره های حضوری و وبینار آنلاین، سورس کد و حل تمرین می‌پردازد. سالهای سال است که نویسندگان این مجموعه با ارائه ی اندوخته ها و تجربیات خود در حوزه های برنامه نویسی، طراحی وب و هوش مصنوعی که دانش آموخته و فعال این حوزه هستند در کنار شما می‌باشند.

ساختمان داده درخت های دودویی

درخت یکی از ساختمان داده های مهم غیرخطی است و درخت دودویی ، مجموعه محدودی از گره هاست که، حاوی گره خاصی به نام ریشه است و بقیه گره های آن، دو زیر درخت دودویی مجزا به نام های زیردرخت چپ و زیردرخت راست را تشکیل میدهند.

ساختمان داده درخت های دودویی

درخت یکی از ساختمان داده های مهم غیرخطی است که کاربردهای فراوانی در علم کامپیوتر دارد و انواع مختلفی دارند که در اینجا درخت های دودویی را مورد بحث قرار میدهیم.

درخت از مجموعه ای عناصر به نام گره تشکیل شده است که یکی از گره ها ریشه نام دارد. برخلاف درختهای طبیعی که ریشه آنها در پایین و برگها در بالا قرار دارند، در درختهای کامپیوتری ، ریشه در بالا و برگها در پایین قرار دارند. هر گره شامل فیلدی برای داده هاست و تعدادی پیوند دارد که از طریق آنها به گره های دیگری وصل میشود. این پیوندها را انشعاب یا اتصال نیز میگویند. گره ای که هیچ انشعابی از آن خارج نشود، برگ نام دارد.

درختها بطور کلی بر دو دسته اند: درختهای عمومی و درختهای دودویی. درخت دودویی درختی است که از هر گره آن حداکثر دو پیوند خارج میشود. درختی که دودویی نباشد، درخت عمومی است.

اصطلاحات مربوط به درختها:

گره، مسیر و طول مسیر: عناصر درخت را گره گویند. هر گره دارای مسیر منحصر به فردی است که آن را به ریشه درخت وصل میکند. مسیر، دنباله ای از گره های همجوار است. طول مسیر برابر با تعداد اتصالهای همجوار است که یکی کمتراز تعداد گره های موجود در آن مسیر میباشد.

عمق گره: طول مسیر آن به گره ریشه است. عمق درخت برابر با بیشترین عمق گره های برگ آن است.

سطح گره: هر گره موجود در درخت دودویی، دارای سطح است. سطح گره ریشه، صفر در نظر گرفته میشود. سطوح بقیه گره ها یک واحد بیشتر از گره بالایی خودش است. سطح درخت، بزرگترین سطح برگهای آن وب سايت دودويی است.

ارتفاع درخت: حداکثر تعداد گره های موجود در مسیری از ریشه به یک گره برگ ارتفاع درخت نامیده میشود. در واقع، ارتفاع درخت یک واحد بیشتر از بزرگترین سطح برگهای آن است.

درخت یگانه: درختی که فقط دارای گره ریشه است، درخت یگانه نام دارد که عمق آن صفر است.

والد (پدر) گره: جد بلافصل یک گره را والد یا پدر آن گره گویند.

فرزندان گره: نسل های بلافصل یک گره را فرزندان آن گره گویند. ریشه تنها گره ای است که والد ندارد.

همزاد: گره هایی که والد انها یکسان است همزاد نامیده میشوند.

گره های برگ: گره هایی که هیچ فرزندی ندارند، برگ نامیده میشوند.

گره های داخلی: گره های غیر برگ را گره های داخلی مینامند.

اندازه درخت: تعداد گره های موجود در درخت را اندازه درخت گویند.

طول مسیر درخت: مجموع وب سايت دودويی طولهای تمام مسیرها از ریشه آن است.

درجه گره: درجه گره برابر با تعداد فرزندان آن است.

مفهوم درخت های دودویی:

درخت دودویی ، مجموعه محدودی از گره هاست که، حاوی گره خاصی به نام ریشه است و بقیه گره های آن، دو زیر درخت دودویی مجزا به نام های زیردرخت چپ و زیردرخت راست را تشکیل میدهند. در این نوع درخت هر گره حداکثر دو فرزند دارد و ترتیب فرزندان مهم است. اگر درخت دودویی در سطح i دارای m گره باشد، در سطح i+1 حداکثر دارای 2m گره است.

درخت دودویی پر:

درخت دودویی پر درختی است که تمام برگهای آن در یک سطح میباشند و هر گره داخلی نیز دارای دو فرزند است. در این نوع درخت، تعداد گره های هر سطح بدین صورت است: سطح صفر دارای 1 گره ( ⁰ 2 )، سطح 1 دارای 2 گره ( 2¹ ) و سطح i دارای 2ͥ گره میباشد.

درخت دودویی کامل:

درخت دودویی کامل، درختی است که یا پر است یا با افزودن گره های پشت سر هم به سمت راست سطح پایینی، به درخت پر تبدیل میشود. اگر عمق درخت دودویی d باشد، در چنین درختی برگها در سطوح d یا d-1 قرار دارند.

خواص درختهای دودویی:

در هر درخت دودویی، حداکثر تعداد گره ها در سطح Ɩ برابر با ᶥ 2 است، بطوریکه Ɩ≥ 0 .

حداکثر تعداد گره های ممکن در درخت دودویی به ارتفاع h برابر با (2 ͪ )-1 است.

حداقل تعداد گره ها در درخت دودویی به ارتفاع h برابر با h است.

برای هر درخت دودویی غیرتهی، اگر n تعداد گره ها و e تعداد پیوندها باشد، آنگاه n=e+1 .

برای هر درخت دودویی غیر خالی T ، اگر n ₀ تعداد گره های برگ و n ₂ تعداد گره های داخلی باشد ، آنگاه n ₀ =n ₂ +1 .