چرخش درخت

چرخش درخت عبارت از یک عملیات بر روی درخت جستجوی دودویی که بدون برهم زدن ترتیب عناصر، ساختار درخت را تغییر می‌دهد.

در چرخش درخت یک گره به سمت پایین و یک گره به سمت بالا حرکت می‌کند. چرخش درخت برای تغییر شکل درخت و به خصوص برای کاهش ارتفاع درخت به وسیله حرکت دادن کوچک‌ترین زیر درخت به سمت پایین و بزرگ‌ترین زیر درخت به سمت بالا، مورد استفاده قرار می‌گیرد. بدین وسیله اجرای بسیاری از توابع و عملیات بر روی درخت آسان می‌گردد.

یک ناهماهنگی در توصیفات متفاوت از نحوه تعریف جهت چرخش‌های درخت وجود دارد. بعضی معتقدند جهت چرخش درخت وابسته به جهتی است که گره‌های درخت شیفت داده می‌شوند در حالی که برخی دیگر می‌گویند که وابسته به فرزندی است که به جای ریشه قرار می‌گیرد.

مثال ویرایش

همان‌طور که در شکل نشان داده شده‌است، عملیات چرخش به سمت راست بر روی Q به عنوان ریشه درخت انجام شده‌است؛ بنابراین یک چرخش به راست در درخت صورت گرفته‌است. نتیجه این عمل چرخش درخت در جهت حرکت عقربه‌های ساعت خواهد بود. در مقابل چرخش به سمت چپ را در درخت داریم که در نتیجه آن یک حرکت در جهت خلاف عقربه‌های ساعت انجام می‌شود. (در شکل بالا چرخش به چپ بر روی P به نوان ریشه صورت گرفته‌است).

جزئیات مثال ویرایش

زمانی که یک زیردرخت چرخش می‌یابد ارتفاع زیردرختی که چرخش بر روی آن انجام شده یک واحد کم می‌شود در حالی که ارتفاع زیر درخت‌های دیگر افزایش می‌یابد. وجود این خاصیت در ایجاد توازن در درخت مفید است.

اصطلاحات Root را برای پدر گره‌ای که چرخش بر روی آن انجام می‌شود، Pivot برای پدر جدید گره، RS جهتی (ضلع) که چرخش به آن سمت انجام می‌شود وOS را برای جهت مقابل در نظر بگیرید. در شکل بالا RS و OS به ترتیب C و P می‌باشند. شبه کد چرخش به صورت زیر می‌باشد:

Pivot = Root.OS
 Root.OS = Pivot.RS
 Pivot.RS = Root
 Root = Pivot

عملیات چرخش در یک زمان ثابت انجام می‌شود. برنامه نویسان باید توجه کنند که پدر ریشه بعد از چرخش به Point اشاره کند.

تغییرناپذیری (غیر بازگشتی) بین ترتیب ویرایش

چرخش درخت پیمایش بین ترتیب درخت را به صورت ثابت (غیر بازگشتی) درمی‌آورد در نتیجه ترتیب عناصر تحت تأثیر چرخش هر بخش در خت قرار نمی‌گیرد. در زیر پیمایش میان ترتیب در خت‌ها آورده شده‌است:

Left tree: ((A, P, B), Q, C) Right tree: (A, P, (B, Q, C))

مثال زیر یک کد به زبان پایتون است که محاسبه بالا را انجام می‌دهد:

def right_rotation(treenode):
  left, Q, C = treenode
  A, P, B = left
  return (A, P, (B, Q, C))

می‌توان از جنبه‌های دیگر نیز این مسئله را بررسی کرد.

چرخش به سمت چپ بر روی گرهP:

Let Q be P's right child.
Set Q to be the new root.
Set P's right child to be Q's left child.
Set Q's left child to be P.

چرخش به سمت چپ بر روی گره Q:

Let P be Q's left child.
Set P to be the new root.
Set Q's left child to be P's right child.
Set P's right child to be Q.

