نمایش مبدأ برای درخت دودویی فرزند-چپ همزاد-راست

'''درخت دودویی فرزند چپ همزاد راست''' {{به انگلیسی|Left-child right-sibling binary tree}} {{اختصاری|LC-RS}} در [[علوم رایانه]]، یک [[درخت باینری]] است که بازنمایی‌ای از درخت <math>K</math> تایی {{به انگلیسی|k-ary tree}} است.<ref>{{cite book
 | title = Introduction To Algorithms
 | edition = 2nd
 | author = Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein
 | publisher = MIT Press
 | year = 2001
 | isbn = 978-0-262-03293-3
 | pages = 214–217
 | url = http://books.google.com/books?id=NLngYyWFl_YC&pg=PA214
}}</ref> روش تبدیل یک درخت <math>K</math> تایی دلخواه به یک درخت باینری به این صورت است که، ریشه درخت اولیه به عنوان ریشه درخت باینری در نظر گرفته می‌شود. سپس از ریشه شروع می‌کنیم و سمت چپ‌ترین فرزند هر رأس در درخت اولیه، فرزند چپ آن رأس در درخت باینری را می‌سازد و نزدیک‌ترین همزاد راست در درخت اولیه، فرزند راست درخت باینری را می‌سازد.<ref>Paul E. Black, [http://www.nist.gov/dads/HTML/leftChildrightSiblingBinaryTree.html Left child-right sibling binary tree] at the [[مؤسسه ملی فناوری و استانداردها|NIST]] [[Dictionary of Algorithms and Data Structures]]</ref> اگر درخت اولیه مرتب شده باشد، درخت جدید [[درخت جستجوی دودویی]] خواهد بود.

== درخت ==
[[پرونده:Tree1.png|پیوند=[[پرونده:Tree1.png]]|چپ|بندانگشتی|200x200پیکسل|نمونه‌ای از یک درخت]]

=== درخت چیست ===
درخت <math>G</math> یک گراف ساده بدون جهت است که در یکی از شروط معادل زیر صدق کند:<ref>Heaps</ref>
* <math>G</math> همبند است و دور ندارد.
* <math>G</math> هیج دوری ندارد و اگر یک یال به آن اضافه شود یک دور ساده در آن به وجود می‌آید.
* <math>G</math> همبند است و اگر یک یال آن حذف شود دیگر متصل نیست.
* <math>G</math> همبند است و [[گراف کامل]] ۳ رأسی <math>K_3</math> جزِئی از آن نیست.
* هر دو رأس در <math>G</math> با یک مسیر سادهٔ یکتا به هم وصل می‌شوند.
اگر <math>G</math> تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:
* <math>G</math> همبند است و <math>n-1</math> یال دارد.
* <math>G</math> دور ساده ندارد و <math>n-1</math> یال دارد.

=== فرزند ===
برای بررسی یک درخت ابتدا یک رأس مانند رأس {{ریاضی|V}} را انتخاب کرده و آن را به عنوان ریشه درخت در نظر می‌گیریم. حال اگر دو رأس مانند {{ریاضی|T , E}} به هم با یک یال متصل باشند با استفاده از تعریف فاصله که بیان می‌کند فاصله دو رأس از یک دیگر به میزان تعداد یال‌های کوتاه‌ترین مسیر بین آن دو رأس است (که با توجه به درخت بودن گراف مطمئن هستیم مسیر وجود دارد) تعریف می‌کنیم رأسی که فاصله کمتری تا رأس {{ریاضی|V}} که رأس ریشه است دارد پدر رأس دیگر است و دیگری فرزند آن به حساب می‌آید. برای مثال داریم:

<syntaxhighlight lang="text">
                                                                               ۱
                                                                             /   \
                                                                            /     \
                                                                           ۲       ۳
                                                                                 /   \
                                                                                /     \
                                                                               ۴       ۵

</syntaxhighlight>

در این شکل ۱ به عنوان ریشه انتخاب شده‌است، ۲ و ۳ فرزندان ۱ هستند، ۲ فرزندی ندارد و ۴ و ۵ فرزندان ۳ هستند. این درخت را به گونه‌ای دیگر نیز می‌توان نشان داد.<syntaxhighlight lang="text">
                                                                                ۲
                                                                                |
                                                                                ۱
                                                                                |
                                                                                ۳
                                                                              /   \
                                                                             ۴     ۵

</syntaxhighlight>

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

=== همزاد ===
به دو رأس مانند {{ریاضی|T , E}} همزاد می‌گوییم اگر پدر مشترک داشته باشند (پدر هر دو یک رأس باشد). به عبارتی دیگر به دو فرزند یک پدر همزاد گوییم. برای مثال در همان [[گراف (ریاضی)|گراف]] قبل داریم :                                                                                                                              <syntaxhighlight lang="text">
                                                                               ۱
                                                                             /   \
                                                                            /     \
                                                                           ۲       ۳
                                                                                 /   \
                                                                                /     \
                                                                               ۴       ۵

</syntaxhighlight>رئوس ۲ و ۳ که هردو دارای پدر مشترک ۱ هستند با یک دیگر همزاد هستند. به طریق مشابه نیز می‌توان گفت رئوس ۴ و ۵ نیز با یک دیگر همزاد هستند.

=== درخت <math>K</math> تایی ===
در نظریه گراف به یک درخت <math>K</math> تایی گفته می‌شود اگر هر رأس حداکثر به تعداد <math>K</math> بچه داشته باشد. برای مثال حالت خاصی از درخت <math>K</math> تایی حالت <math>K=2</math> است که به آن [[درخت باینری]] گفته می‌شود.<ref>{{cite web|url=http://xlinux.nist.gov/dads/HTML/perfectKaryTree.html|title=perfect k-ary tree|date=20 April 2011|accessdate=10 October 2011|publisher=U.S. National Institute of Standards and Technology|last=Black|first=Paul E.}}</ref> <syntaxhighlight lang="text">
                                                                               ۱
                                                                             / | \
                                                                            /  |  \
                                                                           /   |   \
                                                                          ۲    ۴    ۳
                                                                         /        / | \
                                                                        /        /  |  \
                                                                       ۸        ۷   |   ۵
                                                                                    ۶

</syntaxhighlight>
در این شکل یک درخت <math>K</math> تایی به ازای <math>K=3</math> است. چون در آن هر رأس حداکثر ۳ بچه دارد.

== درخت دودویی فرزند چپ همزاد راست چیست؟ ==
در یک [[درخت باینری]] مانند <math>T</math> می‌توان هر رأس را با دو [[اشاره‌گر (علوم رایانه)|اشاره گر]] در نظر گرفت. ابتدا در این درخت ریشه را تعریف می‌کنیم. سپس برای هر رأس از درخت <math>T</math> یک اشاره‌گر به اولین فرزند که به آن فرزند چپ می‌گوییم و اشاره‌گر دوم را به اولین همزاد بعد از خود در درخت که به اصطلاح همزاد راست گفته می‌شود تعریف می‌کنیم. حال برای پیدا کردن فرزند <math>n</math> ام یک رأس (برای مثال رأس <math>V</math>) با توجه به در اختیار داشتن فرزند چپ که اولین فرزند <math>V</math> است و در اختیار داشتن همزاد راست هر رأس (که در اینجا همزاد راست هر فرزند <math>V</math> مد نظر است) می‌توان با پیمایش فرزندان <math>V</math> فرزند <math>n</math> این رأس را پیدا کرد:<syntaxhighlight lang="pascal">
procedure kth-child(V, n):
    child ← V.child
    while n ≠ 0 and child ≠ nil:
        child ← child.next-sibling
        n ← n − 1
    return child
</syntaxhighlight>که کد این پیمایش در زبان پایتون به قرار زیر است:<syntaxhighlight lang="python3">
def kth-child(V, n):
    child = V.child
    while n != 0 and child is not None:
        child = child.nex-sibling
        n -= 1
    return child

</syntaxhighlight>
[[پرونده:Alibehrouz.gif|قاب|الگوریتم تبدیل درخت به درخت دودویی فرزند چپ همزاد راست]]
در شکل روبرو در هر مرحله (الگوریتم از ریشه شروع می‌شود) فرزند چپ و یال واصل به پدر به رنگ سبز و همزادهای آن همگی به رنگ زرد در می‌آیند. حال هر یالی که به رنگ زرد است حذف می‌شود و جایگزین آن به فرزند چپ پدر متصل می‌شوند. در انتها نیز درخت به لحاظ ظاهری مرتب می‌شود.

کد الگوریتم بالا را می‌توان به زبان جاوا به شکل زیر نوشت:

<syntaxhighlight lang="java">
public Child kth-child(V, n){
    Child Child = V.Child ;
    while(n != 0 && child != null){
        Child = Child.nex-sibling ;
        n -- ;
    }
    return child ;
}
</syntaxhighlight>
[[File:N-ary to binary.svg|پیوند=[[:en:File:N-ary to binary.svg]]|بندانگشتی|250x250پیکسل|تبدیل یک درخت ۶ تایی به یک درخت باینری]]
که تنها باید به این نکته توجه کرد که در صورت وجود <math>n</math> امین فرزند <math>V</math> برنامه به عنوان خروجی آن را بازگردانی می‌کند و در غیر این صورت خروجی تهی خواهد بود.

پروسه تبدیل یک درخت <math>K</math> تایی به یک درخت دودویی فرزند چپ همزاد راست گاهی با نام تبدیل کنوت {{به انگلیسی|[[دانلد کنوت|Knuth]] transform}} شناخته می‌شود.<ref>Computer Data Structures. John L. Pfaltz.</ref>

می‌توان [[الگوریتم|الگوریتمی]] به قرار زیر ارائه داد تا با استفاده از آن بتوانیم یک درخت <math>K</math> تایی را به یک درخت دودویی فرزند چپ همزاد راست تبدیل کنیم. در این الگوریتم ابتدا ریشه درخت  <math>K</math> تایی را به عنوان ریشه این درخت نیز انتخاب می‌کنیم. حال برای هر رأس در درخت دودویی فرزند چپ همزاد راست مانند <math>E</math> فرزند چپ در درخت <math>K</math> تایی را فرزند چپ و همزاد راست در درخت <math>K</math> تایی را فرزند راست در این درخت قرار می‌دهیم.<ref name=":0">{{یادکرد وب|نویسنده=|کد زبان=en|تاریخ=|وبگاه=|نشانی=[[:en:Left-child right-sibling binary tree]]|عنوان=Left-child_right-sibling_binary_tree}}</ref>

حال می‌خواهیم این الگوریتم را در فرایند تبدیل یک [[درخت (نظریه گراف)|درخت]] به یک درخت دودویی فرزند چپ همزاد راست بررسی کنیم و در این الگوریتم در شکل اول درخت باینری را مشاهده می‌کنیم که قرار است الگوریتم بر روی آن اجرا شود. هر رأس در این الگوریتم دارای دو نشانه گر است که با استفاده از آن‌ها یال‌ها در درخت نهایی رسم خواهند شد که آن دو نشانه گر فرزند چپ. همزاد راست رأس هستند.

<syntaxhighlight lang="text">
                                                                                  ۱
                                                                                 /|\
                                                                                / | \
                                                                               /  |  \
                                                                              ۲   ۳   ۴
                                                                             / \      |
                                                                            ۵   ۶     ۷
                                                                                     / \
                                                                                    ۸   ۹

</syntaxhighlight>
حال در صورتی که برای هر رأس تنها دو اشاره‌گر یعنی فرزند چپ یا اولین فرزند و همزاد راست یا اولین خواهر یا برادر را به یک دیگر از طریق یال وصل کنیم و باقی مانده یال‌ها را از درخت پاک کنیم خواهیم داشت:

<syntaxhighlight lang="text">
                                                                                  ۱
                                                                                 /
                                                                                /
                                                                               /
                                                                              ۲ ---- ۳ ---- ۴
                                                                             /             /
                                                                            ۵ ---- ۶      ۷
                                                                                         /
                                                                                        ۸ ---- ۹

</syntaxhighlight>که اگر دقت کنیم شکل حاصل یک درخت دودویی فرزند چپ همزاد راست خواهد بود. کافی است خط چین‌ها را که به درخت اضافه کرده‌ایم و عمودی هستند را ۴۵ درجه دوران بدهیم.<syntaxhighlight lang="text">
                                                                                  ۱
                                                                                 /
                                                                                /
                                                                               /
                                                                              ۲
                                                                             / \
                                                                            /   ۳
                                                                           ۵     \
                                                                            \     \
                                                                             \     ۴
                                                                              ۶   /
                                                                                 ۷
                                                                                /
                                                                               ۸
                                                                                \
                                                                                 ۹

</syntaxhighlight>
مثالی دیگر از این الگوریتم را می‌توانید در شکل زیر مشاهده کنید:
[[پرونده:Thirdtree.gif|وسط|بی‌قاب|600x600پیکسل|مثالی دیگر از تبدیل درخت به درخت دودویی فرزند چپ همزاد راست]]

=== بازگردانی الگوریتم ===
در این قسمت می‌خواهیم حالت بازگشت از یک درخت دودویی فرزند چپ همزاد راست به یک درخت <math>K</math> تایی را بررسی کنیم. ابتدا ریشه درخت را در جایگاه ریشه درخت خروجی قرار می‌دهیم. (باید توجه کرد در الگوریتم قبلی مکان ریشه تغییری ایجاد نمی‌شد) حال در هر رأس مانند <math>V</math> تا زمانی که می‌توان به سمت راست حرکت کرد تمام رئوس فرزندان پدر <math>V</math> یا به عبارتی دیگر همزادهای <math>V</math> هستند. حال تمام این رئوس را به عنوان فرزندان پدر <math>V</math> اضافه می‌کنیم. حال به رأس <math>V</math> بازگشته و فرزند چپ را در صورت وجود به فرزندان آن اضافه می‌کنیم و همین الگوریتم را برای فرزند چپ انجام می‌دهیم . <syntaxhighlight lang="python3">
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)
</syntaxhighlight>یا می‌توان به زبان جاوا به شکل زیر بیان کرد:<syntaxhighlight lang="java">
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);
    }
}
</syntaxhighlight>

