درخت باینری
درخت جستجوی دودویی در پایتون (BST in Python)
در این جلسه تیم کدگیت را با آموزش درخت جستجوی دودویی در پایتون همراهی کنید. ابتدای این جلسه درخت جستجوی دودویی در پایتون را معرفی سپس عملیات‌هایی مانند درج و حذف گره را توضیح میدهیم. در پایان یک پیاده سازی کامل از این درخت جستجو را انجام خواهیم داد. پیش نیاز این جلسه شامل موارد زیر است:
- آشنایی با توابع
- آشنایی با شی گرایی
درخت جستجوی دودویی
درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:
1- مقادیر تمامی گره‌های زیردرخت راست از مقدار گره بزرگتر هستند.
2- مقادیر تمامی گره‌های زیردرخت چپ از مقدار گره کوچکتر هستند.
درج گره جدید در درخت جستجوی دودویی
برای اینکه یک گره جدید در درخت جستجوی دودویی اضافه درخت باینری کنیم، باید مکان آن را پیدا کنیم. برای یافتن محل مناسب، عملیات جستجو را برای آن (فرض می کنیم گره وجود دارد) انجام میدهیم. در آخر به گرهی خواهیم رسید که حداقل یکی از فرزندان آن تهی است. این گره والد گره جدید خواهد بود.
حذف گره از درخت جستجوی دودویی
حذف گره از درخت جستجوی دودویی به سه طریق انجام می‌گیرد:
1.گره برگ باشد که به راحتی قابل حذف از درخت می‌باشد
2.گره ما یک فرزند دارد. در این صورت گره حذف و فرزند آن جایگزین می‌شود.
3.گره دارای دو فرزند است. ابتدا گرهی با کوچک‌ترین مقدار در زیردرخت راست گره را پیدا میکنیم. درج این گره به جای گره قبلی شروط درخت جستجوی دودویی را به هم نمی‌زند. در نتیجه میتوان به راحتی آن را جایگزین کرد.
پیاده سازی درخت جستجوی دودویی در پایتون
برای پیاده سازی درخت دودویی در پایتون ابتدا باید یک کلاس برای نگهداری مقدار هر گره و فرزندان چپ و راست آن داشته باشیم.کلاس Node همین کار را برای ما می‌کند.
کلاس Node شامل سه فیلد key و left و right است. بعد از ساخت هر گره نیاز به ساخت درخت است که ما کلاس BinarySearchTree را برای این کار در نظر گرفتیم.
درخت ما نیاز به یک ریشه دارد که با آن به بقیه گره ها دسترسی پیدا کنیم. ما فیلد root را در درخت برای ارجاع به ریشه قرار دادیم. در این کلاس ما باید عملیات هایی که توضیح داده شد را پیاده سازی کنیم.
کد درج در درخت جستجوی دودویی
برای درج در درخت ابتدا باید به محلی برویم که میتوان گره درخت باینری را در آن قرار داد. توابع insert و insetRec برای درج در درخت است و کد آن به صورت زیر است.
همانطور که از کد درخت جستجوی دودویی در پایتون پیداست ابتدا چک میکنیم درخت ما خالی است یا خیر! اگر خالی بود ما ریشه را میسازیم.
اگر درخت ما تعدادی گره داشت ما نیاز به پیدا کردن محل مناسب برای درج گره جدید داریم. تابع insertRec به صورت بازگشتی درون درخت به جستجو و اضافه کردن گره جدید می‌پردازد.
کد حذف گره در درخت جستجوی دودویی
برای حذف همانطور که گفته شد ما باید سه مرحله را طی درخت باینری کنیم. مرحله اول آن است که ما گره ای بدون فرزند را بخواهیم حذف کنیم و مرحله دو اگر یک فرزند داشته باشد و مرحله سه اگر دو فرزند داشته باشد. تابع delete کد حذف را در سه مرحله به ما نشان میدهد.
همانطور که در کد میبینید ما ابتدا بررسی میکنیم آیا گره ای که میخواهیم وجود دارد یا خیر! در صورت درستی سه قسمتی که در قسمت حذف یک گره توضیح داده شد را انجام میدهیم
پیمایش درخت جستجوی دودویی
در این قسمت ما پیمایش inorder در درخت جستجوی دودویی را پیاده سازی خواهیم کرد. این پیمایش به این صورت است که ابتدا فرزند چپ یک گره را چاپ و بعد خود گره و در آخر فرزند راست گره را چاپ می‌کند. در درخت جستجو دودویی اگر از پیمایش inorder استفاده کنیم گره ها به صورت کوچک به بزرگ نمایش داده می‌شوند(چرا؟). برای پیاده سازی این پیمایش ما از روش بازگشتی استفاده کردیم. کد این پیمایش به صورت زیر است:
تست برنامه درخت جستجوی دودویی
برای اجرای برنامه بالا، کد زیر را بزنید:
در برنامه فوق ما از یک تابع به نام Serach استفاده کردیم. روش کار درخت باینری این تابع را به شما دوستان می‌سپاریم(در قسمت دانلود سورس کد، سورس این تابع آورده شده است). خروجی کد بالا به صورت زیر است:
insert 50 30 20 40 70 60 80:
search for 80 Node:
80 node deleted from Tree
Print Tree after Delete 80 node:
اگر سوالی در خصوص درخت جستجوی دودویی دارید در قسمت کامنت سوال خود را مطرح کنید تا پاسخگوی شما باشیم.
