أشجار التباعد هي أشجار البحث الثنائية ذاتية التوازن أو المعدلة ذاتيًا. بمعنى آخر، يمكننا القول أن أشجار التباعد هي أشكال مختلفة من أشجار البحث الثنائية. الشرط الأساسي لأشجار التباعد هو أن نعرف أشجار البحث الثنائية.

كما نعلم بالفعل، التعقيد الزمني لشجرة البحث الثنائية في كل حالة. التعقيد الزمني لشجرة البحث الثنائية في الحالة المتوسطة هو يا (تسجيل الدخول) والتعقيد الزمني في أسوأ الحالات هو O(n). في شجرة البحث الثنائية، تكون قيمة الشجرة الفرعية اليسرى أصغر من العقدة الجذرية، وقيمة الشجرة الفرعية اليمنى أكبر من العقدة الجذرية؛ في مثل هذه الحالة، سيكون تعقيد الوقت يا (تسجيل الدخول) . إذا كانت الشجرة الثنائية منحرفة إلى اليسار أو منحرفة إلى اليمين، فإن التعقيد الزمني سيكون O(n). للحد من الانحراف، و AVL والشجرة الحمراء والسوداء جاء في الصورة، بعد يا (تسجيل الدخول ) التعقيد الزمني لجميع العمليات في جميع الحالات. يمكننا أيضًا تحسين هذا التعقيد الزمني من خلال إجراء المزيد من التطبيقات العملية، وبالتالي فإن الشجرة الجديدة ما هي شجرة التكاثر؟

شجرة التمدد هي شجرة ذاتية التوازن، ولكن تعتبر أشجار AVL وRed-Black أيضًا أشجارًا ذاتية التوازن. ما الذي يجعل شجرة التمدد فريدة من نوعها بين شجرتين. لديها خاصية إضافية تجعلها فريدة من نوعها وهي اللعب.

تحتوي شجرة التباعد على نفس العمليات مثل a شجرة البحث الثنائية ، أي الإدراج والحذف والبحث، ولكنه يحتوي أيضًا على عملية أخرى، أي التفلطح. لذا. جميع العمليات في شجرة التباعد يتبعها تباعد.

الأشجار المفلطحة ليست أشجارًا متوازنة تمامًا، ولكنها أشجار متوازنة تقريبًا. دعونا نفهم عملية البحث في شجرة التباعد.

لنفترض أننا نريد البحث عن 7 عناصر في الشجرة، كما هو موضح أدناه:

للبحث عن أي عنصر في شجرة التباعد، سنقوم أولاً بتنفيذ عملية شجرة البحث الثنائية القياسية. وبما أن 7 أقل من 10، فسنأتي إلى يسار العقدة الجذرية. بعد إجراء عملية البحث، نحتاج إلى إجراء عملية التفلطح. هنا يعني التفليش أن العملية التي نقوم بها على أي عنصر يجب أن تصبح العقدة الجذرية بعد إجراء بعض عمليات إعادة الترتيب. سيتم إعادة ترتيب الشجرة من خلال الدورات.

ملاحظة: يمكن تعريف شجرة التباعد على أنها الشجرة المعدلة ذاتيًا والتي تؤدي فيها أي عملية يتم إجراؤها على العنصر إلى إعادة ترتيب الشجرة بحيث يصبح العنصر الذي تم تنفيذ العملية عليه هو العقدة الجذرية للشجرة.

التناوب

هناك ستة أنواع من الدورات المستخدمة في التفلطح:

1. دوران متعرج (دوران لليمين)
2. الدوران المتعرج (الدوران الأيسر)
3. منعرج الزاك (منعرج يتبعه منعرج)
4. Zag zig (زاج يليه منعرج)
5. منعرج منعرج (دورتان لليمين)
6. متعرج (دورتان لليسار)

العوامل المطلوبة لاختيار نوع التدوير

فيما يلي العوامل المستخدمة لاختيار نوع التدوير:

• هل العقدة التي نحاول تدويرها لها جد؟
• هل العقدة هي الطفل الأيسر أم الأيمن للوالد؟
• هل العقدة يسار أم يمين طفل الجد؟

حالات للدورات

حالة 1: إذا لم يكن للعقدة جد، وإذا كانت هي الابن الأيمن للوالد، فإننا نقوم بالتدوير الأيسر؛ وإلا، يتم تنفيذ التدوير الصحيح.

