شجرة AA

شجرة AA في علوم الحاسوب هي شكل من أشكال الأشجار المتوازنة تُستخدم لتخزين واسترجاع البيانات المرتبة بكفاءة. سُميت أشجار AA نسبةً إلى مبتكرها، عالم الحاسوب السويدي آرني أندرسون . ^{[ 1 ]}

أشجار AA هي نوع من أنواع أشجار البحث الثنائية الحمراء والسوداء ، والتي تتميز بسهولة إضافة وحذف العناصر. على عكس أشجار البحث الثنائية الحمراء والسوداء، لا يمكن إضافة العقد الحمراء في شجرة AA إلا كفرع فرعي أيمن. بمعنى آخر، لا يمكن أن تكون أي عقدة حمراء فرعًا فرعيًا أيسر. ينتج عن ذلك محاكاة شجرة 2-3 بدلًا من شجرة 2-3-4 ، مما يُبسط عمليات الصيانة بشكل كبير. تتطلب خوارزميات صيانة شجرة البحث الثنائية الحمراء والسوداء مراعاة سبعة أشكال مختلفة لتحقيق التوازن الأمثل للشجرة.

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

بينما تتطلب أشجار الأحمر والأسود بتًا واحدًا من بيانات التوازن الوصفية لكل عقدة (اللون)، تتطلب أشجار AA بتًا واحدًا من البيانات الوصفية لكل عقدة، على شكل "مستوى" عددي صحيح، وهو O(log(log(N))). تنطبق الثوابت التالية على أشجار AA:

1. مستوى كل عقدة طرفية هو واحد.
2. مستوى كل طفل أيسر أقل بواحد بالضبط من مستوى والده.
3. مستوى كل طفل من الأطفال ذوي الحقوق يساوي أو يقل بواحد عن مستوى أحد والديه.
4. مستوى كل حفيد من الأحفاد أقل بكثير من مستوى جده أو جدته.
5. كل عقدة من المستوى الأكبر من واحد لها طفلان.

يُطلق على الرابط الذي يتساوى فيه مستوى الابن مع مستوى والده اسم الرابط الأفقي ، وهو يُشابه الرابط الأحمر في شجرة الأحمر والأسود. يُسمح بوجود روابط أفقية يمينية منفردة، بينما تُمنع الروابط المتتالية؛ كما تُمنع جميع الروابط الأفقية اليسارية. تُعد هذه القيود أكثر صرامة من القيود المماثلة في أشجار الأحمر والأسود، مما يجعل إعادة توازن شجرة AA أسهل بكثير من الناحية الإجرائية من إعادة توازن شجرة الأحمر والأسود.

قد تؤدي عمليات الإضافة والحذف مؤقتًا إلى اختلال توازن شجرة AA (أي انتهاك ثوابت شجرة AA). ولا يتطلب استعادة التوازن سوى عمليتين منفصلتين: "التعديل" و"التقسيم". التعديل هو تدوير لليمين لاستبدال شجرة فرعية تحتوي على رابط أفقي يساري بأخرى تحتوي على رابط أفقي يميني. أما التقسيم فهو تدوير لليسار مع زيادة في المستوى لاستبدال شجرة فرعية تحتوي على رابطين أفقيين يمينيين متتاليين أو أكثر بأخرى تحتوي على رابطين أفقيين يمينيين متتاليين أقل. يتم تبسيط تنفيذ عمليات الإضافة والحذف التي تحافظ على التوازن بالاعتماد على عمليتي التعديل والتقسيم لتعديل الشجرة عند الحاجة فقط، بدلًا من جعل الدوال المستدعِية تُقرر ما إذا كانت ستُعدِّل الشجرة أم تُقسِّمها.

الدالة skew تأخذ المدخلات التالية: T، وهي عقدة تمثل شجرة AA تحتاج إلى إعادة توازن. المخرجات: عقدة أخرى تمثل شجرة AA المعاد توازنها. إذا كانت قيمة T فارغة ، فأرجع Nil ، وإذا كانت قيمة left(T) فارغة ، فأرجع T ، وإذا كانت قيمة level(left(T)) تساوي قيمة level(T)، فقم بتبديل مؤشرات الروابط الأفقية اليسرى. L = left(T) left(T) := right(L) يمين(يسار) := T أرجع L وإلا أرجع T نهاية الشرط نهاية الدالة

الانحراف:

تستقبل الدالة split المدخلات التالية: T، وهي عقدة تمثل شجرة AA تحتاج إلى إعادة توازن. وتستقبل المخرجات التالية: عقدة أخرى تمثل شجرة AA المعاد توازنها. إذا كانت قيمة T فارغة، فأرجع قيمة فارغة . وإذا كانت قيمة right(T) فارغة أو قيمة right(right(T)) فارغة ، فأرجع قيمة T. وإذا كان مستوى T يساوي مستوى right(right(T))، فسنحصل على رابطين أفقيين إلى اليمين. خذ العقدة الوسطى، وارفعها، ثم أرجعها. R = right(T) right(T) := left(R) left(R) := T level(R) := level(R) + 1 أرجع R وإلا أرجع T نهاية الشرط نهاية الدالة

ينقسم:

تبدأ عملية الإضافة بإجراء البحث والإضافة المعتاد في الشجرة الثنائية. بعد ذلك، ومع امتداد سلسلة الاستدعاءات (بافتراض تنفيذ البحث بشكل تكراري)، يسهل التحقق من صحة الشجرة وإجراء أي تدويرات ضرورية. في حال ظهور رابط أفقي يساري، يتم إجراء تعديل على الشجرة، وفي حال ظهور رابطين أفقيين يمينيين، يتم إجراء تقسيم، مع إمكانية زيادة مستوى العقدة الجذرية الجديدة للشجرة الفرعية الحالية. لاحظ في الكود المذكور أعلاه زيادة مستوى الشجرة (T). هذا يجعل من الضروري الاستمرار في التحقق من صحة الشجرة مع انتقال التعديلات من الأوراق.