== کاربرد ==
در بازنمایی درخت دودویی فرزند چپ همزاد راست بسیار کارآمدتر از شیوه نمایش سنتی یک درخت است اما هزینه‌ای که برای یافتن یک فرزند بخصوص از یک رأس مانند <math>V</math> می‌پردازیم بسیار زیاد است چون همان‌طور که در قسمت قبل نیز توضیح داده شد برای این کار باید فرزندان رأس <math>V</math> پیمایش شوند که در صورت اینکه درخت <math>K</math> تایی باشد هزینه این الگوریتم از <math>O(k)</math> خواهد بود که در صورت زیاد بودن مقدار <math>K</math> می‌تواند هزینه‌ای سنگین برای یافتن یک فرزند دربرداشته باشد. می‌توان گفت این روش در مواردی کارآمد است که:<ref name=":0" />
* نگرانی‌هایی مبنی بر کارایی حافظه داریم.
* دسترسی تصادفی به فرزندان در الگوریتم مورد نیاز نباشد.
در زمانی نگران مورد یک خواهیم بود که با حجم زیادی از اطلاعات برخورد داریم، برای مثال برای ذخیره‌سازی [[درخت تبارزایی]] که می‌تواند حجم زیادی داشته باشد استفاده از این روش ممکن است کارآمد باشد.<ref>{{Cite web|url=https://stackoverflow.com/questions/14015525/what-is-the-left-child-right-sibling-representation-of-a-tree-why-would-you-u|title=What is the left-child, right-sibling representation of a tree? Why would you use it?|accessdate=2016-12-12|website=stackoverflow.com}}</ref>

== جستارهای وابسته ==
[http://www.techiedelight.com/convert-normal-binary-tree-left-child-right-sibling-binary-tree/ convert normal binary tree]

[https://books.google.com/books?id=JLlqObQVFqcC&pg=PA204&lpg=PA204&dq=LCRS+tree&source=bl&ots=Y-1nOdWB9W&sig=jkuD0gRYGMeykBa7AOqrk38rqmc&hl=en&sa=X&ved=0ahUKEwiAg97y7J_UAhXHiiwKHZZyAWA4ChDoAQgnMAE#v=onepage&q=LCRS%20tree&f=false book about CLRS]

== منابع ==
{{پانویس|چپ‌چین=بله|۲}}
{{درخت‌ها در علوم کامپیوتر}}

[[رده:درخت‌های دودویی]]