الحالة 2: إذا كانت العقدة لها جد، بناءً على السيناريوهات التالية؛ سيتم تنفيذ التدوير:

السيناريو 1: إذا كانت العقدة من حق الوالد وكان الوالد أيضًا من حق الوالد، إذن منعرج منعرج منعرج اليمين التناوب تم إنجازه.

السيناريو 2: إذا كانت العقدة على يسار أحد الوالدين، ولكن الوالد على يمين الوالد، إذن منعرج الزاك دوران اليمين واليسار تم إنجازه.

السيناريو 3: إذا كانت العقدة على حق الوالد والوالد على حق الوالد، إذن منعرج منعرج اليسار الدوران الأيسر تم إنجازه.

السيناريو 4: إذا كانت العقدة على يمين أحد الوالدين، ولكن الوالد على يسار الأصل، إذن دوران متعرج لليمين واليسار تم إنجازه.

الآن، دعونا نفهم التدويرات المذكورة أعلاه مع الأمثلة.

لإعادة ترتيب الشجرة، نحتاج إلى إجراء بعض الدورات. فيما يلي أنواع التدويرات في شجرة التباعد:

دورات منعرج

يتم استخدام التدويرات المتعرجة عندما يكون العنصر المطلوب البحث عنه إما عقدة جذر أو عقدة فرعية للعقدة الجذرية (أي العقدة الفرعية اليسرى أو اليمنى).

فيما يلي الحالات التي يمكن أن توجد في شجرة التباعد أثناء البحث:

حالة 1: إذا كان عنصر البحث عبارة عن عقدة جذر للشجرة.

الحالة 2: إذا كان عنصر البحث تابعًا للعقدة الجذرية، فسيكون السيناريوهين موجودين هناك:

1. إذا كان الطفل طفلًا يسارًا، فسيتم إجراء الدوران الأيمن، المعروف باسم الدوران المتعرج لليمين.
2. إذا كان الطفل طفلًا على اليمين، فسيتم إجراء الدوران الأيسر، المعروف باسم الدوران المتعرج لليسار.

دعونا نلقي نظرة على السيناريوهين أعلاه من خلال مثال.

خذ بعين الاعتبار المثال أدناه:

في المثال أعلاه، علينا البحث عن 7 عناصر في الشجرة. وسوف نتبع الخطوات التالية:

الخطوة 1: أولاً، نقارن 7 بالعقدة الجذرية. وبما أن 7 أقل من 10، فهو الابن الأيسر للعقدة الجذرية.

الخطوة 2: بمجرد العثور على العنصر، سنقوم بإجراء عملية التفلطح. يتم إجراء التدوير الصحيح بحيث يصبح الرقم 7 هو العقدة الجذرية للشجرة، كما هو موضح أدناه:

دعونا نفكر في مثال آخر.

في المثال أعلاه، علينا البحث عن 20 عنصرًا في الشجرة. وسوف نتبع الخطوات التالية:

الخطوة 1: أولاً، نقارن 20 بالعقدة الجذرية. وبما أن 20 أكبر من العقدة الجذرية، فهي الابن الأيمن للعقدة الجذرية.

الخطوة 2: بمجرد العثور على العنصر، سنقوم بإجراء عملية التفلطح. يتم تنفيذ التدوير الأيسر بحيث يصبح 20 عنصرًا العقدة الجذرية للشجرة.

تناوب منعرج منعرج

في بعض الأحيان ينشأ الموقف عندما يكون العنصر المطلوب البحث عنه له أحد الوالدين وكذلك الأجداد. في هذه الحالة، يتعين علينا إجراء أربع دورات للتباعد.

دعونا نفهم هذه الحالة من خلال مثال.

لنفترض أنه يتعين علينا البحث عن عنصر واحد في الشجرة، كما هو موضح أدناه:

الخطوة 1: أولاً، يتعين علينا إجراء عملية بحث BST قياسية للبحث في العنصر 1. نظرًا لأن 1 أقل من 10 و7، فسيكون على يسار العقدة 7. وبالتالي، فإن العنصر 1 له والد، أي 7، بالإضافة إلى جد، أي 10.

