درخت دودویی فرزند-چپ همزاد-راست کیست؟ توضیح بده.
درخت دودویی فرزند چپ همزاد راست در علوم رایانه، یک درخت باینری است که بازنمایی‌ای از درخت formula_1 تایی است. روش تبدیل یک درخت formula_1 تایی دلخواه به یک درخت باینری به این صورت است که، ریشه درخت اولیه به عنوان ریشه درخت باینری در نظر گرفته می‌شود. سپس از ریشه شروع می‌کنیم و سمت چپ‌ترین فرزند هر رأس در درخت اولیه، فرزند چپ آن رأس در درخت باینری را می‌سازد و نزدیک‌ترین همزاد راست در درخت اولیه، فرزند راست درخت باینری را می‌سازد. اگر درخت اولیه مرتب شده باشد، درخت جدید درخت جستجوی دودویی خواهد بود.درخت.درخت چیست.درخت formula_3 یک گراف ساده بدون جهت است که در یکی از شروط معادل زیر صدق کند:اگر formula_3 تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:فرزند.برای بررسی یک درخت ابتدا یک رأس مانند رأس را انتخاب کرده و آن را به عنوان ریشه درخت در نظر می‌گیریم. حال اگر دو رأس مانند به هم با یک یال متصل باشند با استفاده از تعریف فاصله که بیان می‌کند فاصله دو رأس از یک دیگر به میزان تعداد یال‌های کوتاه‌ترین مسیر بین آن دو رأس است (که با توجه به درخت بودن گراف مطمئن هستیم مسیر وجود دارد) تعریف می‌کنیم رأسی که فاصله کمتری تا رأس که رأس ریشه است دارد پدر رأس دیگر است و دیگری فرزند آن به حساب می‌آید. برای مثال داریم: ۱ / \ ۲ ۳ / \ ۴ ۵در این شکل ۱ به عنوان ریشه انتخاب شده‌است، ۲ و ۳ فرزندان ۱ هستند، ۲ فرزندی ندارد و ۴ و ۵ فرزندان ۳ هستند. این درخت را به گونه‌ای دیگر نیز می‌توان نشان داد. ۲ ۱ ۳ ۴ ۵در این شکل نیز همان گراف قبل نمایش داده شده با این تفاوت که در این شکل ۲ به عنوان ریشه درخت انتخاب شده‌است.همزاد.به دو رأس مانند همزاد می‌گوییم اگر پدر مشترک داشته باشند (پدر هر دو یک رأس باشد). به عبارتی دیگر به دو فرزند یک پدر همزاد گوییم. برای مثال در همان گراف قبل داریم : ۱ / \ ۲ ۳ / \ ۴ ۵رئوس ۲ و ۳ که هردو دارای پدر مشترک ۱ هستند با یک دیگر همزاد هستند. به طریق مشابه نیز می‌توان گفت رئوس ۴ و ۵ نیز با یک دیگر همزاد هستند.درخت formula_1 تایی.در نظریه گراف به یک درخت formula_1 تایی گفته می‌شود اگر هر رأس حداکثر به تعداد formula_1 بچه داشته باشد. برای مثال حالت خاصی از درخت formula_1 تایی حالت formula_19 است که به آن درخت باینری گفته می‌شود. ۱ / | \ ۲ ۴ ۳ / / | \ ۸ ۷ | ۵ ۶در این شکل یک درخت formula_1 تایی به ازای formula_21 است. چون در آن هر رأس حداکثر ۳ بچه دارد.درخت دودویی فرزند چپ همزاد راست چیست؟.در یک درخت باینری مانند formula_22 می‌توان هر رأس را با دو اشاره گر در نظر گرفت. ابتدا در این درخت ریشه را تعریف می‌کنیم. سپس برای هر رأس از درخت formula_22 یک اشاره‌گر به اولین فرزند که به آن فرزند چپ می‌گوییم و اشاره‌گر دوم را به اولین همزاد بعد از خود در درخت که به اصطلاح همزاد راست گفته می‌شود تعریف می‌کنیم. حال برای پیدا کردن فرزند formula_24 ام یک رأس (برای مثال رأس formula_25) با توجه به در اختیار داشتن فرزند چپ که اولین فرزند formula_25 است و در اختیار داشتن همزاد راست هر رأس (که در اینجا همزاد راست هر فرزند formula_25 مد نظر است) می‌توان با پیمایش فرزندان formula_25 فرزند formula_24 این رأس را پیدا کرد:procedure kth-child(V, n): child ← V.child while n ≠ 0 and child ≠ nil: child ← child.next-sibling n ← n − 1 return childکه کد این پیمایش در زبان پایتون به قرار زیر است:def kth-child(V, n): child = V.child while n != 0 and child is not None: child = child.nex-sibling n -= 1 return childدر شکل روبرو در هر مرحله (الگوریتم از ریشه شروع می‌شود) فرزند چپ و یال واصل به پدر به رنگ سبز و همزادهای آن همگی به رنگ زرد در می‌آیند. حال هر یالی که به رنگ زرد است حذف می‌شود و جایگزین آن به فرزند چپ پدر متصل می‌شوند. در انتها نیز درخت به لحاظ ظاهری مرتب می‌شود.کد الگوریتم بالا را می‌توان به زبان جاوا به شکل زیر نوشت:public Child kth-child(V, n){ Child Child = V.Child ; while(n != 0 &amp;&amp; child != null){ Child = Child.nex-sibling ; n -- ; return child ;که تنها باید به این نکته توجه کرد که در صورت وجود formula_24 امین فرزند formula_25 برنامه به عنوان خروجی آن را بازگردانی می‌کند و در غیر این صورت خروجی تهی خواهد بود.پروسه تبدیل یک درخت formula_1 تایی به یک درخت دودویی فرزند چپ همزاد راست گاهی با نام تبدیل کنوت شناخته می‌شود.می‌توان الگوریتمی به قرار زیر ارائه داد تا با استفاده از آن بتوانیم یک درخت formula_1 تایی را به یک درخت دودویی فرزند چپ همزاد راست تبدیل کنیم. در این الگوریتم ابتدا ریشه درخت formula_1 تایی را به عنوان ریشه این درخت نیز انتخاب می‌کنیم. حال برای هر رأس در درخت دودویی فرزند چپ همزاد راست مانند formula_35 فرزند چپ در درخت formula_1 تایی را فرزند چپ و همزاد راست در درخت formula_1 تایی را فرزند راست در این درخت قرار می‌دهیم.حال می‌خواهیم این الگوریتم را در فرایند تبدیل یک درخت به یک درخت دودویی فرزند چپ همزاد راست بررسی کنیم و در این الگوریتم در شکل اول درخت باینری را مشاهده می‌کنیم که قرار است الگوریتم بر روی آن اجرا شود. هر رأس در این الگوریتم دارای دو نشانه گر است که با استفاده از آن‌ها یال‌ها در درخت نهایی رسم خواهند شد که آن دو نشانه گر فرزند چپ. همزاد راست رأس هستند. ۱ / | \ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹حال در صورتی که برای هر رأس تنها دو اشاره‌گر یعنی فرزند چپ یا اولین فرزند و همزاد راست یا اولین خواهر یا برادر را به یک دیگر از طریق یال وصل کنیم و باقی مانده یال‌ها را از درخت پاک کنیم خواهیم داشت: ۱ / ۲ ---- ۳ ---- ۴ ۵ ---- ۶ ۷ ۸ ---- ۹که اگر دقت کنیم شکل حاصل یک درخت دودویی فرزند چپ همزاد راست خواهد بود. کافی است خط چین‌ها را که به درخت اضافه کرده‌ایم و عمودی هستند را ۴۵ درجه دوران بدهیم. ۱ / ۲ / ۳ ۵ \ \ ۴ ۶ / ۷ ۸ ۹مثالی دیگر از این الگوریتم را می‌توانید در شکل زیر مشاهده کنید:بازگردانی الگوریتم.در این قسمت می‌خواهیم حالت بازگشت از یک درخت دودویی فرزند چپ همزاد راست به یک درخت formula_1 تایی را بررسی کنیم. ابتدا ریشه درخت را در جایگاه ریشه درخت خروجی قرار می‌دهیم. (باید توجه کرد در الگوریتم قبلی مکان ریشه تغییری ایجاد نمی‌شد) حال در هر رأس مانند formula_25 تا زمانی که می‌توان به سمت راست حرکت کرد تمام رئوس فرزندان پدر formula_25 یا به عبارتی دیگر همزادهای formula_25 هستند. حال تمام این رئوس را به عنوان فرزندان پدر formula_25 اضافه می‌کنیم. حال به رأس formula_25 بازگشته و فرزند چپ را در صورت وجود به فرزندان آن اضافه می‌کنیم و همین الگوریتم را برای فرزند چپ انجام می‌دهیم . def rev-LCRS(node, Tree): if node.root : Tree.root = node temp = node while temp.rightChild is not None: Tree.search(node).parent.addChild(temp.rightChild) temp = temp.rightChild if node.leftChild is not None: Tree.search(node).addChild(node.leftChild) return rev-LCRS(node.leftChild, Tree)یا می‌توان به زبان جاوا به شکل زیر بیان کرد:public void rev-LCRS(Node node, Tree tree){ if (node.root) { tree.root = node; temp = node; while (temp.rightChild is not None){ Tree.search(node).parent.addChild(temp.rightChild); temp = temp.rightChild; if (node.leftChild is not None){ Tree.search(node).addChild(node.leftChild); return rev-LCRS(node.leftChild, Tree);کاربرد.در بازنمایی درخت دودویی فرزند چپ همزاد راست بسیار کارآمدتر از شیوه نمایش سنتی یک درخت است اما هزینه‌ای که برای یافتن یک فرزند بخصوص از یک رأس مانند formula_25 می‌پردازیم بسیار زیاد است چون همان‌طور که در قسمت قبل نیز توضیح داده شد برای این کار باید فرزندان رأس formula_25 پیمایش شوند که در صورت اینکه درخت formula_1 تایی باشد هزینه این الگوریتم از formula_47 خواهد بود که در صورت زیاد بودن مقدار formula_1 می‌تواند هزینه‌ای سنگین برای یافتن یک فرزند دربرداشته باشد. می‌توان گفت این روش در مواردی کارآمد است که:در زمانی نگران مورد یک خواهیم بود که با حجم زیادی از اطلاعات برخورد داریم، برای مثال برای ذخیره‌سازی درخت تبارزایی که می‌تواند حجم زیادی داشته باشد استفاده از این روش ممکن است کارآمد باشد.جستارهای وابسته.convert normal binary treebook about CLRS