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

در این مطلب، تعریف «درخت جستجوی دودویی» (Binary Search Tree | BST) بیان و عملیات در درخت جستجوی دودویی شامل جستجو و درج آموزش داده شده و همچنین، پیاده‌سازی‌های مربوط به این اعمال، در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java) و «پایتون» (Python) انجام شده است. تعریف درخت جستجوی دودویی در ادامه آمده است. درخت جستجوی دودویی، یک ساختار درختی مبتنی بر گره و دارای مشخصات زیر است:

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

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

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

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

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

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

فیلم آموزش الگوریتم های مرتب سازی در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

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

مثال:

اکنون، مقدار ۶ در درختی که در ادامه آمده است جستجو می‌شود. مراحل انجام این کار، در ادامه بیان شده‌اند.

1. از ریشه شروع کن.
2. عنصر درج شده را با ریشه مقایسه کن. اگر کمتر از ریشه بود، برای چپ بازگشت کن، در غیر این صورت، برای راست بازگشت کن.
3. اگر عنصری که باید جستجو شود در هر جایی یافت شد، مقدار true و در غیر این صورت، مقدار false را بازگردان.

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

در درخت جستجوی دودویی، یک کلید جدید همیشه در برگ درج می‌شود. کار با جستجوی کلید از ریشه آغاز می‌شود و تا هنگامی که گره برگ ساخته شود ادامه دارد.

فیلم آموزش درخت جستجوی دودویی (AVL) در ساختمان داده ها (رایگان) در فرادرس

کلیک کنید

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

         100                               100
        /   \        Insert 40            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                              \   
                                              40

درج کلید در درخت جستجوی دودویی در ++C

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

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

خروجی قطعه کدهای بالا، به صورت زیر است.

20
30
40
50
60
70
80

مثال:

در ادامه، مثالی ارائه شده که طی آن، عدد ۲ در درختی که تصویر آن در زیر آمده، درج می‌شود. مراحل انجام این کار، در زیر بیان شده است.

1. از ریشه شروع کن.
2. عنصر درج شده را با ریشه مقایسه کن، اگر از ریشه کمتر بود، برای چپ بازگشت کن، در غیر این صورت، برای راست بازگشت کن.
3. پس از رسیدن به پایان، آن گره را (اگر کمتر از مقدار کنونی بود) در چپ و در غیر این صورت، در راست قرار بده.

پیچیدگی زمانی جستجو و درج در درخت جستجوی دودویی

پیچیدگی زمانی در بدترین حالت از عملیات جستجو و درج، برابر با (O(h است که در آن، h ارتفاع درخت جستجوی دودویی محسوب می‌شود. در بدترین حالت، ممکن است نیاز باشد از ریشه به عمیق‌ترین گره برگ پیمایش شود. ارتفاع درخت دارای چولگی ممکن است برابر با n و پیچیدگی زمانی جستجو و درج ممکن است از درجه (O(n باشد.

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

نکاتی جالب پیرامون درخت جستجوی دودویی

• پیمایش مرتب درخت جستجوی دودویی همیشه یک خروجی مرتب شده تولید می‌کند.
• یک درخت جستجوی دودویی را می‌توان با پیمایش پیش‌ترتیب، پس‌ترتیب و یا پیمایش مرتبه سطحی ساخت. توجه به این نکته نیز لازم است که همیشه می‌توان پیمایش مرتب را با مرتب‌سازی تنها پیمایش داده شده به دست آورد.
• تعداد درخت‌های جستجوی دودویی با n کلید متمایز، یک «عدد کاتالان» (Catalan Number) است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
• برنامه محاسبه مجموع اعداد از ۱ تا n — راهنمای کاربردی

^^