الخطوة 2: في هذه الخطوة، يتعين علينا إجراء التفلطح. نحن بحاجة إلى جعل العقدة 1 كعقدة جذر بمساعدة بعض التدويرات. في هذه الحالة، لا يمكننا ببساطة إجراء دوران متعرج أو متعرج؛ علينا أن ننفذ التناوب المتعرج.

من أجل جعل العقدة 1 كعقدة جذر، نحتاج إلى إجراء دورتين لليمين تعرفان بالدورات المتعرجة. عندما نقوم بالتدوير الصحيح فإن العقدة 10 ستتحرك للأسفل، والعقدة 7 ستتحرك للأعلى كما هو موضح في الشكل أدناه:

مرة أخرى، سنقوم بإجراء دوران متعرج لليمين، وستتحرك العقدة 7 للأسفل، وستتحرك العقدة 1 للأعلى كما هو موضح أدناه:

كما نلاحظ في الشكل أعلاه أن العقدة 1 أصبحت العقدة الجذرية للشجرة؛ وبذلك يكون قد اكتمل البحث.

لنفترض أننا نريد البحث عن 20 في الشجرة أدناه.

من أجل البحث عن 20، نحتاج إلى إجراء دورتين لليسار. فيما يلي الخطوات المطلوبة للبحث في 20 عقدة:

الخطوة 1: أولاً، نقوم بإجراء عملية البحث القياسية BST. وبما أن 20 أكبر من 10 و15، فسيكون على يمين العقدة 15.

الخطوة 2: الخطوة الثانية هي تنفيذ التفلطح. في هذه الحالة، سيتم تنفيذ دورتين لليسار. في الدورة الأولى، ستتحرك العقدة 10 إلى الأسفل، وستتحرك العقدة 15 إلى الأعلى كما هو موضح أدناه:

في الدوران الأيسر الثاني، ستتحرك العقدة 15 إلى الأسفل، وتصبح العقدة 20 هي العقدة الجذرية للشجرة، كما هو موضح أدناه:

كما لاحظنا أنه يتم تنفيذ دورتين لليسار؛ لذلك يُعرف بالتناوب المتعرج إلى اليسار.

دورات متعرجة

حتى الآن، قرأنا أن كلا من الوالدين والأجداد إما في علاقة RR أو LL. الآن، سوف نرى العلاقة RL أو LR بين الوالد والجد.

دعونا نفهم هذه الحالة من خلال مثال.

لنفترض أننا نريد البحث عن 13 عنصرًا في الشجرة الموضحة أدناه:

الخطوة 1: أولاً، نقوم بإجراء عملية بحث BST القياسية. بما أن 13 أكبر من 10 ولكن أقل من 15، فإن العقدة 13 ستكون الابن الأيسر للعقدة 15.

الخطوة 2: نظرًا لأن العقدة 13 تقع على يسار 15 والعقدة 15 تقع على يمين العقدة 10، فإن علاقة RL موجودة. أولاً، نقوم بإجراء التدوير الصحيح على العقدة 15، وستتحرك العقدة 15 للأسفل، وستتحرك العقدة 13 للأعلى، كما هو موضح أدناه:

ومع ذلك، فإن العقدة 13 ليست العقدة الجذرية، و13 تقع على يمين العقدة الجذرية، لذلك سنقوم بإجراء دوران لليسار يُعرف باسم الدوران المتعرج. ستتحرك العقدة 10 للأسفل، وستصبح 13 العقدة الجذرية كما هو موضح أدناه:

كما نلاحظ في الشجرة أعلاه أن العقدة 13 أصبحت العقدة الجذرية؛ وبذلك يكون قد اكتمل البحث. في هذه الحالة، قمنا أولاً بإجراء الدوران المتعرج ثم الدوران المتعرج؛ ولذلك، فإنه يعرف باسم دوران متعرج.

دوران متعرج متعرج

دعونا نفهم هذه الحالة من خلال مثال.

لنفترض أننا نريد البحث عن 9 عناصر في الشجرة، كما هو موضح أدناه:

الخطوة 1: أولاً، نقوم بإجراء عملية البحث القياسية BST. وبما أن 9 أقل من 10 ولكنه أكبر من 7، فسيكون الابن المناسب للعقدة 7.

الخطوة 2: نظرًا لأن العقدة 9 تقع على يمين العقدة 7، والعقدة 7 تقع على يسار العقدة 10، فإن علاقة LR موجودة. أولاً، نقوم بإجراء التدوير الأيسر على العقدة 7. ستتحرك العقدة 7 إلى الأسفل، وتتحرك العقدة 9 إلى الأعلى كما هو موضح أدناه:

