زنگ‌تفریح تصادفی

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 ساختار درختي درهم (Splay Tree) - قسمت آخر (زنگ تفريح شماره‌ي 24)
ساختار درختي درهم (Splay Tree) - قسمت آخر (زنگ تفريح شماره‌ي 24)زنگ تفريح كامپيوتر
قضيه‌هاي مربوط به بازده

ساختار درختي درهم (Splay Tree) - قسمت آخر


 فعالیت با Splay

زمانی که به یک نود x دسترسی می‌شود، ساختار درختی درهم کاری می‌کند تا x به‌سمت ریشه‌ي ساختار حرکت کند. برای این مقصود یک توالی از Splay Steps به‌انجام می‌رسد که هر مرحله این حرکت را بیش‌تر پیش می‌برد. تا هنگامی که x از Grandparent (والد بزرگ) برخودار است هر مرحله‌ي خاص به دو عامل بستگی دارد:

 - آیا x کودک سمت راستی و یا سمت چپی نود والد خود p می‌باشد؟
 - آیا p کودک سمت راست و یا سمت چپ والد خود g (والد بزرگ x) مي‌باشد؟


بنابراین برای زمانی که x دارای یک والد بزرگ می‌باشد چهار حالت وجود دارد که به دو نوع از مراحل Splay تقسیم می‌شود.


 مرحله‌ي زيگ‌زاگ
زیگ‌زاگ زمانی پیش می‌آید که x فرزند سمت راست g باشد (تصویر بالا). P کودک جدید سمت چپ x می باشد، g کودک جدید سمت راست x است و زیر شاخه‌های A، B، C و D از x و g در صورت لزوم مجددا آرایش داده می‌شوند.
زیگ‌زاگ دیگر تصویر آینه این است یعنی زمانی که کودک سمت چپ p کودک سمت راست g می‌باشد.
توجه داشته باشید که یک مرحله زیگ‌زاگ مساوی است با دروان در لبه میان x و p و بعد دوران در لبه‌ي میان x و g.


 

 

 



 مرحله‌ي زيگ‌زاگ
زیگ‌زاگ زمانی پیش می‌آید که x فرزند سمت راست g باشد (تصویر بالا). P کودک جدید سمت راست x می‌باشد، g کودک جدید سمت راست x است و زیرشاخه‌های A، B، C و D از x و g در صورت لزوم مجددا آرایش داده می‌شوند.
زیگ‌زاگ دیگر تصویر آینه این است یعنی زمانی که کودک سمت چپ p کودک سمت راست g می‌باشد. توجه داشته باشید که مراحل زیگ‌زاگ تنها چیزی هستند که ساختارهای درختی درهم را از Retate to Root معرفی شده از سوی آلن و مونرو متمایز می‌سازند.

 

 



 مرحله‌ي زيگ
نوع سومی از مرحله‌ي Splay وجود دارد که زمانی انجام می‌شود که x دارای یک والد p می‌باشد اما والد بزرگ ندارد. به این وضعیت یک مرحله‌ي زیگ می‌گویند که دورانی بر روی لبه‌ي میان x و p می‌باشد. مراحل زیگ برای مواجهه با مسأله‌ي Parity وجود دارند و تنها به‌عنوان آخرین مرحله در فعالیت Splay و تنها زمانی که x در ابتدای عمل ساختار دارای زیرشاخه‌ي فرد باشد به‌انجام می­رسد.
با اجرای یک عمل Splay در نود مورد نظر بعد از هر دسترسی، نودهای که اخیرا به آن‌ها دسترسی صورت پذیرفته است در نزدیکی ریشه نگه داشته می‌شوند تا تعادل ساختار حفظ شود و از این طریق می‌توانیم به محدوده‌ي مطلوب زمان هرز رفته دست پیدا کنیم.

 


 قضیه‌های مربوط به بازده
چند قضیه و حدس در مورد بازده در بدترین زمان اجرا برای اجرای یک توالی S از دسترسی‌های m در یک ساختار درختی حاوی مؤلفه‌های n ارائه شده است. برخي از اين قضايا عبارت‌اند از:
- قضیه‌ي تعادل
- قضیه‌ي بهبودی استاتيك
- قضیه‌ي زبانه‌ي استاتیک
- قضیه‌ي مجموعه‌ي کاری
- قضیه‌ي زبانه‌ي دینامیک
- قضیه‌ي اسکنینگ

 

 

 


 حدس در مورد بهبودی دینامیک
علاوه بر قضیه‌هایی که در مورد میزان بازده ساختار درختی درهم ارائه می‌شوند در مقاله‌ي «اسلیتور» و «تارجان» حدس دیگری نیز عنوان شده است. به این حدس Dynamic Optimality Conjecture می‌گویند و اساسا بر این ادعاست که ساختارهای درختی درهم به‌خوبی هر الگوریتم باینری دیگر عمل می‌نمایند. A را هر گونه درخت جستجوی باینری در نظر می‌گیریم که از راه مسیر شاخه به x به ارزش d(x)+1 به یک مؤلفه دسترسی پیدا می‌کند و این‌که می‌توان دسترسی از طریق دوران در ساختار درختی به ارزش 1 برای هر دوران به‌میزان بازده دست یافت. را ارزش A برای اجرای توالی S در نظر می‌گیریم. بنابراین ارزش ساختار درختی همان میزان دسترسی می‌باشد. مورد خاصی هست که در آن این حدس با عنوان Traversal Conjecture نامیده می‌شود. Traversal Conjecture: T1 و T2 دو ساختار درختی حاوی مولفه های یکسان می باشند.

S یک توالی در نظر می‌گیریم که حاوی مشاهده‌ي مؤلفه‌های درون T2 پیش از نظم یافتن می‌شود. کل ارزش اجرای S از دسترسی به T1 عبارت است از .

با عرض سلام و خسته نباشید (به مناسبت پایان امتحانات!!) به کاربران گرامی !

دوستان عزیز ،

شما می توانید در قسمت زنگ تفریح با ارائه نظرات خود و پیشنهاد موضوعات جدید و جالب برای قسمت زنگ تفریح ، در قسمت "نظر شما" ، ضمن مشارکت در فعالیت های رشد ما را در این بخش یاری کنید.

منتظر نظرات شما هستیم !

پیشاپیش از همکاری صمیمانه ی شما سپاس گذاریم !

موفق باشید !

1386/3/19لينک مستقيم

فرستنده :
petros_2092 HyperLink HyperLink 1386/5/19
مـتـن : its the best thing i see.
پاسـخ :دوست عزيز!
از اظهار نظرت ممنونيم. اميدوارم نظرهاي اصلاحي خود را نيز براي‌امان ارسال كني.

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 زنگ تفريح‌ها

 
 المپياد كامپيوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  8577
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  8577