درخت گسترده

درخت اسپلی (به انگلیسی: Splay tree) یک درخت جستجوی دودویی خود متعادل است؛ که از قابلیت‌های جدیدی برخوردار می‌باشد که دسترسی به اطلاعات جدیداً دسترسی یافته را سهولت می‌بخشد؛ و عناصری که اخیراً دسترسی یافته‌اند سریعتر مورد دسترسی قرار می‌گیرند. این درخت اعمال اساسی مانند درج و جستجو و حذف را در(o(lgnانجام می‌دهد. برای خیلی از دنباله‌های غیر یکنواخت، بهتر از سایر درخت‌های جستجو عمل می‌کند. درخت اسپلی به وسیله «دانیل اسلیتور» و «رابرت تارجان» در سال ۱۹۸۵ اختراع شد. همهٔ عملیات معمول در درخت جستجوی دودویی با یک عمل پایه به نام splaying ترکیب می‌شوند. به این معنی که برای یک عنصر خاص درخت را باز می‌آراید تا عنصر در ریشهٔ درخت قرار بگیرد. یک راه انجام این کار این است که ابتدا یک جستجو برای یافتن عنصر مورد نظر انجام می‌دهیم وسپس آن را به بالای درخت می‌رسانیم.

مزایا

• کارایی بهتر: کارایی بهتر برای یک درخت اسپلی به خود متوازنی آن بستگی دارد و به این که عناصری که بارها دسترسی یافته‌اند به ریشه نزدیکتر شوند تا سریعتر مورد دسترسی قرار بگیرند. این تقریباً برای تمام کاربردهای عملی این ساختار مزیتی است که برای پیاده‌سازی کاشه و الگوریتم garbage collection بسیار مفید است. این ساختار هنگامی کارامدتر خواهد بود که دسترسی به صورت یک پارچه نباشد.
• پیاده‌سازی ساده‌تر: پیاده‌سازی ساده‌تری نسبت به دیگر درختهای جستجوی دودویی خود متوازن، مانند درخت قرمز سیاه و یا درخت هایAVLدارد.
• امکان ایجاد یک نسخه پایدار: که اجازه دسترسی به هر دو نسخه قبلی و جدید را پس از بروز رسانی می‌دهد. این می‌تواند در برنامه‌نویسی تابعی مفید باشد و به(O(lgn فضا در هر بروز رسانی نیاز دارد.
• بر خلاف سایر انواع درختان خود متعادل به خوبی با گره حاوی کلیدهای هویت کار می‌کند. حتی با وجود کلیدهای هویت، عملکرد در (O(lgn باقی می‌ماند. یک طراحی دقیق عملیات find می‌تواند چپ‌ترین و یا راست‌ترین گرهٔ کلید داده شده را برگرداند.

معایب

• درختانی می‌توانند وجود داشته باشند که توزیع داده شده از ورودی را «کمی» سریعتر انجام می‌دهند.
• عملکرد ضعیف در دسترسی یکنواخت: عملکرد درخت اسپلی بطور قابل توجهی بدتر از درخت جستجوی دودویی متعادل ساده برای دسترسی یکنواخت است.
• یکی از بدترین حالت‌های الگوریتم درخت اسپلی دسترسی ترتیبی به همه عناصر در درخت مرتب شده‌است که درخت را کاملاً نامتعادل می‌کند (این n دسترسی دارد که هرکدام از (o(lgn است). دوباره مورد دسترسی قرار دادن عنصر اول، باعث می‌شود که عملیاتی که از (O(n است اجرا شود تا درخت دوباره متوازن شود (قبل بازگشت عنصر اول). این تأخیر قابل توجهی برای عملیات نهایی است، با این حال، تحقیقات اخیر نشان می‌دهد که «متعادل‌سازی تصادفی» می‌تواند از اثر عدم تعادل جلوگیری کند و بازدهی مشابه سایر الگوریتم‌های خود متوازن بدهد.

فعالیت با Splay

هنگامی که یک گره x مورد دسترسی قرار می‌گیرد، ساختار درختی splay روی آن انجام می‌شود تا آن را در ریشه قرار دهد. برای این مقصود یک توالی از Splay Steps به‌انجام می‌رسد که هر مرحله این حرکت را بیش‌تر پیش می‌برد؛ و x را به ریشه نزدیکتر می‌کند. با انجام عملیات splay در گره مورد نظر بعد از هر دسترسی، گره‌ای که اخیراً مورد دسترسی قرار گرفته در نزدیکی ریشه درخت نگه داشته می‌شود و تقریباً متعادل باقی می‌ماند.

هر مرحله به سه عامل بستگی دارد:

• آیا x فرزند چپ یا راست گره پدر خود p است،
• آیا گره p ریشه‌است یا نه، و اگر نه
• آیا گره p فرزند چپ یا راست پدر خود g است، (g پدربزرگ x می‌شود).

سه مرحله splayعبارتند از:

مرحله zig

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

مرحله zig-zag

این مرحله هنگامی اجرا می‌شود که p ریشه نباشد و x فرزند راست و p فرزند چپ باشد (یا بر عکس). درخت ابتدا روی لبه بین x ,p دوران می‌کند و سپس روی لبه بین x و پدر جدیدش g دوران می‌کند.

مرحله Zig-zig

این مرحله وقتی اجرا می‌شود که p ریشه نباشد و x و p هر دو فرزندان راست یا چپ باشند. تصویر زیر حالتی را نشان می‌دهد که x ,p هر دو فرزندان چپ هستند. درخت ابتدا روی لبه اتصال p با پدرش g، و سپس روی لبه اتصال xبا p دوران می‌کند. مراحل زیگ‌زیگ تنها چیزی هستند که ساختارهای درختی درهم را از Retate to Root معرفی شده از سوی آلن و مونرو متمایز می‌سازند.

درج

برای درج گره x به درخت اسپلی، ما ابتدا آن را مانند درخت دودویی جستجوی نرمال درج می‌کنیم. سپس با الگوریتم اسپلی گره جدید را به بالای درخت می‌آوریم.

حذف

برای حذف گره x، از همان روش درخت دودویی جستجو استفاده می‌کنیم. اگر x دو بچه داشت، ما مقدار آن را با راست‌ترین گرهٔ زیر درخت چپ آن (in-order predecessor)یا چپ‌ترین گرهٔ زیر درخت راست آن (in-order successor)جایگزین می‌کنیم. سپس آن گره را حذف می‌کنیم. در این روش پاک کردن، به حذف گره با ۰ یا ۱ بچه کاهش می‌یابد. پس از حذف، پدر گرهٔ حذف شده را به بالای درخت می‌آوریم.

برنامه درخت اسپلی به زبان C

در برنامهٔ زیر ایده ساختن درخت اسپلی، به زبان C است: X گره‌ای است که عملیات اسپلی روی آن اجرا می‌شود و root ریشه درخت است.

void splay (struct node *x, struct node *root
{
        node *p,*g;
        /*check if node x is the root node*/
        if(x==root);
        /*Performs Zig step*/
        else if(x->parent==root)
        {  
                if(x==(x->parent)->left)
                rightrotation(root);
                else
                leftrotation(root);
        }     
        else  
        {     
                p=x->parent; /*now points to parent of x*/
                g=p->parent; /*now points to parent of x's parent*/
                /*Performs the Zig-zig step when x is left and x's parent is left*/
                if(x== p->left&&p ==g->left)
               {  
                       rightrotation(g);
                       rightrotation(p);
               }
               /*Performs the Zig-zig step when x is right and x's parent is right*/
               else if(x== p->right&&p ==g->right)
               {      
                       leftrotation(g);
                       leftrotation(p);
               }   
               /*Performs the Zig-zag step when x's is right and x's parent is left*/
               else if(x== p->right&&p ==g->left)
               {      
                       leftrotation(p);
                       rightrotation(g);
               }   
               /*Performs the Zig-zag step when x's is left and x's parent is right*/
               else if(x== p->left&&p ==g->right)
               {      
                       rightrotation(p);
                       leftrotation(g);
               }
               splay(x, root);
       }
}

منابع

• http://en.wikipedia.org/wiki/Splay_tree
• http://www.cs.gsu.edu/~skarmakar/cs3410/slide22.pdf
• http://ce.sharif.edu/~ghodsi/ds-alg-dic/dads-orig