لا تزال العقدة 9 ليست عقدة جذر، و9 تقع على يسار العقدة الجذرية، لذلك سنقوم بإجراء التدوير الأيمن المعروف باسم الدوران المتعرج. بعد إجراء التدوير الصحيح، تصبح العقدة 9 هي العقدة الجذرية، كما هو موضح أدناه:

كما يمكننا أن نلاحظ في الشجرة أعلاه أن العقدة 13 هي عقدة جذر؛ وبذلك يكون قد اكتمل البحث. في هذه الحالة، قمنا أولاً بإجراء الدوران المتعرج (الدوران الأيسر)، ومن ثم يتم إجراء الدوران المتعرج (الدوران الأيمن)، لذلك يُعرف بالدوران المتعرج (الدوران المتعرج).

مميزات شجرة السبلاي

• في شجرة التباعد، لا نحتاج إلى تخزين المعلومات الإضافية. في المقابل، في أشجار AVL، نحتاج إلى تخزين عامل التوازن لكل عقدة تتطلب مساحة إضافية، وتتطلب الأشجار ذات اللون الأحمر والأسود أيضًا تخزين بت إضافي واحد من المعلومات التي تشير إلى لون العقدة، إما باللون الأحمر أو الأسود.
• إنه أسرع نوع من شجرة البحث الثنائية لمختلف التطبيقات العملية. يتم استخدامه في المترجمين Windows NT وGCC .
• إنه يوفر أداءً أفضل حيث أن العقد التي يتم الوصول إليها بشكل متكرر ستقترب من العقدة الجذرية، مما يمكن من خلاله الوصول إلى العناصر بسرعة في الأشجار المتباعدة. يتم استخدامه في تنفيذ ذاكرة التخزين المؤقت حيث يتم تخزين البيانات التي تم الوصول إليها مؤخرًا في ذاكرة التخزين المؤقت بحيث لا نحتاج إلى الانتقال إلى الذاكرة للوصول إلى البيانات، ويستغرق الأمر وقتًا أقل.

عيب شجرة سبلاي

العيب الرئيسي لشجرة التباعد هو أن الأشجار ليست متوازنة بشكل صارم، أي أنها متوازنة تقريبًا. في بعض الأحيان تكون أشجار التباعد خطية، لذلك ستستغرق تعقيدًا زمنيًا O(n).

عملية الإدراج في شجرة Splay

في ال إدراج العملية، نقوم أولاً بإدراج العنصر في الشجرة ثم نقوم بإجراء عملية الترحيل على العنصر المدرج.

15، 10، 17، 7

الخطوة 1: أولاً، نقوم بإدراج العقدة 15 في الشجرة. بعد الإدراج، نحن بحاجة إلى أداء التفلطح. نظرًا لأن 15 هي عقدة جذر، فلا نحتاج إلى إجراء عملية التفلطح.

الخطوة 2: العنصر التالي هو 10. وبما أن 10 أقل من 15، فإن العقدة 10 ستكون الابن الأيسر للعقدة 15، كما هو موضح أدناه:

الآن، نحن نؤدي التفلطح . لجعل 10 بمثابة عقدة جذر، سنقوم بإجراء التدوير الصحيح، كما هو موضح أدناه:

الخطوه 3: العنصر التالي هو 17. وبما أن 17 أكبر من 10 و15، فسيصبح الابن الصحيح للعقدة 15.

الآن، سوف نقوم بإجراء التفلطح. نظرًا لأن الرقم 17 لديه أحد الوالدين بالإضافة إلى الجد، لذلك سنقوم بإجراء دورات متعرجة.

في الشكل أعلاه، يمكننا أن نلاحظ أن 17 يصبح العقدة الجذرية للشجرة؛ ولذلك، اكتمال الإدراج.

الخطوة 4: العنصر التالي هو 7. بما أن 7 أقل من 17 و15 و10، فستبقى العقدة 7 تابعة للرقم 10.

والآن علينا أن نقطع الشجرة. بما أن الرقم 7 هو وجود أحد الوالدين بالإضافة إلى الجد، لذلك سنقوم بإجراء دورتين لليمين كما هو موضح أدناه:

