درخت جستجوی دودویی در پایتون (BST in Python)

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

  1. آشنایی با توابع
  2. آشنایی با if
  3. آشنایی با for
  4. آشنایی با while
  5. آشنایی با شی گرایی

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

درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:

    1- مقادیر تمامی گره‌های زیردرخت راست از مقدار گره بزرگتر هستند.

    2- مقادیر تمامی گره‌های زیردرخت چپ از مقدار گره کوچکتر هستند.

درخت جستجوی دودویی در پایتون

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

برای اینکه یک گره جدید در درخت جستجوی دودویی اضافه کنیم، باید مکان آن را پیدا کنیم. برای یافتن محل مناسب، عملیات جستجو را برای آن (فرض می کنیم گره وجود دارد) انجام می‌دهیم. در آخر به گرهی خواهیم رسید که حداقل یکی از فرزندان آن تهی است. این گره والد گره جدید خواهد بود.

درخت جستجوی دودویی در پایتون

حذف گره از درخت جستجوی دودویی

حذف گره از درخت جستجوی دودویی به سه طریق انجام می‌گیرد:

1.گره برگ باشد که به راحتی قابل حذف از درخت می‌باشد

درخت جستجوی دودویی در پایتون

2.گره ما یک فرزند دارد. در این صورت گره حذف و فرزند آن جایگزین می‌شود.

درخت جستجوی دودویی در پایتون

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

درخت جستجوی دودویی در پایتون

پیاده سازی درخت جستجوی دودویی در پایتون

برای پیاده سازی درخت دودویی در پایتون ابتدا باید یک کلاس برای نگهداری مقدار هر گره و فرزندان چپ و راست آن داشته باشیم.کلاس Node همین کار را برای ما  می‌کند.

 کلاس Node شامل سه فیلد key و left و right است. بعد از ساخت هر گره نیاز به ساخت درخت است که ما کلاس BinarySearchTree را برای این کار در نظر گرفتیم.

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

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

برای درج در درخت ابتدا باید به محلی برویم که میتوان گره را در آن قرار داد. توابع insert و insetNode برای درج در درخت است و کد آن به صورت زیر است.

همانطور که از کد درخت جستجوی دودویی در پایتون  پیداست ابتدا چک میکنیم درخت ما خالی است یا خیر! اگر خالی بود ما ریشه را میسازیم.

اگر درخت ما تعدادی گره داشت ما نیاز به پیدا کردن محل مناسب برای درج گره جدید داریم. تابع insertNode به صورت بازگشتی درون درخت به جستجو می‌پردازد.

کد حذف گره در درخت جستجوی دودویی

برای حذف همانطور که گفته شد ما باید سه مرحله را طی کنیم. مرحله اول آن است که ما گره ای بدون فرزند را بخواهیم حذف کنیم و مرحله دو اگر یک فرزند داشته باشد و مرحله سه اگر دو فرزند داشته باشد. تابع delete کد حذف را در سه مرحله به ما نشان میدهد.

همانطور که در کد میبینید ما ابتدا بررسی میکنیم آیا گره ای که میخواهیم وجود دارد یا خیر! در صورت درستی سه قسمتی که در قسمت حذف یک گره توضیح داده شد را انجام میدهیم

پیمایش درخت جستجوی دودویی

در این قسمت ما پیمایش inorder در درخت جستجوی دودویی را پیاده سازی خواهیم کرد. این پیمایش به این صورت است که ابتدا فرزند چپ یک گره را چاپ و بعد خود گره و در آخر فرزند راست گره را چاپ می‌کند. در درخت جستجو دودویی اگر از پیمایش inorder استفاده کنیم گره ها به صورت کوچک به بزرگ نمایش داده می‌شوند(چرا؟). برای پیاده سازی این پیمایش ما از روش بازگشتی استفاده کردیم. کد این پیمایش به صورت زیر است:

بیشتر بخوانید:  تبدیل سپیا رنگ در پایتون (Convert to Sepia colored image)

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

برای اجرای برنامه بالا، کد زیر را بزنید:

در برنامه فوق ما از یک تابع به نام Serach استفاده کردیم. روش کار این تابع را به شما دوستان می‌سپاریم(در قسمت دانلود سورس کد، سورس این تابع آورده شده است). خروجی کد بالا به صورت زیر است:

insert 50 30 20 40 70 60 80:

inorder Permutation:

20

30

40

50

60

70

80

search for 80 Node:

80  is in tree

80 node deleted from Tree

Print Tree after Delete 80 node:

20

30

40

50

60

70

اگر سوالی در خصوص درخت جستجوی دودویی دارید در قسمت کامنت سوال خود را مطرح کنید تا پاسخگوی شما باشیم.

    پسورد: www.codegate.ir

    دیدگاهتان را بنویسید

    نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *