موضوع مقاله: درخت دودویی فرزند-چپ همزاد-راست | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت دودویی فرزند-چپ همزاد-راست | مقدمه: درخت دودویی فرزند چپ همزاد راست در علوم رایانه، یک درخت باینری است که بازنمایی‌ای از درخت تایی است. | ## بخش 1: درخت دودویی فرزند-چپ همزاد-راست | روش تبدیل یک درخت تایی دلخواه به یک درخت باینری به این صورت است که، ریشه درخت اولیه به عنوان ریشه درخت باینری در نظر گرفته می‌شود. سپس از ریشه شروع می‌کنیم و سمت چپ‌ترین فرزند هر رأس در درخت اولیه، فرزند چپ آن رأس در درخت باینری را می‌سازد و نزدیک‌ترین همزاد راست در درخت اولیه، فرزند راست درخت باینری را می‌سازد.Paul E. اگر تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند: همبند است و یال دارد. فرزند برای بررسی یک درخت ابتدا یک رأس مانند رأس را انتخاب کرده و آن را به عنوان ریشه درخت در نظر می‌گیریم. حال اگر دو رأس مانند به هم با یک یال متصل باشند با استفاده از تعریف فاصله که بیان می‌کند فاصله دو رأس از یک دیگر به میزان تعداد یال‌های کوتاه‌ترین مسیر بین آن دو رأس است (که با توجه به درخت بودن گراف مطمئن هستیم مسیر وجود دارد) تعریف می‌کنیم رأسی که فاصله کمتری تا رأس که رأس ریشه است دارد پدر رأس دیگر است و دیگری فرزند آن به حساب می‌آید. برای مثال داریم: ۱ / \ / \ ۲ ۳ / \ / \ ۴ ۵ در این شکل ۱ به عنوان ریشه انتخاب شده‌است، ۲ و ۳ فرزندان ۱ هستند، ۲ فرزندی ندارد و ۴ و ۵ فرزندان ۳ هستند. ۲ | ۱ | ۳ / \ ۴ ۵ در این شکل نیز همان گراف قبل نمایش داده شده با این تفاوت که در این شکل ۲ به عنوان ریشه درخت انتخاب شده‌است. همزاد به دو رأس مانند همزاد می‌گوییم اگر پدر مشترک داشته باشند (پدر هر دو یک رأس باشد). | ## بخش 2: درخت دودویی فرزند-چپ همزاد-راست | برای مثال در همان گراف قبل داریم : ۱ / \ / \ ۲ ۳ / \ / \ ۴ ۵رئوس ۲ و ۳ که هردو دارای پدر مشترک ۱ هستند با یک دیگر همزاد هستند. درخت تایی در نظریه گراف به یک درخت تایی گفته می‌شود اگر هر رأس حداکثر به تعداد بچه داشته باشد. سپس برای هر رأس از درخت یک اشاره‌گر به اولین فرزند که به آن فرزند چپ می‌گوییم و اشاره‌گر دوم را به اولین همزاد بعد از خود در درخت که به اصطلاح همزاد راست گفته می‌شود تعریف می‌کنیم. حال هر یالی که به رنگ زرد است حذف می‌شود و جایگزین آن به فرزند چپ پدر متصل می‌شوند. می‌توان الگوریتمی به قرار زیر ارائه داد تا با استفاده از آن بتوانیم یک درخت تایی را به یک درخت دودویی فرزند چپ همزاد راست تبدیل کنیم. در این الگوریتم ابتدا ریشه درخت تایی را به عنوان ریشه این درخت نیز انتخاب می‌کنیم. حال برای هر رأس در درخت دودویی فرزند چپ همزاد راست مانند فرزند چپ در درخت تایی را فرزند چپ و همزاد راست در درخت تایی را فرزند راست در این درخت قرار می‌دهیم. حال می‌خواهیم این الگوریتم را در فرایند تبدیل یک درخت به یک درخت دودویی فرزند چپ همزاد راست بررسی کنیم و در این الگوریتم در شکل اول درخت باینری را مشاهده می‌کنیم که قرار است الگوریتم بر روی آن اجرا شود. | ## بخش 3: درخت دودویی فرزند-چپ همزاد-راست | هر رأس در این الگوریتم دارای دو نشانه گر است که با استفاده از آن‌ها یال‌ها در درخت نهایی رسم خواهند شد که آن دو نشانه گر فرزند چپ. ۱ /|\ / | \ / | \ ۲ ۳ ۴ / \ | ۵ ۶ ۷ / \ ۸ ۹ حال در صورتی که برای هر رأس تنها دو اشاره‌گر یعنی فرزند چپ یا اولین فرزند و همزاد راست یا اولین خواهر یا برادر را به یک دیگر از طریق یال وصل کنیم و باقی مانده یال‌ها را از درخت پاک کنیم خواهیم داشت: ۱ / / / ۲ ۳ ۴ / / ۵ ۶ ۷ / ۸ ۹که اگر دقت کنیم شکل حاصل یک درخت دودویی فرزند چپ همزاد راست خواهد بود. کافی است خط چین‌ها را که به درخت اضافه کرده‌ایم و عمودی هستند را ۴۵ درجه دوران بدهیم. ۱ / / / ۲ / \ / ۳ ۵ \ \ \ \ ۴ ۶ / ۷ / ۸ \ ۹ مثالی دیگر از این الگوریتم را می‌توانید در شکل زیر مشاهده کنید: وسط|بی‌قاب|600x600پیکسل|مثالی دیگر از تبدیل درخت به درخت دودویی فرزند چپ همزاد راست بازگردانی الگوریتم در این قسمت می‌خواهیم حالت بازگشت از یک درخت دودویی فرزند چپ همزاد راست به یک درخت تایی را بررسی کنیم. (باید توجه کرد در الگوریتم قبلی مکان ریشه تغییری ایجاد نمی‌شد) حال در هر رأس مانند تا زمانی که می‌توان به سمت راست حرکت کرد تمام رئوس فرزندان پدر یا به عبارتی دیگر همزادهای هستند. حال به رأس بازگشته و فرزند چپ را در صورت وجود به فرزندان آن اضافه می‌کنیم و همین الگوریتم را برای فرزند چپ انجام می‌دهیم . می‌توان گفت این روش در مواردی کارآمد است که: نگرانی‌هایی مبنی بر کارایی حافظه داریم. | ## جمع‌بندی | در زمانی نگران مورد یک خواهیم بود که با حجم زیادی از اطلاعات برخورد داریم، برای مثال برای ذخیره‌سازی درخت تبارزایی که می‌تواند حجم زیادی داشته باشد استفاده از این روش ممکن است کارآمد باشد.