لا تزال العقدة 7 ليست عقدة جذر، فهي فرع يسار للعقدة الجذرية، أي 17. لذا، نحتاج إلى إجراء دوران آخر لليمين لجعل العقدة 7 كعقدة جذر كما هو موضح أدناه:

خوارزمية لعملية الإدراج

 Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n) 

في الخوارزمية المذكورة أعلاه، T هي الشجرة وn هي العقدة التي نريد إدراجها. لقد أنشأنا متغيرًا مؤقتًا يحتوي على عنوان العقدة الجذرية. سوف نقوم بتشغيل حلقة while حتى تصبح قيمة درجة الحرارة NULL.

بمجرد الانتهاء من الإدراج، سيتم تنفيذ التفلطح

خوارزمية لعملية Splaying

 Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y 

في التنفيذ أعلاه، x هي العقدة التي يتم إجراء التدوير عليها، في حين أن y هي الابن الأيسر للعقدة x.

تنفيذ دوران اليسار (T، x)

 left.rotation(T, x) y=x->right x->right = y->left y->left = x return y 

في التنفيذ أعلاه، x هي العقدة التي يتم إجراء التدوير عليها وy هي الابن الأيمن للعقدة x.

الحذف في شجرة Splay

كما نعلم أن أشجار التباعد هي متغيرات شجرة البحث الثنائية، لذا فإن عملية الحذف في شجرة التباعد ستكون مشابهة لعملية BST، ولكن الاختلاف الوحيد هو أن عملية الحذف تتبعها عملية الحذف في أشجار التباعد.

أنواع الحذف:

هناك نوعان من عمليات الحذف في أشجار التباعد:

1. التفلطح من الأسفل إلى الأعلى
2. التفلطح من أعلى إلى أسفل

التفلطح من الأسفل إلى الأعلى

في عملية الترحيل من أسفل إلى أعلى، نقوم أولاً بحذف العنصر من الشجرة ثم نقوم بإجراء عملية الترحيل على العقدة المحذوفة.

دعونا نفهم الحذف في شجرة Splay.

لنفترض أننا نريد حذف 12، 14 من الشجرة الموضحة أدناه:

حجم الثعبان

• أولاً، نقوم ببساطة بإجراء عملية حذف BST القياسية لحذف 12 عنصرًا. نظرًا لأن 12 عبارة عن عقدة ورقية، فإننا ببساطة نحذف العقدة من الشجرة.

عملية الحذف لم تكتمل بعد. نحن بحاجة إلى تباعد أصل العقدة المحذوفة، أي 10. علينا أن نؤديها سبلاي(10) على الشجرة. كما يمكننا أن نلاحظ في الشجرة أعلاه أن 10 تقع على يمين العقدة 7، والعقدة 7 تقع على يسار العقدة 13. لذلك، أولاً، نقوم بإجراء التدوير الأيسر على العقدة 7 ثم نقوم بإجراء التدوير الأيمن على العقدة 13 كما هو موضح أدناه:

ومع ذلك، العقدة 10 ليست عقدة جذر؛ العقدة 10 هي الابن الأيسر للعقدة الجذرية. لذلك، نحن بحاجة إلى إجراء التدوير الصحيح على العقدة الجذرية، أي 14 لجعل العقدة 10 عقدة جذر كما هو موضح أدناه:

• الآن علينا حذف العنصر 14 من الشجرة، كما هو موضح أدناه:

كما نعلم أنه لا يمكننا ببساطة حذف العقدة الداخلية. سوف نقوم باستبدال قيمة العقدة إما باستخدام سلف داخلي أو خليفة داخلي . لنفترض أننا نستخدم الخلف بالترتيب الذي نستبدل فيه القيمة بأقل قيمة موجودة في الشجرة الفرعية اليمنى. أدنى قيمة في الشجرة الفرعية اليمنى للعقدة 14 هي 15، لذلك نستبدل القيمة 14 بـ 15. وبما أن العقدة 14 تصبح العقدة الطرفية، فيمكننا حذفها ببساطة كما هو موضح أدناه:

ومع ذلك، لم يكتمل الحذف. نحن بحاجة إلى إجراء عملية أخرى، أي التقطيع حيث نحتاج إلى جعل أصل العقدة المحذوفة هو العقدة الجذرية. قبل الحذف، كانت العقدة الأصلية 14 هي العقدة الجذرية، أي 10، لذلك نحن بحاجة إلى إجراء أي فاصل في هذه الحالة.

التفلطح من أعلى إلى أسفل

في الترحيل من أعلى إلى أسفل، نقوم أولاً بإجراء الترحيل الذي سيتم إجراء الحذف عليه ثم نحذف العقدة من الشجرة. بمجرد حذف العنصر، سنقوم بإجراء عملية الانضمام.

دعونا نفهم التباعد من أعلى إلى أسفل من خلال مثال.

لنفترض أننا نريد حذف 16 من الشجرة الموضحة أدناه:

الخطوة 1: في عملية الترحيل من أعلى إلى أسفل، نقوم أولاً بإجراء عملية الترحيل على العقدة 16. تحتوي العقدة 16 على كلا من الأصل والجد. العقدة 16 تقع على يمين العقدة الأصلية وتقع العقدة الأصلية أيضًا على يمين العقدة الأم، لذا فهذه حالة متعرجة. في هذه الحالة، سنقوم أولاً بإجراء التدوير لليسار على العقدة 13 ثم 14 كما هو موضح أدناه:

لا تزال العقدة 16 ليست عقدة جذر، وهي فرع يمين للعقدة الجذرية، لذلك نحتاج إلى إجراء التدوير الأيسر على العقدة 12 لجعل العقدة 16 كعقدة جذر.

بمجرد أن تصبح العقدة 16 عقدة جذر، سنقوم بحذف العقدة 16 وسنحصل على شجرتين مختلفتين، أي الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى كما هو موضح أدناه:

كما نعلم أن قيم الشجرة الفرعية اليسرى تكون دائمًا أقل من قيم الشجرة الفرعية اليمنى. جذر الشجرة الفرعية اليسرى هو 12 وجذر الشجرة الفرعية اليمنى هو 17. الخطوة الأولى هي العثور على الحد الأقصى للعنصر في الشجرة الفرعية اليسرى. في الشجرة الفرعية اليسرى، الحد الأقصى للعنصر هو 15، ثم نحتاج إلى إجراء عملية تباعد على 15.

كما يمكننا أن نلاحظ في الشجرة أعلاه أن العنصر 15 له والد وجد. العقدة تقع على يمين العقدة الأصلية، والعقدة الأصلية أيضًا على يمين العقدة الأم، لذلك نحتاج إلى إجراء دورتين لليسار لجعل العقدة 15 عقدة جذر كما هو موضح أدناه:

بعد إجراء دورتين على الشجرة، تصبح العقدة 15 هي العقدة الجذرية. كما نرى، الابن الأيمن للرقم 15 هو NULL، لذلك نعلق العقدة 17 في الجزء الأيمن من الـ 15 كما هو موضح أدناه، وتعرف هذه العملية باسم ينضم عملية.

ملاحظة: إذا لم يكن العنصر موجودًا في شجرة التباعد، والذي سيتم حذفه، فسيتم إجراء التباعد. سيتم تنفيذ التفلطح على العنصر الأخير الذي تم الوصول إليه قبل الوصول إلى NULL.

خوارزمية عملية الحذف

 If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root 

في الخوارزمية المذكورة أعلاه، نتحقق أولاً مما إذا كان الجذر خاليًا أم لا؛ إذا كان الجذر NULL فهذا يعني أن الشجرة فارغة. إذا لم تكن الشجرة فارغة، فسنقوم بإجراء عملية الترحيل على العنصر الذي سيتم حذفه. بمجرد اكتمال عملية الترحيل، سنقوم بمقارنة بيانات الجذر مع العنصر الذي سيتم حذفه؛ إذا لم يكن كلاهما متساويين فهذا يعني أن العنصر غير موجود في الشجرة. وإذا كانا متساويين فمن الممكن أن تحدث الحالات التالية:

حالة 1 : يسار الجذر فارغ، ويمين الجذر يصبح العقدة الجذرية.

الحالة 2 : في حالة وجود كل من اليسار واليمين، فإننا نوزع الحد الأقصى للعنصر في الشجرة الفرعية اليسرى. عند اكتمال التدرج، يصبح الحد الأقصى للعنصر هو جذر الشجرة الفرعية اليسرى. ستصبح الشجرة الفرعية اليمنى الابن الأيمن لجذر الشجرة الفرعية اليسرى.