درخت گسترده

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

مرحله زیگ

این مرحله هنگامی انجام می‌گیرد که 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);
       }}