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

مفهوم درخت در نظریه گراف ها، نشان دهنده گره‌هایی است که به وسیله یال‌ها یا لبه ها به هم متصل شده‌اند. ما در این نوشته در مورد درخت‌های دودویی (باینری) یا درخت‌های جستجوی دودویی ( Binary Search Tree ) به اختصار BST صحبت  خواهیم کرد. درخت دودویی نوع خاصی از ساختمان داده است که برای ذخیره‌سازی داده مورد استفاده قرار می‌گیرد. یک درخت دودویی شرایط خاصی دارد که در آن هر گره در حالت ماگزیمم دو فرزند دارد. درخت جستجوی دودوی یک ساختار داده مبتنی بر گره است که دارای خواص زیر است:

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

مثال درخت جستجوی دودویی

عملیاتی که می توان در درخت دودویی انجام داد شامل جستجو Search، اضافه کردن یا درج Insertion و حذف Delete خواهد بود. که در ادامه این سه عملیات تشریح می شوند.

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

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

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

بسته به حالت 1 و 2، زیردرخت سمت چپ یا زیردرخت سمت راست را با استفاده از الگوریتم بالا جستجو می‌کنیم. عمل جستجو در درخت جستجوی دودویی، از مرتبه O(h)‎ است که در آن h ارتفاع درخت است. چرا که حداکثر باید به میزان عمق درخت، به طرف پایین حرکت کنیم. برای مثال عدد 6 را می خواهیم در درخت بالا جستجو کنیم. برای این کار عملیات زیر را باید انجام داد:

  1. از ریشه شروع کنید (وضعیت 6 را با گره ریشه؟ کوچکتر است پس عدد در زیر دخت سمت چپ است )
  2. عدد 6 را با ریشه زیر درخت سمت چپ مقایسه کنید. (بزرگتر است پس عدد در زیر دخت سمت راست است )
  3. عدد 6 را با ریشه زیر درخت سمت راست مقایسه کنید. (برابر است پس پیدا شد)

عملیات درج در درخت دودویی

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

Insertion of a key

کد عملیات درج بصورت زیر خواهد بود.

حذف از درخت دودویی

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

  1. عنصر حذف شده در برگ باشد یعنی هیچ فرزندی نداشته باشد.
  2. دارای یک فرزند باشد
  3. دارای دو فرزند باشد.

حذف عنصر از برگ

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

درخت BST

 

حذف عنصر با یک فرزند

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

درخت BST

 

حذف عنصر با دو فرزند

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

درخت BST

کد عملیات حذف بصورت زیر خواهد بود.

تحلیل الگوریتم درخت جستجوی دودویی BST

در جستجو با استفاده از درخت جستجوی دودویی، در هر مرحله اگر به گره مورد نظر نرسیم، یک لایه در درخت به سمت پایین حرکت می‌کنیم. بنابراین تعداد مقایسه‌ها حداکثر برابر با عمق درخت است. حداقل تعداد مقایسه‌ها هم زمانی اتفاق می‌افتد که گره مورد نظر در رأس درخت قرار داشته باشد. در این حالت تنها یک مقایسه صورت می‌گیرد.

عمق یک درخت با n گره حداکثر n و حداقل log2n]+1] است. پس می‌توان گفت این روش جستجو حداقل از مرتبه‌ی یک، حداکثر از مرتبه‌ی n و به طور متوسط از مرتبه‌ی logn است.

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

 

مطالب زیر را حتما بخوانید

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

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

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.