قضيه‌هاي مربوط به بازده
| ساختار درختي درهم (Splay Tree) - قسمت آخر |
زمانی که به یک نود 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 عبارت است از 
.
|
با عرض سلام و خسته نباشید (به مناسبت پایان امتحانات!!) به کاربران گرامی !
دوستان عزیز ،
شما می توانید در قسمت زنگ تفریح با ارائه نظرات خود و پیشنهاد موضوعات جدید و جالب برای قسمت زنگ تفریح ، در قسمت "نظر شما" ، ضمن مشارکت در فعالیت های رشد ما را در این بخش یاری کنید.
منتظر نظرات شما هستیم !
پیشاپیش از همکاری صمیمانه ی شما سپاس گذاریم !
موفق باشید ! |