تستقبل الدالة insert المدخلات التالية : X، القيمة المراد إدراجها، وT، جذر الشجرة المراد إدراجها فيه. وتخرج الدالة نسخة متوازنة من T تتضمن X. نفّذ إجراء إدراج الشجرة الثنائية المعتاد. عيّن نتيجة الاستدعاء التكراري إلى الابن الصحيح في حالة إنشاء عقدة جديدة أو تغيير جذر الشجرة الفرعية. إذا كانت قيمة T تساوي صفرًا، فأنشئ عقدة ورقة جديدة بالقيمة X. أرجع العقدة (X، 1، Nil، Nil). وإلا، إذا كانت X أقل من قيمة T، left(T) := insert(X, left(T)) وإلا إذا كانت قيمة X أكبر من قيمة T، right(T) := insert(X, right(T)) نهاية الشرط. لاحظ أن حالة X == قيمة(T) غير محددة. كما هو معلوم، لن يكون للإدراج أي تأثير. قد يرغب المطور في سلوك مختلف.قم بإجراء عملية الإمالة ثم التقسيم. توجد الشروط التي تحدد ما إذا كان سيحدث دوران أم لا داخل الإجراءات، كما هو موضح أعلاه. T := skew(T) T := split(T) إرجاع T نهاية الدالة

كما هو الحال في معظم الأشجار الثنائية المتوازنة، يمكن تحويل حذف عقدة داخلية إلى حذف عقدة طرفية عن طريق استبدالها بأقرب عقدة سابقة أو لاحقة لها، وذلك حسب موقعها في الشجرة أو حسب رغبة المطور. واستعادة العقدة السابقة تتم ببساطة عن طريق اتباع رابط واحد إلى اليسار ثم جميع الروابط المتبقية إلى اليمين. وبالمثل، يمكن العثور على العقدة اللاحقة بالتحرك يمينًا مرة واحدة ثم يسارًا حتى الوصول إلى مؤشر فارغ. ونظرًا لخاصية AA التي تنص على أن جميع العقد من المستوى الأعلى من واحد لها عقدتان فرعيتان، فإن العقدة اللاحقة أو السابقة ستكون في المستوى 1، مما يجعل إزالتها أمرًا بسيطًا.

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

1. قم بتخفيض المستوى، إذا كان ذلك مناسبًا.
2. قم بتحريف المستوى.
3. قسّم المستوى.

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

تستقبل الدالة delete المدخلات التالية: X، القيمة المراد حذفها، وT، جذر الشجرة التي يجب حذفها منها. وتُخرج الدالة T، وهي الشجرة المتوازنة، بدون القيمة X. إذا كانت قيمة T تساوي صفرًا، إرجاع T وإلا إذا كانت قيمة X أكبر من قيمة T، right(T) := delete(X, right(T)) وإلا إذا كانت قيمة X أقل من قيمة T، left(T) := delete(X, left(T)) وإلا، إذا كنا ورقة، فالأمر سهل، وإلا نختزل إلى حالة الورقة. إذا كانت ورقة(T) أعد اليمين(T) وإلا إذا كانت قيمة `Live(T)` تساوي `nil`، فـ L := successor(T) right(T) := delete(value(L), right(T)) قيمة(T) := قيمة(L) آخر L := سلف(T) left(T) := delete(value(L), left(T)) قيمة(T) := قيمة(L) نهاية الشرط نهاية الشرطأعد توازن الشجرة. قلل مستوى جميع العقد في هذا المستوى إذا لزم الأمر، ثم قم بتعديل وتقسيم جميع العقد في المستوى الجديد. T := reduction_level(T) T := skew(T) right(T) := skew(right(T)) إذا لم يكن يمين(T) فارغًا right(right(T)) := skew(right(right(T))) نهاية الشرط T := split(T) right(T) := split(right(T)) إرجاع T نهاية الدالة

الدالة reduce_level تأخذ المدخلات التالية: T، وهي شجرة نريد إزالة الروابط التي تتجاوز مستويات منها. وتخرج الدالة T بعد خفض مستواها. should_be = min(level(left(T)), level(right(T))) + 1 إذا كان يجب أن يكون < مستوى(T) المستوى(T) := يجب أن يكون إذا كان يجب أن يكون < مستوى(يمين(T)) المستوى(يمين(T)) := يجب_أن_يكون نهاية الشرط نهاية الشرط إرجاع T نهاية الدالة

يوجد مثال جيد على الحذف بواسطة هذه الخوارزمية في ورقة أندرسون .

يُعادل أداء شجرة AA أداء شجرة الأحمر والأسود. ورغم أن شجرة AA تُجري عمليات تدوير أكثر من شجرة الأحمر والأسود، إلا أن الخوارزميات الأبسط تميل إلى أن تكون أسرع، ويتوازن كل ذلك ليُؤدي إلى أداء مُتقارب. تتميز شجرة الأحمر والأسود بأداء أكثر اتساقًا من شجرة AA، لكن شجرة AA تميل إلى أن تكون أكثر تسطحًا، مما يُؤدي إلى أوقات بحث أسرع قليلًا. ^{[ 2 ]}

• شجرة حمراء سوداء
• شجرة B
• شجرة AVL
• شجرة كبش الفداء