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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

درخت دودویی فرزند-چپ همزاد-راست (به انگلیسی: Left-child right-sibling binary tree) (با نماد اختصاری LC-RS)در علوم رایانه، یک درخت باینری است که بازنمایی‌ای از درخت k تایی (به انگلیسی: k-ary tree) است.[۱] فرایند تبدیل یک درخت k تایی به یک درخت فرزند-چپ همزاد-راست در حالت کلی، بدون داشتن اطلاعات اضافی برگشت‌پذیر نیست.

روش تبدیل یک درخت k تایی دلخواه به یک درخت باینری به این صورت است که، ریشه درخت اولیه به عنوان ریشه درخت باینری درنظر گرفته می‌شود. سپس از ریشه شروع می‌کنیم و سمت چپ ترین فرزند هر نود در درخت اولیه، فرزند چپ آن نود در درخت باینری را می‌سازد و نزدیک‌ترین همزاد راست در درخت اولیه، فرزند راست درخت باینری را می‌سازد[۲]. اگر درخت اولیه مرتب شده باشد، درخت جدید درخت جستجوی دودویی خواهد بود.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  1. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein (2001). Introduction To Algorithms (2nd ed.). MIT Press. pp. 214–217. ISBN 9780262032933. 
  2. Paul E. Black, Left child-right sibling binary tree at the NIST Dictionary of Algorithms and Data Structures