مزایا و مضرات باینری

درخت جستجوی باینری (BST) یک درخت باینری مخصوص است که دارای خواص است:

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

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

عملیات روی درخت جستجوی باینری:

چهار عمل اصلی BST:

1. جستجوکردن،
2. درج ، و
3. حذف
4. گذرگاه

1. جستجو در BST:

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

جستجو در الگوریتم BST:-

• بررسی کنید که آیا درخت تهی است ، اگر درخت تهی نیست ، مراحل زیر را دنبال کنید.
• کلید جستجو را با ریشه BST مقایسه کنید.
• اگر کلید از ریشه کمتر است ، در زیر قسمت سمت چپ جستجو کنید.
• اگر کلید از ریشه بزرگتر است ، در زیر درخت راست جستجو کنید.
• اگر کلید برابر با root است ، پس جستجو را موفق و چاپ کنید.
• مرحله 3 ، 4 یا 5 را برای زیر درخت به دست آمده تکرار کنید.

2. درج در BST:

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

3. حذف در BST:

حذف در BST شامل سه مورد است:-

ابتدا کلید حذف شده را با استفاده از الگوریتم جستجو جستجو کنید و گره را پیدا کنید. سپس تعداد فرزندان گره را حذف کنید.

• مورد 1- اگر گره حذف شود گره برگ است: اگر گره حذف شود یک گره برگ است ، آن را حذف کنید.
• مورد 2- اگر گره حذف شود یک فرزند دارد: اگر گره حذف شود یک فرزند دارد ، گره را حذف کرده و فرزند گره را در موقعیت گره حذف شده قرار دهید.
• مورد 3- اگر گره حذف شود دارای دو فرزند است: اگر گره حذف شود دارای دو فرزند است ، پس از آن ، جانشین Inorder یا سلف Inorder گره را با توجه به نزدیکترین مقدار توانمند گره پیدا کنید. با استفاده از موارد فوق ، جانشین یا سلف را حذف کنید. گره را با جانشین یا سلف Inorder جایگزین کنید.

4- سفر در BST:

4 نوع تراورس از درخت جستجوی باینری وجود دارد.

سطح ترازو سفارش: هر گره درخت به ترتیب از سطح آن به ترتیب سطح می شود.

پیش سفارش Traversal: گره ها در قالب Root و سپس Subtree سمت چپ و سپس Subtree راست عبور می کنند.

inorder traversal: گره ها در قالب Subtree سمت چپ و سپس Root و سپس Subtree راست عبور می کنند.

Post Taversal: گره ها در قالب زیر درختان سمت چپ و سپس STREE RIGHT و سپس ROOT عبور می کنند

برنامه های درخت جستجوی باینری:

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

استفاده از زمان واقعی درخت جستجوی باینری:

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

مزایای درخت جستجوی باینری:

• BST هنگام تعادل در درج و حذف سریع است. با پیچیدگی زمانی O (log n) سریع است.
• BST همچنین برای جستجوی سریع ، با پیچیدگی زمانی O (log n) برای اکثر عملیات است.
• BST کارآمد است. این کارآمد است زیرا آنها فقط عناصر را ذخیره می کنند و برای نشانگرها یا سایر ساختارهای داده نیازی به حافظه اضافی ندارند.
• ما همچنین می توانیم نمایش داده شدگان را انجام دهیم - کلیدهای بین N و M را پیدا کنیم (N
• کد BST نسبت به سایر ساختارهای داده ساده است.
• BST می تواند به طور خودکار عناصر را به عنوان درج مرتب کند ، بنابراین عناصر همیشه به ترتیب مرتب شده ذخیره می شوند.
• BST را می توان به راحتی برای ذخیره داده های اضافی یا پشتیبانی از سایر عملیات اصلاح کرد. این باعث انعطاف پذیری آن می شود.

مضرات درخت جستجوی باینری:

• نقطه ضعف اصلی این است که ما همیشه باید یک درخت جستجوی باینری متعادل را پیاده سازی کنیم. در غیر این صورت ممکن است هزینه عملیات لگاریتمی و انحطاط در یک جستجوی خطی در یک آرایه نباشد.
• آنها برای ساختارهای داده ای که باید به طور تصادفی به آنها دسترسی پیدا کنند ، مناسب نیستند ، زیرا پیچیدگی زمانی برای جستجو ، درج و حذف عملیات O (log n) است که برای مجموعه داده های بزرگ مفید است ، اما به همان اندازه سریع دیگر نیستساختار داده مانند آرایه یا جداول هش.
• BST می تواند نامتعادل یا دژنراسیون شود که می تواند پیچیدگی را افزایش دهد.
• برخی از عملیات را که با ساختار داده های سفارش داده شده امکان پذیر است ، پشتیبانی نکنید.
• آنها تضمین نمی شوند که متعادل شوند ، به این معنی که در بدترین حالت ، ارتفاع درخت می تواند O (n) باشد و پیچیدگی زمانی برای عملیات می تواند به O (n) تخریب شود.

توصیه شده

مشکلات DSA را در تمرین GFG حل کنید.