کلون کردن درخت دودویی با اشاره گرهای تصادفی – راهنمای کاربردی

۲۳۶ بازدید

آخرین به‌روزرسانی: ۱۹ تیر ۱۴۰۲

زمان مطالعه: ۷ دقیقه

دانلود PDF مقاله

در این مطلب، چگونگی «کلون کردن درخت دودویی با اشاره گرهای تصادفی» (Clone a Binary Tree with Random Pointers) بیان و پیاده‌سازی آن در زبان برنامه‌نویسی ++C انجام شده است. در اینجا، منظور از کلون کردن در واقع کپی کردن است.

فهرست مطالب این نوشته

کلون کردن درخت دودویی با اشاره گرهای تصادفی

کلون کردن درخت دودویی با اشاره گرهای تصادفی

یک «درخت دودویی» (Binary Tree) داده شده که در آن هر «گره» (Node)، دارای ساختار زیر است.

اشاره‌گر تصادفی به هر گره تصادفی از درخت دودویی اشاره دارد و حتی می‌تواند به Null نیز اشاره و درخت دودویی داده شده را کلون کند.

روش ۱: استفاده از درهم‌سازی

ایده نهفته در پس روش استفاده از «درهم‌سازی» (Hash) آن است که نگاشت گره‌های درخت داده شده را در «جدول هش» (Hashtable) ذخیره کند. در ادامه، گام‌های انجام این کار همراه با جزئیات بیان شده‌اند.

فیلم آموزش مروری بر توابع Hash و خطر تصادم در آن ها (رایگان) در فرادرس

کلیک کنید

۱. به صورت بازگشتی، درخت دودویی داده شده را پیمایش و مقادیر کلید، اشاره گر چپ و اشاره گر راست را برای کلون کردن درخت کپی کن. در حین کپی، نگاشت را از گره درخت داده شده به گره درخت کلون شده در جدول هش ذخیره کن. در شبه کد زیر، «cloneNode» گره کنونی مشاهده شده از درخت کلون و «treeNode» گره کنونی مشاهده شده از درخت داده شده است.

 cloneNode->key = treeNode->key
cloneNode->left = treeNode->left
cloneNode->right = treeNode->right
map[treeNode] = cloneNode

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

در ادامه، پیاده‌سازی ++C ایده بالا، ارائه شده است. پیاده‌سازی که در ادامه آمده از unordered_map از STL استفاده کرده است.

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

Inorder traversal of original binary tree is:
[4 1], [2 NULL], [5 3], [1 5], [3 NULL],

Inorder traversal of cloned binary tree is:
[4 1], [2 NULL], [5 3], [1 5], [3 NULL],

روش ۲: ویرایش موقت درخت دودویی داده شده

الگوریتم این روش، در ادامه آمده است.

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

کلیک کنید

۱. گره‌های جدید را در درخت کلون شده بساز و هر گره جدید را در درخت اصلی، بین لبه اشاره‌گر چپ از گره متناظر درج کن. (مشاهده تصویر زیر، برای درک بهتر این موضوع، توصیه می‌شود.)

اگر کره کنونی A و فرزند سمت چپ آن B است (A — >> B)، گره جدید کلون شده با کلید A ساخته می‌شود (cA) و به عنوان A — >> cA — >> B قرار داده می‌شود (B می‌تواند نال یا فرزند غیر نال سمت چپ باشد). اشاره‌گر فرزند سمت راست به درستی تنظیم می‌شود. اگر برای فرزند کنونی A، فرزند راست در درخت اصلی C است (A — >> C)، سپس، گره‌های کلون شده متناظر cA و cC مشابه cA —- >> cC هستند.

کلون کردن درخت دودویی با اشاره گرهای تصادفی -- راهنمای کاربردی

۲. تنظیم اشاره‌گر تصادفی در درخت کلون شده به ازای درخت اصلی.

اگر اشاره‌گر تصادفی A به گره B اشاره کند، در درخت کلون شده، cA به cB اشاره می‌کند (cA و cB گره‌های جدید در درخت کلون شده و متناظر با گره‌های A و B در درخت اصلی هستند).

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

در ادامه، پیاده‌سازی الگوریتم بالا در زبان برنامه‌نویسی ++C ارائه شده است.

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

Inorder traversal of original binary tree is:
[5 9], [6 7], [7 NULL], [8 10], [9 7], [10 6], [11 9], [12 8], [13 NULL],

Inorder traversal of cloned binary tree is:
[5 9], [6 7], [7 NULL], [8 10], [9 7], [10 6], [11 9], [12 8], [13 NULL],

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

محصول، خدمات یا برند خود را در مجله فرادرس معرفی کنید.

کلیک کنید

بر اساس رای ۱ نفر

آیا این مطلب برای شما مفید بود؟

اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

ثبت نظر

منابع:

GeeksforGeeks

الهام حصارکی (+)

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.