{CodeGate}

درخت جستجوی دودویی در جاوا (Binary Search Tree)

در این جلسه تیم کدگیت را با آموزش درخت جستجوی دودویی در جاوا با همراهی کنید. پیش نیاز این قسمت شامل موارد زیر است:

  1. آشنایی با متد
  2. آشنایی با if
  3. آشنایی با for
  4. آشنایی با شی گرایی
  5. آشنایی با constructor
  6. آشنایی با this
  7. آشنایی با while

قبل از ایتکه توضیحات را آغاز کنم باید بگوییم که توضیحات الگوریتمی این آموزش از سایت www.algorithmha.ir گرفته شده است.

درخت دودویی

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

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

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

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

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

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

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

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

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

مهمترین کاربرد چنین درختی از نام آن مشخص است. این درخت با توجه به تعریف آن برای انجام عملیات جستجو مناسب است. فرض کنید در مجموعه اعداد درخت فوق به دنبال عدد 6 هستیم. ابتدا 6 را با مقدار گره رأس یعنی5 مقایسه می‌کنیم. این گره، گره مورد نظر ما نیست. عدد 6 هم از عدد 5 بزرگتر است. در نتیجه با توجه به تعریف درخت جستجوی دودویی، مطمئن هستیم که اگر گرهی با مقدار6 وجود داشته باشد، به طور حتم در زیردرخت راست گره 5 است. پس به سمت راست حرکت کرده و عدد 6  را با 8 مقایسه می‌کنیم. باز هم به گره مطلوب نرسیدیم. اما با توجه به اینکه 6 از 8 کوچکتر است، به زیردرخت چپ گره 8 مراجعه می‌کنیم. در این مرحله به گره با مقدار 6 می‌رسیم که گره مطلوب ما است.

اگر در حین جستجو مجبور به حرکت به سمتی شدیم که زیردرختی وجود ندارد، به این معنی است که گره مورد نظر در درخت وجود ندارد.

عملیات‌های اصلی بر روی درخت جستجوی دودویی

معمولاً عملیات زیر بر روی یک درخت جستجوی دودویی تعریف می‌شود:

  1. ایجاد یک درخت جستجوی خالی
  2. آزمایش خالی بودن درخت
  3. درج کردن یک کلید جدید در درخت، بدون برهم خوردن خاصیت درخت
  4. جستجو کردن و یافتن یک کلید خاص در درخت
  5. حذف کردن یک کلید از درخت، با حفط خاصیت درخت
  6. پیمایش درخت جستجوی دودویی، به طوری تمام گره‌ها دقیقاً یک بار مورد دسترسی قرار گیرند.

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

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

برای مثال فرض کنید می‌خواهیم گرهی با مقدار 7 را به درخت فوق اضافه کنیم:

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

و اگر گرهی با مقدار صفر درج کنیم:

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

زمانی که قصد ساخت یک درخت جستجوی دودویی را داریم، ترتیب درج مقادیر تاثیر مستقیمی در عمق درخت و سرعت اجرای عملیات جستجو خواهد داشت. اگر مجموعه اعداد وارد شده از قبل مرتب باشند، درخت به دست آمده از عمق n خواهد بود که در هر لایه‌ی آن تنها یک گره وجود دارد:

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

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

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

هر گره در درخت جستجوی دودویی ممکن است در یکی از سه وضعیت زیر باشد:

1.گره فاقد فرزند است: یعنی گره مذکور یک برگ است. در چنین حالتی به راحتی می‌توان گره را حذف کرده و فضای مصرفی آن را آزاد کرد.

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

2.گره دارای یک فرزند است: در این حالت گره فرزند را جایگزین گره مذکور می‌کنیم. به عبارت ساده‌تر، بین والد گره و فرزند گره ارتباط مستقیم برقرار کرده و گره مطلوب را حذف می‌کنیم.

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

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

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

گرهی که جایگزین می‌شود به طور حتم فرزند چپ ندارد (چرا؟). اما ممکن است فرزند راست داشته باشد. در این حالت عمل حذف طی دو مرحله انجام می‌شود. ابتدا گره جایگزین از محل خود بنا به حالت شماره‌ی 2حذف می‌شود. سپس گره اصلی با جایگزین شدن این گره حذف می‌گردد. حال نوبت به پیاده سازی درخت دودویی جستجو در جاوا رسیده است.

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

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

کلاس Node شامل سه فیلد data و leftchild و rightchild است. در این کلاس یک constructor است که مقدار data را معین میکند. برای تغییر یا حذف هر کدام فیلد ها میتوانید از setter و getter های نوشته شده استفاده کنید.

بعد از ساخت هر گره نیاز به ساخت درخت است که ما کلاس BST را برای این کار در نظر گرفتیم.

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

در این کلاس ما باید عملیات هایی که توضیح داده شد را پیاده سازی کنیم.

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

برای درج در درخت ابتدا باید به محلی برویم که میتوان گره را در آن قرار داد(در بالا توضیح داده شده است).متد insert برای درج در درخت است و کد آن به صورت زیر است.

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

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

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

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

ابتدا متدهای حذف گره درخت جستجوی دودویی در جاوا که در این کد استفاده شده را توضیح میدهیم.

  1. متد findmin: کوچکترین گره را در فرزندی که به عنوان ورودی میگیرد برمیگرداند.
  2. متد isrightchildofparentnode: بررسی میکند گره ای که میخواهیم حذف کنیم فرزند راست است یا خیر.
  3. متد isleftchildofparentnode: بررسی میکند گره ای که میخواهیم حذف کنیم فرزند چپ است یا خیر.
  4. متد nochild : بررسی میکند گره ای که ورودی گرفته است هیچ فرزندی نداشته باشد.
  5. متد onechild : بررسی میکند گره ای که به عنوان ورودی گرفته دقیقا یک فرزند دارد یا خیر.
  6. متد findparent: گره ای را پیدا میکند که فرزندش گره ای باشد که به عنوان ورودی گرفته(پدر گره را پیدا میکند)
  7. متد Search : جستو جو میکند که گره خاص وجود دارد یا خیر.

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

اگر گره ما فرزند دارد باید ببینیم یک فرزند دارد یا دو فرزند. برای یک فرزند ما جای فرزند گره را با خودش عوض میکنیم.

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

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

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

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

این قسمت برای کد خود یک main مینویسیم. کد زیر main برنامه درخت جستجوی دودویی است.

پسورد: www.codegate.ir

 

دسته : java, جاوا, ساختمان داده در جاوا, گراف در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz