التحويل والحل (Transform-and-Conquer)
تغطي هذه الوحدة استراتيجية التحويل والحل في تصميم الخوارزميات، بما في ذلك الفرز المسبق، الحذف الغاوسي، وأشجار البحث المتوازنة (AVL).
Transform-and-Conquer
This module covers the Transform-and-Conquer algorithm design strategy, including presorting, Gaussian Elimination, and Balanced Search Trees (AVL).
أهداف التعلم
- وصف استراتيجية التحويل والحل (Transform-and-Conquer) وأنواعها المختلفة.
- التعبير عن الفرز المسبق (Presorting) وعملية الحذف الغاوسي (Gaussian Elimination).
- التعرف على أشجار البحث المتوازنة (AVL) وخصائصها.
- Describe Transform-and-Conquer and their various types.
- Express the presorting and Gaussian Elimination.
- Recognize Balanced Search Trees (AVL) tree & its properties.
1 استراتيجية التحويل والحل
1 Transform-and-Conquer Strategy
تقنية تعتمد على تحويل المشكلة إلى شكل أسهل قبل حلها، مثل ترتيب الأوراق قبل البحث عن اسم معين.
A technique based on transforming a problem into an easier-to-solve instance before conquering it.
تعمل هذه الاستراتيجية كإجراء من مرحلتين: المرحلة الأولى (التحويل): يتم تعديل نسخة المشكلة لتصبح أكثر قابلية للحل. المرحلة الثانية (الحل): يتم حل المشكلة في شكلها الجديد.
هناك ثلاثة أنواع رئيسية:
- تبسيط النسخة (Instance Simplification) مثل الفرز المسبق.
- تغيير التمثيل (Representation Change) مثل استخدام هياكل بيانات مختلفة كأشجار AVL.
- اختزال المشكلة (Problem Reduction) بتحويلها لمشكلة يوجد لها خوارزمية جاهزة.
This strategy works as a two-stage procedure: First Stage (Transformation): the problem's instance is modified to be more amenable to a solution. Second Stage (Conquering): the problem is solved.
There are three main variations:
- Instance Simplification (e.g., presorting).
- Representation Change (e.g., using a different data structure like AVL trees).
- Problem Reduction (transforming into a different problem for which an algorithm is already available).
تكمن قوة هذه الاستراتيجية في أن تكلفة التحويل (مثل الفرز في وقت O(n log n)) غالباً ما يتم تعويضها بشكل كبير من خلال التخفيض الهائل في وقت مرحلة الحل (مثلاً من O(n^2) إلى O(n)).
هذا يغير عنق الزجاجة في الأداء من المشكلة الأصلية إلى عملية التحويل نفسها.
The power of this strategy lies in the fact that the cost of transformation (e.g., sorting in O(n log n) time) is often heavily outweighed by the massive reduction in the conquering stage's time (e.g., from O(n^2) to O(n)).
This shifts the performance bottleneck from the original problem to the transformation process itself.
لماذا لا نستخدم التحويل والحل في جميع المشاكل الخوارزمية؟ Why don't we use Transform-and-Conquer for all algorithmic problems?
لأن تكلفة مرحلة التحويل (مثل الفرز) قد تكون أعلى من تكلفة حل المشكلة مباشرة بالطرق التقليدية في بعض الحالات.
Because the cost of the transformation stage (like sorting) might be higher than solving the problem directly using traditional methods in some cases.
2 الفرز المسبق (Presorting)
2 Presorting
ترتيب البيانات أولاً لجعل العمليات اللاحقة (مثل البحث أو إيجاد العناصر المكررة) أسرع بكثير.
Sorting data first to make subsequent operations (like searching or finding duplicates) much faster.
الفرز المسبق هو تطبيق لمبدأ 'تبسيط النسخة'. العديد من المشاكل التي تتضمن قوائم تصبح أسهل إذا كانت القائمة مرتبة.
أمثلة:
- البحث: فرز ثم بحث ثنائي بكفاءة O(n log n).
- تفرد العناصر (Element Uniqueness): بدلاً من مقارنة كل زوج بكفاءة O(n^2)، نقوم بالفرز O(n log n) ثم فحص العناصر المتجاورة O(n)، لتصبح الكفاءة الكلية O(n log n).
Presorting is an application of 'Instance Simplification'. Many problems involving lists are easier when the list is sorted.
Examples:
- Searching: Sort then apply binary search with efficiency O(n log n).
- Element Uniqueness: Instead of brute-force comparing all pairs in O(n^2), we sort in O(n log n) and scan adjacent elements in O(n), yielding an overall efficiency of O(n log n).
كفاءة الخوارزميات التي تعتمد على الفرز المسبق تعتمد بشكل أساسي على كفاءة خوارزمية الفرز نفسها.
تنص النظرية على أن أي خوارزمية فرز تعتمد على المقارنة تتطلب على الأقل n log_2 n مقارنات في أسوأ حالة.
لذلك، الفرز المسبق مفيد فقط إذا كانت المشكلة الأصلية تتطلب وقتاً أسوأ من O(n log n).
The efficiency of algorithms involving presorting depends heavily on the sorting algorithm's efficiency.
A theorem states that any comparison-based sorting algorithm requires at least n log_2 n comparisons in the worst case.
Thus, presorting is only beneficial if the original problem takes worse than O(n log n) time to solve directly.
ALGORITHM PresortElementUniqueness(A[0..n-1])
// Sorts the array first, then checks for uniqueness
sort the array A
for i <- 0 to n - 2 do
if A[i] == A[i + 1] return false
return true| Brute Force | Presorting | |
|---|---|---|
| الكفاءة الزمنيةTime Efficiency | O(n^2)O(n^2) | O(n log n)O(n log n) |
| النهجApproach | مقارنة كل زوج من العناصرCompare all pairs of elements | الفرز أولاً ثم فحص العناصر المتجاورةSort first, then scan adjacent elements |
هل هناك طريقة أسرع من الفرز المسبق لحل مشكلة تفرد العناصر؟ Is there a faster way than presorting to solve the Element Uniqueness problem?
نعم، باستخدام التجزئة (Hashing) يمكن تحقيق كفاءة متوسطة تقارب O(n)، رغم أن أسوأ حالة قد تكون أسوأ.
Yes, using Hashing can achieve an average-case efficiency of O(n), though the worst-case might be worse.
3 الحذف الغاوسي (Gaussian Elimination)
3 Gaussian Elimination
تحويل نظام من المعادلات الخطية المعقدة إلى مصفوفة مثلثية عليا يسهل حلها من الأسفل للأعلى.
Transforming a complex system of linear equations into an upper triangular matrix that is easy to solve from bottom to top.
الحذف الغاوسي هو مثال على 'تبسيط النسخة'.
لحل نظام من n معادلة خطية، نقوم بتحويل مصفوفة المعاملات إلى نظام مكافئ بمصفوفة مثلثية عليا (المرحلة 1: الحذف الأمامي).
بعد ذلك، نقوم بحل النظام باستخدام التعويض العكسي (المرحلة 2: Back substitution) بدءاً من المعادلة الأخيرة صعوداً إلى الأولى.
Gaussian Elimination is an example of 'Instance Simplification'.
To solve a system of n linear equations, we transform the coefficient matrix into an equivalent system with an upper triangular matrix (Stage 1: Forward Elimination).
Then, we solve the system using back substitution (Stage 2) starting from the last equation and moving up to the first.
الكفاءة الزمنية للحذف الغاوسي يهيمن عليها مرحلة الحذف الأمامي التي تحتوي على ثلاث حلقات متداخلة، مما يعطي كفاءة O(n^3).
مرحلة التعويض العكسي تتطلب حلقتين متداخلتين بكفاءة O(n^2).
الكفاءة الإجمالية هي O(n^3).
The time efficiency of Gaussian Elimination is dominated by the forward elimination stage, which has three nested loops, yielding O(n^3) efficiency.
The back substitution stage requires two nested loops, yielding O(n^2).
The overall efficiency is O(n^3).
// Stage 1: Reduction to upper-triangular matrix
for i <- 1 to n-1 do
for j <- i+1 to n do
for k <- i to n+1 do
A[j, k] <- A[j, k] - A[i, k] * A[j, i] / A[i, i]
// Stage 2: Back substitutions
for j <- n down to 1 do
t <- 0
for k <- j+1 to n do
t <- t + A[j, k] * x[k]
x[j] <- (A[j, n+1] - t) / A[j, j]لماذا تعتبر مرحلة التعويض العكسي أسرع بكثير من مرحلة الحذف الأمامي؟ Why is the back substitution stage much faster than the forward elimination stage?
لأن التعويض العكسي يتطلب فقط حساب قيمة متغير واحد في كل خطوة باستخدام القيم المحسوبة مسبقاً (حلقتين متداخلتين O(n^2))، بينما الحذف الأمامي يتطلب تحديث صفوف كاملة في المصفوفة (ثلاث حلقات متداخلة O(n^3)).
Because back substitution only requires calculating one variable per step using previously computed values (two nested loops O(n^2)), while forward elimination requires updating entire rows in the matrix (three nested loops O(n^3)).
4 أشجار البحث الثنائية (BST)
4 Binary Search Trees (BST)
شجرة يكون فيها كل عقدة يسارية أصغر من الجذر، وكل عقدة يمينية أكبر منه، لتسهيل البحث.
A tree where every left child is smaller than the parent, and every right child is larger, facilitating fast search.
شجرة البحث الثنائية ترتب المفاتيح بحيث تحقق 'خاصية شجرة البحث الثنائية'.
تدعم عمليات القاموس: البحث (مباشر)، الإدراج (البحث عن المفتاح وإدراجه كعقدة ورقية)، والحذف (3 حالات: ورقة، عقدة بطفل واحد، عقدة بطفلين).
تعتمد كفاءة هذه العمليات على ارتفاع الشجرة h، حيث log_2(n) <= h <= n-1.
A Binary Search Tree arranges keys to satisfy the 'binary search tree property'.
It supports dictionary operations: Search (straightforward), Insertion (search for key, insert at leaf), and Deletion (3 cases: leaf, node with one child, node with two children).
Efficiency depends on the tree's height h, where log_2(n) <= h <= n-1.
المشكلة الرئيسية في BST هي أن أسوأ حالة للكفاءة هي O(n) عندما تكون الشجرة غير متوازنة (مثلاً عند إدراج عناصر مرتبة مسبقاً، فتتحول الشجرة إلى قائمة مرتبطة).
متوسط الكفاءة للملفات العشوائية هو O(log n).
هذا العيب أدى إلى ابتكار أشجار البحث المتوازنة مثل AVL.
The main flaw of a standard BST is that its worst-case efficiency is O(n) when the tree becomes unbalanced (e.g., inserting already sorted elements turns it into a linked list).
The average case for random files is O(log n).
This linear worst-case efficiency necessitated the invention of balanced search trees like AVL.
ماذا يحدث إذا قمنا بإدراج الأرقام 1، 2، 3، 4، 5 بالترتيب في شجرة بحث ثنائية فارغة؟ What happens if we insert the numbers 1, 2, 3, 4, 5 in order into an empty BST?
ستصبح الشجرة غير متوازنة تماماً (منحرفة لليمين) وتشبه القائمة المرتبطة، مما يجعل وقت البحث O(n).
The tree will become completely unbalanced (right-skewed) and resemble a linked list, making search time O(n).
5 أشجار AVL (AVL Trees)
5 AVL Trees
شجرة بحث ثنائية ذاتية التوازن تضمن ألا يزيد فرق الارتفاع بين الفرع الأيمن والأيسر لأي عقدة عن 1.
A self-balancing BST that ensures the height difference between the left and right subtrees of any node is at most 1.
شجرة AVL هي شجرة بحث ثنائية حيث يكون 'عامل التوازن' (Balance Factor) لكل عقدة هو إما -1، 0، أو 1.
عامل التوازن يُحسب كـ (ارتفاع الشجرة الفرعية اليسرى - ارتفاع الشجرة الفرعية اليمنى). ارتفاع الشجرة الفارغة يُعرّف بأنه -1.
هذا التوازن الصارم يضمن أن عمليات البحث والإدراج والحذف تتم في وقت O(log n) في أسوأ الحالات.
An AVL tree is a BST in which the 'balance factor' for every node is either -1, 0, or 1.
The balance factor is calculated as (height of left subtree - height of right subtree). The height of an empty tree is defined as -1.
This strict balancing guarantees that search, insertion, and deletion operations take O(log n) time in the worst case.
للحفاظ على هذا التوازن، تقوم شجرة AVL بإعادة هيكلة نفسها باستخدام 'الدورانات' (Rotations) كلما أدى إدراج أو حذف إلى الإخلال بعامل التوازن.
العيب الرئيسي لأشجار AVL هو كثرة الدورانات المطلوبة والتعقيد البرمجي، مما يجعل أشجار Red-Black (التي تسمح باختلاف الارتفاع حتى الضعف) مفضلة في بعض التطبيقات العملية.
To maintain this balance, an AVL tree restructures itself using 'rotations' whenever an insertion or deletion violates the balance factor.
The main disadvantage of AVL trees is the frequency of rotations and implementation complexity, which makes Red-Black trees (allowing height differences up to a factor of 2) preferable in some practical applications.
| Standard BST | AVL Tree | |
|---|---|---|
| كفاءة البحث في أسوأ حالةWorst-case Search Efficiency | O(n)O(n) | O(log n)O(log n) |
| التوازنBalancing | غير مضمون (قد تصبح كقائمة مرتبطة)Not guaranteed (can become skewed) | مضمون بصرامة (فرق الارتفاع <= 1)Strictly guaranteed (height diff <= 1) |
| تعقيد الإدراج/الحذفInsertion/Deletion Complexity | بسيطSimple | معقد (يتطلب دورانات متكررة)Complex (requires frequent rotations) |
لماذا نعرّف ارتفاع الشجرة الفارغة بأنه -1 في سياق أشجار AVL؟ Why do we define the height of an empty tree as -1 in the context of AVL trees?
لجعل الحسابات الرياضية لعامل التوازن متسقة. فعقدة الورقة (Leaf) لها أشجار فرعية فارغة، وإذا كان ارتفاعها -1، فإن ارتفاع الورقة يصبح max(-1, -1) + 1 = 0.
To make the mathematical calculations of the balance factor consistent. A leaf node has empty subtrees; if their height is -1, the leaf's height becomes max(-1, -1) + 1 = 0.
6 دورانات شجرة AVL
6 AVL Tree Rotations
حركات هيكلية (يمين، يسار، أو مزدوجة) تُستخدم لإصلاح الخلل في توازن شجرة AVL بعد إضافة عنصر جديد.
Structural movements (Right, Left, or Double) used to fix the balance of an AVL tree after a new element is added.
إذا أدى إدراج مفتاح إلى الإخلال بشرط التوازن، يتم تحويل الشجرة الفرعية باستخدام أحد الدورانات الأربعة:
- دوران أحادي لليمين (R-rotation): يُنفذ عند الإدراج في الشجرة الفرعية اليسرى للابن الأيسر.
- دوران أحادي لليسار (L-rotation): يُنفذ عند الإدراج في الشجرة الفرعية اليمنى للابن الأيمن.
- دوران مزدوج يسار-يمين (LR-rotation): يُنفذ عند الإدراج في الشجرة الفرعية اليمنى للابن الأيسر.
- دوران مزدوج يمين-يسار (RL-rotation): يُنفذ عند الإدراج في الشجرة الفرعية اليسرى للابن الأيمن.
If a key insertion violates the balance requirement, the subtree is transformed via one of four rotations:
- Single Right (R-rotation): Performed after insertion into the left subtree of the left child.
- Single Left (L-rotation): Performed after insertion into the right subtree of the right child.
- Double Left-Right (LR-rotation): Performed after insertion into the right subtree of the left child.
- Double Right-Left (RL-rotation): Performed after insertion into the left subtree of the right child.
الدوران يُنفذ دائماً على الشجرة الفرعية التي جذرها هو العقدة 'غير المتوازنة' الأقرب إلى الورقة الجديدة المضافة.
الدورانات المزدوجة هي ببساطة مزيج من دورانين أحاديين متتاليين.
هذه العمليات تتم في وقت ثابت O(1) لأنها تتطلب فقط إعادة توجيه عدد قليل من المؤشرات (Pointers).
The rotation is always performed for a subtree rooted at an 'unbalanced' node closest to the new leaf.
Double rotations are simply a combination of two consecutive single rotations.
These operations take O(1) constant time because they only involve reassigning a few pointers.
لماذا لا يكفي الدوران الأحادي (R-rotation) لحل مشكلة الإدراج في الشجرة الفرعية اليمنى للابن الأيسر؟ Why is a single R-rotation not enough to fix an insertion into the right subtree of the left child?
لأن الدوران الأحادي لليمين في هذه الحالة لن يحل مشكلة الارتفاع الزائد في المنتصف، بل سينقله فقط إلى الجهة الأخرى. لذلك نحتاج لدوران لليسار أولاً لتبسيط الشكل، ثم دوران لليمين.
Because a single right rotation in this case won't resolve the excess height in the middle; it will just shift it to the other side. Thus, we need a left rotation first to straighten the path, followed by a right rotation.