درخت گسترده

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

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

مزایا

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

معایب

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

عملیات‌های گسترش

گسترش

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

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

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

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

مرحله زیگ

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

مرحله زیگ-زاگ

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

مرحله زیگ-زیگ

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

درج

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

حذف

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

برنامه درخت اسپلی به زبان 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

<link rel="mw:PageProp/Category" href="./رده:مهندسی_نرم‌افزار" />