همچنین می‌توان چرخش دابل را که ترکیب چرخش به راست و چرخش به چپ است را تعریف کرد. یک چرخش دابل چپ بر روی گره X را می‌توان یک چرخش به راست بر روی فرزند راست و به دنبال آن یک چرخش به چپ بر روی فرزند چپ X تعریف کرد. به‌طور مشابه چرخش دابل راسترا می‌توان به صورت یک چرخش به چپ بر روی فرزند چپ X و یگ چرخش به راست ب روی گره X تعریف کرد.

چرخش‌های درخت در داده ساختارها مبتنی بر درخت مانند درخت متوازن، درخت سرخ-سیاه، درخت گسترده و تریپ‌ها کاربرد دارد. عملیات چرخش درخت در این داده ساختارها به دلیل تغییراتی که در ساختار درخت به صورت موضعی انجام می‌شود فقط در یک زمان ثابت انجام می‌گیرد: آن‌ها فقط بر روی ۵ گره اجرا می‌شوند و احتیاج به بررسی باقی‌مانده درخت نمی‌باشد.

درخت متوازن، درخت سرخ-سیاه، درخت گسترده، سه ساختار داده درخت جستجوی دودویی که به وسیله چرخش‌ها به روز و جدید می‌شوند، می‌باشند و امکان دستیابی سریع را به یک دنباله از توابع فراهم می‌کنند.

شرکت پذیری یک تابع دودویی یعنی انجام یک چرخش در درخت بدون تغییر در نتیجه نهایی یک مجموعه به نسبت مرتب که اعضای آن می‌توانند به صورت بک درخت دودویی بیان شوند و ترتیب بین آن‌ها به وسیله چرخش درخت مشخص می‌گردد.

چرخش‌ها برای ایجاد توازن ویرایش

توصیف تصویری از نحوه متوازن کردن درخت AVL به وسیله چرخش‌ها

یک درخت با استفاده از چرخش‌ها می‌تواند به صورت متوازن در آید. یک نوع از درخت که از این تکنیک برای برقراری توازن استفاده می‌کند در خت متوازن است. دلیل این که چرا چرخش‌ها می‌توانند باعث ایجاد تغییر در توازن درخت شوند، پس از چرخش آشکار می‌گردد. ارتفاع در جهتی که چرخش در آن انجام می‌شود یک واحد کم می‌شود در حالی که ارتفاع در طرف‌های دیگر یک واحد افزایش می‌یابد.

فاصله چرخش ویرایش

فاصله چرخش بین هر دو درخت دودویی با تعداد گره مساوی به صورت کمترین تعداد چرخش‌های لازم برای تبدیل یکی به دیگری تعریف می‌شود. با این فاصله، مجموعه گره‌های درخت دودویی به فضای متری تبدیل می‌شود. زمانی که دو درخت متمایز باشند این فاصله متقارن و مثبت خواهد بود و همچنین نامساوی مثلث را ارضا می‌کند. این مسئله که آیا یک الگوریتم از مرتبه چند جمله‌ای برای محاسبه فاصله چرخش وجود دارد، یک مسئله باز است. هر چند دانیل اسلیتور، رابرت تارژان، ویلیام ثارستون نشان داده‌اند که فاصله توازن بین هر دو درخت با n گره (برای n بزرگتر یا مساوی۱۱) حداکثر ۲n-۶ است وبه‌طور نامحدود بسیاری از جفت درخت‌ها به این مقدار از یکدیگر فاصله دارند…^[۱]

منابع ویرایش

↑ Sleator, ‎Daniel D. (1988), Tarjan, Robert E. ; Thurston, William P., Journal of the American Mathematical Society (به انگلیسی), vol. 1, p. 647–681 {{citation}}: |مقاله= ignored (help); External link in |شاپا= (help); Missing or empty |title= (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link).

E.NRamsden B.Sc,phD,D.phil

Wolfreton school ,Hull General chemistry

پیوند به بیرون ویرایش

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

[1] Sleator, ‎Daniel D. (1988), Tarjan, Robert E. ; Thurston, William P., Journal of the American Mathematical Society (به انگلیسی), vol. 1, p. 647–681 {{citation}}: |مقاله= ignored (help); External link in |شاپا= (help); Missing or empty |title= (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link).

[۱]