شجرة AVL

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

سُميت شجرة AVL نسبةً إلى مخترعيها السوفيتيين ، جورجي أديلسون-فيلسكي وإيفجيني لانديس ، اللذين نشراها في بحثهما عام 1962 بعنوان "خوارزمية لتنظيم المعلومات". ^{[ 2 ]} وهي أول بنية بيانات لشجرة بحث ثنائية ذاتية التوازن يتم ابتكارها. ^{[ 3 ]}

غالبًا ما تتم مقارنة أشجار AVL بأشجار الأحمر والأسود لأن كليهما يدعم نفس مجموعة العمليات ويأخذ ${\text{O}}(\log n)$ يستغرق الأمر وقتًا أطول لإجراء العمليات الأساسية. بالنسبة للتطبيقات التي تتطلب عمليات بحث مكثفة، تُعد أشجار AVL أسرع من أشجار الأحمر والأسود لأنها أكثر توازنًا. ^{[ 4 ]} على غرار أشجار الأحمر والأسود، فإن أشجار AVL متوازنة الارتفاع. وكلاهما، بشكل عام، ليسا متوازنين من حيث الوزن ولا $\mu$ متوازن لأي $\mu \leq {\tfrac {1}{2}}$ ; ^{[ 5 ]} أي أن العقد الشقيقة يمكن أن يكون لها أعداد مختلفة بشكل كبير من النسل.

تعريف

عامل التوازن

في الشجرة الثنائية، يُعرَّف عامل التوازن للعقدة X بأنه فرق الارتفاع

\mathrm {BF} (X):=\mathrm {الارتفاع} (\mathrm {RightSubtree} (X))-\mathrm {الارتفاع} (\mathrm {LeftSubtree} (X))

^{[ 6 ]}^{: 459}

من شجرتيها الفرعيتين المتفرعتين من العقدة X.

تُعرَّف الشجرة الثنائية بأنها شجرة AVL إذا

\mathrm {BF} (X)\in \{-1,0,1\}

ينطبق هذا على كل عقدة X في الشجرة.

عقدة X مع $\mathrm {BF} (X)<0$ يُطلق عليه اسم "ذو ثقل يساري"، وهو ذو $\mathrm {BF} (X)>0$ يُطلق عليه اسم "ثقيل اليمين"، وهو واحد مع $\mathrm {BF} (X)=0$ يُطلق عليه أحيانًا ببساطة اسم "متوازن".

ملكيات

يمكن تحديث عوامل التوازن بمعرفة عوامل التوازن السابقة والتغير في الارتفاع - ليس من الضروري معرفة الارتفاع المطلق. يكفي استخدام بتّين لكل عقدة لتخزين معلومات توازن AVL. ^{[ 7 ]}

الارتفاع $h$ (يُحتسب كأقصى عدد من المستويات) لشجرة AVL مع $n$ تقع العقدة في الفترة: ^{[ 6 ]}^{: 460}

\log _{2}(n+1)\leq h<\log _{\varphi }(n+2)+b

أين ${\displaystyle \varphi$ النسبة الذهبية هي: $...$ $b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\approx \;-0.3277.$ وذلك لأن شجرة AVL ذات ارتفاع $h$ يحتوي على الأقل $F_{h+2}-1$ العقد حيث $\{F_{n}\}_{n\in \mathbb {N} }$ هي متتالية فيبوناتشي ذات القيم الأولية $F_{1}=F_{2}=1.$

العمليات

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

البحث

يمكن البحث عن مفتاح محدد في شجرة AVL بنفس طريقة البحث في أي شجرة بحث ثنائية متوازنة أو غير متوازنة . ^{[ 8 ]}^{: الفصل 8.} لكي يعمل البحث بفعالية، يجب أن يستخدم دالة مقارنة تُنشئ ترتيبًا كليًا (أو على الأقل ترتيبًا جزئيًا كليًا ) على مجموعة المفاتيح. ^{[ 9 ]}^{: 23.} عدد المقارنات المطلوبة للبحث الناجح محدود بالارتفاع $h$ ، أما للبحث غير الناجح فهو قريب جدًا من $h$ ، لذا فإن كلا الحالتين من رتبة $O(log n)$ ، حيث n هو عدد العقد في الشجرة. ^{[ 10 ]}^{: 216}

اجتياز

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

بمجرد العثور على عقدة في شجرة AVL، يمكن الوصول إلى العقدة التالية أو السابقة في وقت ثابت مُعدَّل . ^{[ 11 ]}^{: 58} تتطلب بعض حالات استكشاف هذه العقد "القريبة" اجتياز ما يصل إلى $h \propto log(n)$ من الروابط (خاصةً عند الانتقال من أقصى يمين الشجرة الفرعية اليسرى للجذر إلى الجذر، أو من الجذر إلى أقصى يسار الشجرة الفرعية اليمنى للجذر؛ في شجرة AVL الموضحة في الشكل 1، يستغرق الانتقال من العقدة P إلى العقدة Q المجاورة لها يمينًا 3 خطوات). بما أن هناك $n - 1$ رابطًا في أي شجرة، فإن التكلفة المُعدَّلة هي $2 \times (n - 1) / n$ ، أو ما يقارب 2.

أدخل

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

بعد هذا الإدخال، إذا أصبحت الشجرة غير متوازنة، فإن أسلاف العقدة المُدخلة حديثًا فقط هي التي تصبح غير متوازنة. وذلك لأن هذه العقد فقط هي التي تتغير أشجارها الفرعية. ^{[ 12 ]} لذا، من الضروري التحقق من كل سلف من أسلاف العقدة للتأكد من توافقه مع ثوابت أشجار AVL: وهذا ما يُسمى "إعادة التتبع". ويتم ذلك من خلال النظر في عامل التوازن لكل عقدة. ^{[ 6 ]}^{: 458-481}^{[ 11 ]}^{: 108}

بما أن ارتفاع شجرة AVL الفرعية لا يمكن أن يزيد بأكثر من واحد عند إدخال عقدة واحدة، فإن عامل التوازن المؤقت للعقدة بعد الإدخال سيكون ضمن النطاق [–2، +2]. لكل عقدة يتم فحصها، إذا بقي عامل التوازن المؤقت ضمن النطاق من –1 إلى +1، فلا يلزم سوى تحديث عامل التوازن دون الحاجة إلى تدوير. أما إذا كان عامل التوازن المؤقت ±2، فإن الشجرة الفرعية المتجذرة عند هذه العقدة تكون غير متوازنة وفقًا لـ AVL، ويلزم تدويرها. ^{[ 9 ]}^{: 52} مع الإدخال كما هو موضح في الكود أدناه، يُعيد التدوير المناسب توازن الشجرة بشكل مثالي على الفور.

في الشكل 1، من خلال إدخال العقدة الجديدة Z كعقدة فرعية للعقدة X، يزداد ارتفاع تلك الشجرة الفرعية Z من 0 إلى 1.

ثابت حلقة التراجع للإدخال

ازداد ارتفاع الشجرة الفرعية التي جذرها Z بمقدار 1. وهي الآن على شكل AVL.

مثال على كود لعملية إدراج

for ( X = parent ( Z ); X != null ; X = parent ( Z )) { // حلقة تكرارية (ربما حتى الجذر)// يجب تحديث BF(X):إذا كان ( Z == right_child ( X )) { // الشجرة الفرعية اليمنى تزدادإذا كانت قيمة BF ( X ) أكبر من الصفر ، فهذا يعني أن X مصفوفة ذات ثقل أيمن.// ==> BF(X) المؤقت == +2// ==> إعادة التوازن مطلوبة.G = parent ( X ); // حفظ العنصر الأب لـ X حول عمليات الدورانإذا ( BF ( Z ) < 0 ) // حالة اليمين واليسار (انظر الشكل 3)N = rotate_RightLeft ( X , Z ); // دوران مزدوج: يمين(Z) ثم يسار(X)وإلا // حالة اليمين (انظر الشكل 2)N = rotate_Left ( X , Z ); // دوران واحد لليسار (X)// بعد التدوير، قم بتكييف الرابط الأصل} آخر {إذا كانت قيمة BF ( X ) أقل من الصفر ، {BF ( X ) = 0 ; // يتم امتصاص الزيادة في ارتفاع Z عند X.break ; // الخروج من الحلقة}BF ( X ) = + 1 ;Z = X ; // يزداد الارتفاع (Z) بمقدار 1يكمل ؛}} else { // Z == left_child(X): تزداد الشجرة الفرعية اليسرىإذا كانت قيمة BF ( X ) أقل من الصفر ، فهذا يعني أن X ذات ثقل يساري.// ==> BF(X) المؤقت == -2// ==> إعادة التوازن مطلوبة.G = parent ( X ); // حفظ العنصر الأب لـ X حول عمليات الدورانإذا ( BF ( Z ) > 0 ) // حالة اليسار واليمينN = rotate_LeftRight ( X , Z ); // دوران مزدوج: يسار (Z) ثم يمين (X)وإلا // حالة اليسارN = rotate_Right ( X , Z ); // دوران واحد لليمين (X)// بعد التدوير، قم بتكييف الرابط الأصل} آخر {إذا كانت قيمة BF ( X ) أكبر من الصفر {BF ( X ) = 0 ; // يتم امتصاص الزيادة في ارتفاع Z عند X.break ; // الخروج من الحلقة}BF ( X ) = -1 ;Z = X ; // يزداد الارتفاع (Z) بمقدار 1يكمل ؛}}// بعد التدوير، قم بتكييف الرابط الأصل:// N هو الجذر الجديد للشجرة الفرعية المدورة// لا يتغير الارتفاع: الارتفاع (N) == الارتفاع القديم (X)parent ( N ) = G ;إذا كان ( G != null ) {إذا كان ( X == left_child ( G ))left_child ( G ) = N ;آخرright_child ( G ) = N ;} آخرtree -> root = N ; // N هو الجذر الجديد للشجرة الكاملةاستراحة ؛// لا يوجد خيار للفشل، فقط خيار للتوقف؛ أو الاستمرار؛}// ما لم يتم الخروج من الحلقة عبر break، فإن ارتفاع الشجرة الكلي يزداد بمقدار 1.

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

يمكن إيقاف عملية إعادة التتبع إذا أصبح عامل التوازن 0 مما يعني أن ارتفاع تلك الشجرة الفرعية يظل دون تغيير.

إذا أصبح عامل التوازن ±1، فإن ارتفاع الشجرة الفرعية يزداد بمقدار واحد، ويجب أن يستمر التراجع.

إذا أصبح عامل التوازن مؤقتًا ±2، فيجب إصلاح ذلك عن طريق دوران مناسب وبعد ذلك يكون للشجرة الفرعية نفس الارتفاع كما كان من قبل (وجذرها عامل التوازن 0).

يستغرق البحث وقتًا قدره $O(log n) ، بالإضافة إلى حد أقصى قدره$ $O(log n)$ من مستويات التتبع ( بمعدل $O(1)$ ) في طريق العودة إلى الجذر، لذا يمكن إتمام العملية في وقت قدره $O(log n)$ . ^{[ 9 ]}^{: 53}

يمسح

تتشابه الخطوات التمهيدية لحذف عقدة مع تلك المتبعة في شجرة البحث الثنائية . ففيها، يؤدي الحذف الفعلي للعقدة الأصلية أو العقدة البديلة إلى تقليل ارتفاع شجرة الأبناء المقابلة إما من 1 إلى 0 أو من 2 إلى 1، إذا كان لتلك العقدة ابن.

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

بما أن حذف عقدة واحدة لا يُقلل ارتفاع الشجرة الفرعية في AVL بأكثر من واحد، فإن عامل التوازن المؤقت للعقدة يتراوح بين -2 و+2. إذا بقي عامل التوازن ضمن النطاق من -1 إلى +1، يُمكن تعديله وفقًا لقواعد AVL. أما إذا أصبح ±2، فإن الشجرة الفرعية تكون غير متوازنة وتحتاج إلى تدوير. (على عكس الإضافة، حيث يُعيد التدوير توازن الشجرة دائمًا، قد يكون BF(Z) ≠ 0 بعد الحذف (انظر الشكلين 2 و3)، بحيث ينخفض ارتفاع الشجرة الفرعية المُعاد توازنها بمقدار واحد بعد التدوير الأحادي أو المزدوج المناسب، مما يعني ضرورة إعادة توازن الشجرة مرة أخرى على المستوى الأعلى التالي). تُشرح حالات التدوير المختلفة في قسم إعادة التوازن .

ثابت حلقة التتبع العكسي للحذف

انخفض ارتفاع الشجرة الفرعية التي جذرها N بمقدار 1. وهي الآن على شكل AVL.

مثال على كود لعملية الحذف

for ( X = parent ( N ); X != null ; X = G ) { // حلقة تكرارية (ربما حتى الجذر)G = parent ( X ); // حفظ العنصر الأب لـ X حول عمليات الدوران// لم يتم تحديث BF(X) بعد!إذا كان ( N == left_child ( X )) { // تتناقص الشجرة الفرعية اليسرىإذا كانت قيمة BF ( X ) أكبر من الصفر ، فهذا يعني أن X مصفوفة ذات ثقل أيمن.// ==> BF(X) المؤقت == +2// ==> إعادة التوازن مطلوبة.Z = right_child ( X ); // شقيق N (أكبر منه بمقدار 2)ب = BF ( Z );إذا ( ب < 0 ) // حالة اليمين واليسار (انظر الشكل 3)N = rotate_RightLeft ( X , Z ); // دوران مزدوج: يمين(Z) ثم يسار(X)وإلا // حالة اليمين (انظر الشكل 2)N = rotate_Left ( X , Z ); // دوران واحد لليسار (X)// بعد التدوير، قم بتكييف الرابط الأصل} آخر {إذا كانت قيمة BF ( X ) تساوي صفرًا ،BF ( X ) = + 1 ; // يتم امتصاص انخفاض ارتفاع N عند X.break ; // الخروج من الحلقة}N = X ;BF ( N ) = 0 ; // ينقص الارتفاع (N) بمقدار 1يكمل ؛}} else { // (N == right_child(X)): الشجرة الفرعية اليمنى تتناقصإذا كانت قيمة BF ( X ) أقل من الصفر ، فهذا يعني أن X ذات ثقل يساري.// ==> BF(X) المؤقت == -2// ==> إعادة التوازن مطلوبة.Z = left_child ( X ); // شقيق N (أكبر منه بمقدار 2)ب = BF ( Z );إذا ( ب > 0 ) // حالة اليسار واليمينN = rotate_LeftRight ( X , Z ); // دوران مزدوج: يسار (Z) ثم يمين (X)وإلا // حالة اليسارN = rotate_Right ( X , Z ); // دوران واحد لليمين (X)// بعد التدوير، قم بتكييف الرابط الأصل} آخر {إذا كانت قيمة BF ( X ) تساوي صفرًا ،BF ( X ) = -1 ; // يتم امتصاص انخفاض ارتفاع N عند X.break ; // الخروج من الحلقة}N = X ;BF ( N ) = 0 ; // ينقص الارتفاع (N) بمقدار 1يكمل ؛}}// بعد التدوير، قم بتكييف الرابط الأصل:// N هو الجذر الجديد للشجرة الفرعية المدورةparent ( N ) = G ;إذا كان ( G != null ) {إذا كان ( X == left_child ( G ))left_child ( G ) = N ;آخرright_child ( G ) = N ;} آخرtree -> root = N ; // N هو الجذر الجديد للشجرة الكاملةإذا كان ( ب == 0 )break ; // لا يتغير الارتفاع: اخرج من الحلقة// ينخفض الارتفاع (N) بمقدار 1 (== الارتفاع القديم (X)-1)}// إذا كانت (b != 0) فإن ارتفاع الشجرة الكلية ينقص بمقدار 1.

يمكن إيقاف عملية إعادة التتبع إذا أصبح عامل التوازن ±1 (يجب أن يكون 0) مما يعني أن ارتفاع تلك الشجرة الفرعية يظل دون تغيير.

إذا أصبح عامل التوازن 0 (يجب أن يكون ±1) فإن ارتفاع الشجرة الفرعية ينخفض بمقدار واحد ويجب أن يستمر التراجع.

إذا أصبح عامل التوازن مؤقتًا ±2، فيجب إصلاح ذلك بتدوير مناسب. يعتمد الأمر على عامل توازن الشجرة الشقيقة Z (الشجرة الفرعية الأعلى في الشكل 2) لتحديد ما إذا كان ارتفاع الشجرة الفرعية ينخفض بمقدار واحد - ويستمر التراجع - أو لا يتغير (إذا كان عامل توازن Z يساوي صفرًا) وتبقى الشجرة بأكملها على شكل AVL.

الوقت المطلوب هو $O(log n)$ للبحث، بالإضافة إلى حد أقصى قدره $O(log n)$ مستويات إعادة التتبع ( $O(1)$ في المتوسط) في طريق العودة إلى الجذر، لذلك يمكن إكمال العملية في وقت $O(log n) .$

عمليات الضبط والعمليات المجمعة

بالإضافة إلى عمليات الإدراج والحذف والبحث لعنصر واحد، تم تعريف عدة عمليات على مجموعات أشجار AVL: الاتحاد ، والتقاطع ، وفرق المجموعات . وبذلك، يمكن تنفيذ عمليات سريعة على مجموعات كبيرة من العناصر للإدراج أو الحذف بالاعتماد على هذه الدوال. وتعتمد هذه العمليات على عمليتين مساعدتين: التقسيم والضم . وبفضل هذه العمليات الجديدة، يصبح تنفيذ أشجار AVL أكثر كفاءة وقابلية للتوازي بدرجة عالية. ^[¹³^]

تُعيد الدالة Join، $عند تطبيقها على شجرتي AVL، t1 و t2، باستخدام المفتاح k، شجرةً تحتوي على جميع العناصر في t1 و t2 بالإضافة إلى k. يشترط أن يكون k أكبر من جميع المفاتيح في t1$ $وأصغر$ من $جميع$ $المفاتيح$ في $t2 .$ إذا $كان$ $الفرق$ في $ارتفاع$ الشجرتين $لا$ يتجاوز $واحدًا$ ، تُنشئ $Join$ $ببساطة$ عقدةً $جديدةً$ ذات شجرة فرعية يسارية $t1$ ، وجذر $k،$ $وشجرة$ فرعية يمينية $t2 .$ وإلا، بافتراض أن $t1$ أكبر من $t2$ بأكثر من واحد (الحالة الأخرى متناظرة)، $تتبع$ $Join$ العمود الفقري الأيمن لـ $t1$ $حتى$ $الوصول$ إلى عقدة $c$ متوازنة مع $t2$ $. عند هذه النقطة$ $،$ تُنشأ عقدة جديدة ذات ابن أيسر $c$ ، وجذر $k،$ وابن أيمن $t2$ لتحل محل c. تُحقق العقدة الجديدة شرط AVL، ويكون ارتفاعها أكبر من $c$ بمقدار واحد . قد تؤدي الزيادة في الارتفاع إلى زيادة ارتفاع أسلافها، مما قد يُبطل شرط AVL لتلك العقد. يمكن إصلاح ذلك إما بتدوير مزدوج إذا كان العنصر غير صالح عند الأصل، أو بتدوير واحد لليسار إذا كان العنصر غير صالح في مستوى أعلى من الشجرة، وفي كلتا الحالتين يتم استعادة الارتفاع لأي عقد سلفية لاحقة. وبالتالي، تتطلب عملية الربط تدويرين على الأكثر. تكلفة هذه العملية هي الفرق في الارتفاعات بين شجرتي الإدخال.

تنفيذ خوارزمية الربط باستخدام الشفرة الزائفة

دالة JoinRightAVL(TL _, k, _TR ) (l, k', c) = expose(T _L ) if (Height(c) <= Height(T _R )+1) T' = Node(c, k, T _R ) إذا كان ارتفاع (T') أقل من أو يساوي ارتفاع (l) + 1، فقم بإرجاع العقدة (l، k'، T'). وإلا، يتم إرجاع دالة التدوير لليسار (Node(l, k', rotateRight(T')))، وإلا فإن T' = JoinRightAVL(c, k, T _R ) T'' = Node(l, k', T') إذا كان ارتفاع (T') أقل من أو يساوي ارتفاع (l) + 1، فأرجع T''، وإلا فأرجع rotateLeft(T'').

دالة JoinLeftAVL(TL _, k, _TR ) /* متناظر مع JoinRightAVL */

دالة Join( _TL , k, TR ₎ إذا كان (ارتفاع(TL ₎ > ارتفاع(TR ₎ + 1) تُرجع JoinRightAVL(TL _, k, TR ₎ إذا كان (ارتفاع(TR ₎ > ارتفاع(TL ₎ + 1) تُرجع JoinLeftAVL(TL _, k, TR ₎ تُرجع Node (TL _, k, _TR )

هنا، يُمثل Height(v) ارتفاع الشجرة الفرعية (العقدة) $v$ . يستخرج (l,k,r) = expose(v) الابن الأيسر $l للعقدة$ $v$ ، والمفتاح $k$ لجذر $v$ ، والابن الأيمن $r$ . أما Node(l,k,r) فتعني إنشاء عقدة تتكون من الابن الأيسر $l$ ، والمفتاح $k$ ، والابن الأيمن $r$ .

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

تنفيذ خوارزمية التقسيم باستخدام الشفرة الزائفة

دالة Split(T, k) إذا كان (T = nil) تُرجع (nil, false, nil) (L,m,R) = expose(T) إذا كان (k = m) فأرجع (L، صحيح، R) إذا كان (k<m) (L',b,R') = Split(L,k) أرجع (L', b, Join(R', m, R)) إذا كان (k>m) (L',b,R') = Split(R, k) return (Join(L, m, L'), b, R'))

اتحاد شجرتي AVL $t 1$ و $t 2$ اللتين تمثلان المجموعتين $A$ و $B$ ، هو AVL $t$ الذي يمثل $A \cup B.$

تنفيذ خوارزمية الاتحاد باستخدام الشفرة الزائفة

دالة Union(t1 _, t2 ₎ : إذا _{كانت t1} = nil: أرجع t2 _.إذا كانت _t2 = nil: أرجع t1 _. (t _< , b, t _> ) = Split(t2 _, t1.root ₎ . أرجع Join(Union(left(t1 ₎ , t _< ), _t1.root , Union(right(t1 ₎ , t _> ))

هنا، يُفترض أن تُعيد دالة Split شجرتين: إحداهما تحتوي على المفاتيح الأقل من مفتاح الإدخال، والأخرى تحتوي على المفاتيح الأكبر. (الخوارزمية غير مُتلفة ، ولكن توجد نسخة مُتلفة في مكانها أيضًا).

تتشابه خوارزمية التقاطع أو الطرح، لكنها تتطلب روتين المساعدة Join2 ، وهو مماثل لروتين Join ولكن بدون المفتاح الأوسط. وبناءً على الدوال الجديدة للاتحاد والتقاطع والطرح، يمكن إدراج مفتاح واحد أو عدة مفاتيح في شجرة AVL أو حذفها منها. ولأن Split يستدعي Join ولكنه لا يتعامل مع معايير موازنة أشجار AVL بشكل مباشر، يُطلق على هذا النوع من التنفيذ عادةً اسم التنفيذ "القائم على Join" .

إن تعقيد كل من الاتحاد والتقاطع والاختلاف هو ${\text{O}}\left(m\log \left({n \over m}+1\right)\right)$ لأشجار AVL ذات الأحجام $m$ و $n\;(\geq m)$ والأهم من ذلك، بما أن الاستدعاءات المتكررة للوحدات (الاتحاد، التقاطع، أو الفرق) مستقلة عن بعضها البعض، فإنه يمكن تنفيذها بالتوازي بعمق متوازٍ . ${\text{O}}(\log m\log n)$ [ ¹³^] عندما $m=1$ ، يحتوي التنفيذ القائم على الربط على نفس الرسم البياني الحسابي الموجه غير الدوري (DAG) مثل إدراج وحذف عنصر واحد.

إعادة التوازن

إذا تغير فرق الارتفاع بين شجرتين فرعيتين أثناء عملية تعديل، فقد ينعكس ذلك، طالما أنه أقل من 2، في تعديل معلومات التوازن في الشجرة الأصلية. أثناء عمليات الإضافة والحذف، قد ينشأ فرق ارتفاع (مؤقت) مقداره 2، مما يعني ضرورة "إعادة توازن" الشجرة الأصلية. أدوات الإصلاح المُستخدمة هي ما يُسمى بتدوير الشجرة ، لأنها تُحرك المفاتيح "عموديًا" فقط، بحيث يُحفظ تسلسل المفاتيح "الأفقي" بالكامل (وهو أمر أساسي لشجرة البحث الثنائية). ^{[ 6 ]}^{: 458-481}^{[ 11 ]}^{: 33}

لنفترض أن X هي العقدة التي لها عامل توازن (مؤقت) يساوي -2 أو +2. تم تعديل شجرتها الفرعية اليسرى أو اليمنى. ولنفترض أن Z هي العقدة الفرعية ذات الشجرة الفرعية الأعلى (انظر الشكلين 2 و3). لاحظ أن كلا العقدتين الفرعيتين لهما شكل AVL وفقًا لفرضية الاستقراء .

في حالة الإضافة، حدثت هذه الإضافة لأحد أبناء Z بحيث زاد طول Z. في حالة الحذف، حدث هذا الحذف للشقيق t1 _لـ Z بحيث انخفض طول t1، الذي كان أقصر بالفعل. (هذه هي الحالة الوحيدة التي قد يكون فيها عامل توازن Z مساويًا للصفر) _.

هناك أربعة احتمالات محتملة للانتهاك:

يمين يمين	⟹ Z هو اليمين	ابن والده X و BF(Z) ≥ 0
يسار يسار	⟹ Z هو اليسار	ابن لوالده X و BF(Z) ≤ 0
يمين يسار	⟹ Z هو اليمين	ابن لوالده X و BF(Z) < 0
يسار يمين	⟹ Z هو اليسار	ابن لوالده X و BF(Z) > 0

وتتم عملية إعادة التوازن بشكل مختلف:

يمين يمين	⟹ يتم إعادة موازنة X باستخدام	بسيط	تناوب`rotate_Left`	(انظر الشكل 2)
يسار يسار	⟹ يتم إعادة موازنة X باستخدام	بسيط	تناوب`rotate_Right`	(صورة معكوسة للشكل 2)
يمين يسار	⟹ يتم إعادة موازنة X باستخدام	مزدوج	تناوب`rotate_RightLeft`	(انظر الشكل 3)
يسار يمين	⟹ يتم إعادة موازنة X باستخدام	مزدوج	تناوب`rotate_LeftRight`	(صورة معكوسة للشكل 3)

وبالتالي، يُرمز إلى هذه الحالات بالرمز CB ، حيث C (اتجاه الطفل) و B (التوازن) ينتميان إلى المجموعة { يسار ، يمين } مع يمين := -يسار . يُصلح اختلال التوازن في الحالة C == B بدوران بسيط rotate_(-C ) ، بينما تُصلح الحالة C ≠ B بدوران مزدوج rotate_CB .

تكلفة الدوران، سواء كان بسيطًا أو مزدوجًا، ثابتة.

دوران بسيط

يوضح الشكل 2 حالة "يمين يمين". في النصف العلوي، تحتوي العقدة X على شجرتين فرعيتين بمعامل توازن +2 . علاوة على ذلك، فإن الابن الداخلي t23 _للعقدة Z (أي الابن الأيسر عندما تكون Z هي الابن الأيمن، أو الابن الأيمن عندما تكون Z هي الابن الأيسر) ليس أعلى من شقيقه t4 _. يمكن أن يحدث هذا إما بزيادة ارتفاع الشجرة الفرعية t4 _أو بانخفاض ارتفاع الشجرة الفرعية t1 _. في الحالة الأخيرة، قد تحدث أيضًا حالة "الظل" حيث يكون لـ _t23 نفس ارتفاع _t4 .

تظهر نتيجة الدوران إلى اليسار في النصف السفلي من الشكل. يجب تحديث ثلاثة روابط (الحواف السميكة في الشكل 2) وعاملي توازن.

كما هو موضح في الشكل، قبل الإضافة، كانت طبقة الأوراق عند المستوى h+1، ثم انتقلت مؤقتًا إلى المستوى h+2، وبعد الدوران عادت إلى المستوى h+1. في حالة الحذف، كانت طبقة الأوراق عند المستوى h+2، وهو المستوى الذي كانت عليه عندما كان ارتفاع _t23 و t4 _{متساويًا} . وإلا، فإن طبقة الأوراق تصل إلى المستوى h+1، مما يؤدي إلى انخفاض ارتفاع الشجرة بعد الدوران.

مقتطف برمجي لدوران بسيط لليسار

مدخل:	X = جذر الشجرة الفرعية المراد تدويرها إلى اليسار
	Z = الابن الأيمن لـ X، وZ ذو ثقل أيمن.
	مع ارتفاع يساوي $ارتفاع (الشجرة الفرعية اليسرى ($ X $)) + 2$
نتيجة:	الجذر الجديد للشجرة الفرعية المعاد توازنها

node * rotate_Left ( node * X , node * Z ) {// قيمة Z أعلى بمقدار 2 من قيمة شقيقهاt23 = left_child ( Z ); // الابن الداخلي لـ Zright_child ( X ) = t23 ;إذا كان ( t23 != null )parent ( t23 ) = X ;left_child ( Z ) = X ;parent ( X ) = Z ;// الحالة الأولى، BF(Z) == 0،// يحدث هذا فقط مع الحذف، وليس مع الإضافة:إذا كان ( BF ( Z ) == 0 ) { // كان ارتفاع t23 مساويًا لارتفاع t4BF ( X ) = + 1 ; // t23 الآن أعلىBF ( Z ) = – 1 ; // t4 الآن أقل من X} آخر{ // الحالة الثانية تحدث مع الإضافة أو الحذف:BF ( X ) = 0 ;BF ( Z ) = 0 ;}إرجاع Z ؛ // إرجاع الجذر الجديد للشجرة الفرعية المدورة}

دوران مزدوج

يوضح الشكل 3 حالة يمين-يسار. في ثلثه العلوي، يحتوي العقد X على شجرتين فرعيتين بمعامل توازن +2 . ولكن على عكس الشكل 2، فإن الابن الداخلي Y للعقدة Z أعلى من شقيقه t4 _. قد يحدث هذا بإضافة Y نفسه، أو بزيادة ارتفاع إحدى شجرتيه الفرعيتين t2 _أو t3 ₍ مما يؤدي إلى اختلاف ارتفاعهما)، أو بانخفاض ارتفاع الشجرة الفرعية t1 _. في الحالة الأخيرة، قد يكون ارتفاع t2 _و t3 _{متساوياً} .

تظهر نتيجة الدوران الأول، وهو الدوران إلى اليمين، في الثلث الأوسط من الشكل. (فيما يتعلق بعوامل التوازن، يختلف هذا الدوران عن دورات AVL الفردية الأخرى، لأن فرق الارتفاع بين Y و t ₄ هو 1 فقط). تظهر نتيجة الدوران الأخير إلى اليسار في الثلث السفلي من الشكل. يجب تحديث خمسة روابط (الحواف السميكة في الشكل 3) وثلاثة عوامل توازن.

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

مقتطف من كود دوران مزدوج من اليمين إلى اليسار

مدخل:	X = جذر الشجرة الفرعية المراد تدويرها
	Z = طفلها الأيمن، ذو ثقل يساري
	مع ارتفاع يساوي $ارتفاع (الشجرة الفرعية اليسرى ($ X $)) + 2$
نتيجة:	الجذر الجديد للشجرة الفرعية المعاد توازنها

node * rotate_RightLeft ( node * X , node * Z ) {// قيمة Z أعلى بمقدار 2 من قيمة شقيقهاY = left_child ( Z ); // الابن الداخلي لـ Z// قيمة Y أعلى بمقدار 1 من قيمة شقيقهاt3 = right_child ( Y );left_child ( Z ) = t3 ;إذا كان ( t3 != null )parent ( t3 ) = Z ;right_child ( Y ) = Z ;parent ( Z ) = Y ;t2 = left_child ( Y );right_child ( X ) = t2 ;إذا كان ( t2 != null )parent ( t2 ) = X ;left_child ( Y ) = X ;parent ( X ) = Y ;// الحالة الأولى، BF(Y) == 0إذا كانت قيمة BF ( Y ) تساوي صفرًا ،BF ( X ) = 0 ;BF ( Z ) = 0 ;} else if ( BF ( Y ) > 0 ) {// كان t3 أعلىBF ( X ) = – 1 ; // t1 الآن أعلىBF ( Z ) = 0 ;} آخر {// كان t2 أعلىBF ( X ) = 0 ;BF ( Z ) = + 1 ; // t4 الآن أعلى}BF ( Y ) = 0 ;إرجاع Y ؛ // إرجاع الجذر الجديد للشجرة الفرعية المدورة}

مقارنة بالهياكل الأخرى

تُعدّ كلٌّ من أشجار AVL وأشجار الأحمر والأسود (RB) أشجار بحث ثنائية متوازنة ذاتيًا، وترتبطان رياضيًا. في الواقع، يمكن تلوين أي شجرة AVL باللونين الأحمر والأسود، ^{[ 14 ]} ولكن توجد أشجار RB غير متوازنة وفقًا لنموذج AVL. تلعب عمليات التدوير دورًا هامًا في الحفاظ على ثوابت شجرة AVL (أو RB). في أسوأ الحالات، حتى بدون تدوير، تتطلب عمليات الإضافة أو الحذف في AVL أو RB عددًا من عمليات الفحص و/أو تحديثات عوامل توازن AVL (أو ألوان RB) $قدره O(log n)$ . تتطلب عمليات الإضافة والحذف في RB، وكذلك عمليات الإضافة في AVL، من صفر إلى ثلاث عمليات تدوير متكررة ، وتُنفَّذ في زمن $O(1)$ مُستهلك ، ^[¹⁵^]^:^{الصفحات 165،}¹⁵⁸^[¹⁶^]، وبالتالي فهي ثابتة بنفس القدر في المتوسط. كما أن عمليات الحذف في AVL التي تتطلب $O(log$ $n$ $)$ من عمليات التدوير في أسوأ الحالات، تكون أيضًا $O(1)$ في المتوسط. تتطلب أشجار RB تخزين بت واحد من المعلومات (اللون) في كل عقدة، بينما تستخدم أشجار AVL في الغالب بتين لعامل التوازن، مع العلم أنه عند تخزينها في العقد الفرعية، يكفي بت واحد بمعنى «أصغر من شقيقه». ويكمن الاختلاف الأكبر بين بنيتي البيانات هاتين في حد الارتفاع.

بالنسبة لشجرة بحجم $n \geq 1$

يبلغ ارتفاع شجرة AVL على الأكثر
${\begin{array}{ll}h&\leqq \;c\log _{2}(n+d)+b\\&<\;c\log _{2}(n+2)+b\end{array}}$

أين

{\displaystyle \varphi

النسبة الذهبية :

={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618}

c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.440,

b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328,

و

d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.065

.

يبلغ ارتفاع شجرة RB على الأكثر
${\begin{array}{ll}h&\leqq \;2\log _{2}(n+1)\end{array}}$ [ ¹⁷^]

تتميز أشجار AVL بتوازن أكثر دقة من أشجار RB، حيث تبلغ نسبة الارتفاعات القصوى AVL/RB ≈ 0.720. وبالنسبة لعمليات الإدخال والحذف، أظهر بن بفاف في 79 قياسًا أن نسبة AVL/RB تتراوح بين 0.677 و1.077، بمتوسط وسيط ≈ 0.947 ومتوسط هندسي ≈ 0.910. ^{[ 4 ]}

انظر أيضاً

مراجع

1 2 3 4 5 6 إريك ألكسندر. "أشجار AVL" . مؤرشف من الأصل في 31 يوليو 2019.
↑ أديلسون-فيلسكي، جورجي؛ لانديس، يفغيني (1962). "خوارزمية لتنظيم المعلومات". وقائع أكاديمية العلوم في الاتحاد السوفيتي (باللغة الروسية). 146 : 263-266 .الترجمة الإنجليزية من قبل مايرون ج. ريتشي في الرياضيات السوفيتية - دوكلادي ، 3:1259–1263، 1962.
↑ سيدجويك ، روبرت (1983). "الأشجار المتوازنة" . الخوارزميات . أديسون-ويسلي. ص 199. ISBN 0-201-06672-6.
1 2 بفاف، بن (يونيو 2004). "تحليل أداء أشجار البحث الثنائية في برمجيات النظام" (ملف PDF) . جامعة ستانفورد .
↑ هل أشجار AVL غير متوازنة الوزن؟ (بمعنى: هل أشجار AVL غير متوازنة μ؟) وبالتالي: تُسمى الشجرة الثنائية $\mu$ متوازن، مع $0\leq \mu \leq {\tfrac {1}{2}}$ ، إذا كان لكل عقدة $N$ عدم المساواة
${\tfrac {1}{2}}-\mu \leq {\tfrac {|N_{l}|}{|N|+1}}\leq {\tfrac {1}{2}}+\mu$
يحمل و $\mu$ يتميز هذا العقار بانخفاضه إلى الحد الأدنى. $|N|$ يمثل عدد العقد الموجودة أسفل الشجرة مع $N$ كجذر (بما في ذلك الجذر) و $N_{l}$ هي العقدة الفرعية اليسرى لـ $N$ .
1 2 3 4 كنوت، دونالد إي. (2000). الفرز والبحث (الطبعة الثانية، الطبعة السادسة، طبعة منقحة ومحدثة ). بوسطن [ua]: أديسون-ويسلي. ISBN 0-201-89685-0.
↑ مع ذلك، يمكن الاحتفاظ بمعلومات التوازن في العقد الفرعية على شكل بت واحد يشير إلى ما إذا كانت العقدة الأصلية أعلى بمقدار 1 أو بمقدار 2؛ وبالتالي لا يمكن أن تكون أعلى بمقدار 2 لكلا العقدتين الفرعيتين. وبهذه الطريقة، تُعتبر شجرة AVL شجرة "متوازنة الرتبة" ، كما صاغها هاوبلر وسين وتارجان .
↑ ديكسيت، جيه بي (2010). إتقان هياكل البيانات من خلال لغة "سي" . نيودلهي، الهند: دار نشر جامعة ساينس برس، وهي إحدى مطبوعات لاكشمي للنشر المحدودة. ISBN 9789380386720. OCLC 939446542 .
1 2 3 براس، بيتر (2008). هياكل البيانات المتقدمة . كامبريدج: مطبعة جامعة كامبريدج. ISBN 9780511438202. OCLC 312435417 .
↑ هوبارد، جون راست (2000). ملخص شوم لنظرية ومشاكل هياكل البيانات باستخدام جافا . نيويورك: ماكجرو هيل. ISBN 0071378707. OCLC 48139308 .
1 2 3 بفاف، بن (2004). مقدمة في أشجار البحث الثنائية والأشجار المتوازنة . مؤسسة البرمجيات الحرة.
↑ وايس، مارك ألين (2006). هياكل البيانات وتحليل الخوارزميات في لغة C++ ( الطبعة الثالثة). بوسطن: بيرسون أديسون-ويسلي. ص 145. ISBN 0-321-37531-9. OCLC 61278554 .
1 2 بليلوش، جاي إي؛ فيريزوفيتش، دانيال؛ صن، ييهان (2016)، "الربط المباشر للمجموعات المرتبة المتوازية"، ندوة حول الخوارزميات والهياكل المتوازية ، ACM، ص 253-264 ، arXiv : 1602.02120 ، doi : 10.1145/2935764.2935768 ، ISBN 978-1-4503-4210-0، S2CID 2897793 .
↑ بول إي. بلاك (13 أبريل 2015). "شجرة AVL" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا . تم الاسترجاع في 2 يوليو 2016 .
↑ ميلهورن، كورت؛ ساندرز، بيتر (2008). الخوارزميات وهياكل البيانات . برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ. doi : 10.1007/978-3-540-77978-0 . ISBN 978-3-540-77977-3.
↑ دينش ب. ميهتا؛ سرتاج ساهني، محرران. (15-12-2017). دليل هياكل البيانات وتطبيقاتها ( الطبعة الثانية). نيويورك: تشابمان آند هول/سي آر سي. doi : 10.1201/9781315119335 . ISBN 978-1-315-11933-5.
↑ شجرة حمراء-سوداء# إثبات الحدود

للمزيد من القراءة

دونالد كنوث . فن برمجة الحاسوب ، المجلد 3: الفرز والبحث ، الطبعة الثالثة. أديسون-ويسلي، 1997. ISBN 0-201-89685-0الصفحات 458-475 من القسم 6.2.3: الأشجار المتوازنة.
هاوبلر، برنارد؛ سين، سيدهارتا؛ تارجان، روبرت إي. (2015)، "الأشجار المتوازنة الرتب" (ملف PDF) ، معاملات ACM في الخوارزميات ، 11 (4): المادة 30، 26، doi : 10.1145/2689412 ، MR 3361215 ، S2CID 1407290 .

روابط خارجية

تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "شجرة AVL" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .

[wiscurl-1] 1 2 3 4 5 6 إريك ألكسندر. "أشجار AVL" . مؤرشف من الأصل في 31 يوليو 2019.

[2] أديلسون-فيلسكي، جورجي؛ لانديس، يفغيني (1962). "خوارزمية لتنظيم المعلومات". وقائع أكاديمية العلوم في الاتحاد السوفيتي (باللغة الروسية). 146 : 263-266 .الترجمة الإنجليزية من قبل مايرون ج. ريتشي في الرياضيات السوفيتية - دوكلادي ، 3:1259–1263، 1962.

[3] سيدجويك ، روبرت (1983). "الأشجار المتوازنة" . الخوارزميات . أديسون-ويسلي. ص 199. ISBN 0-201-06672-6.

[Pfaff1-4] 1 2 بفاف، بن (يونيو 2004). "تحليل أداء أشجار البحث الثنائية في برمجيات النظام" (ملف PDF) . جامعة ستانفورد .

[5] هل أشجار AVL غير متوازنة الوزن؟ (بمعنى: هل أشجار AVL غير متوازنة μ؟) وبالتالي: تُسمى الشجرة الثنائية $\mu$ متوازن، مع $0\leq \mu \leq {\tfrac {1}{2}}$ ، إذا كان لكل عقدة $N$ عدم المساواة
${\tfrac {1}{2}}-\mu \leq {\tfrac {|N_{l}|}{|N|+1}}\leq {\tfrac {1}{2}}+\mu$
يحمل و $\mu$ يتميز هذا العقار بانخفاضه إلى الحد الأدنى. $|N|$ يمثل عدد العقد الموجودة أسفل الشجرة مع $N$ كجذر (بما في ذلك الجذر) و $N_{l}$ هي العقدة الفرعية اليسرى لـ $N$ .

[Knuth-6] 1 2 3 4 كنوت، دونالد إي. (2000). الفرز والبحث (الطبعة الثانية، الطبعة السادسة، طبعة منقحة ومحدثة ). بوسطن [ua]: أديسون-ويسلي. ISBN 0-201-89685-0.

[7] مع ذلك، يمكن الاحتفاظ بمعلومات التوازن في العقد الفرعية على شكل بت واحد يشير إلى ما إذا كانت العقدة الأصلية أعلى بمقدار 1 أو بمقدار 2؛ وبالتالي لا يمكن أن تكون أعلى بمقدار 2 لكلا العقدتين الفرعيتين. وبهذه الطريقة، تُعتبر شجرة AVL شجرة "متوازنة الرتبة" ، كما صاغها هاوبلر وسين وتارجان .

[dixit-mastering-data-structures-8] ديكسيت، جيه بي (2010). إتقان هياكل البيانات من خلال لغة "سي" . نيودلهي، الهند: دار نشر جامعة ساينس برس، وهي إحدى مطبوعات لاكشمي للنشر المحدودة. ISBN 9789380386720. OCLC 939446542 .

[brass-advanced-data-structures-9] 1 2 3 براس، بيتر (2008). هياكل البيانات المتقدمة . كامبريدج: مطبعة جامعة كامبريدج. ISBN 9780511438202. OCLC 312435417 .

[hubbard-outline-theory-problems-10] هوبارد، جون راست (2000). ملخص شوم لنظرية ومشاكل هياكل البيانات باستخدام جافا . نيويورك: ماكجرو هيل. ISBN 0071378707. OCLC 48139308 .

[Pfaff-11] 1 2 3 بفاف، بن (2004). مقدمة في أشجار البحث الثنائية والأشجار المتوازنة . مؤسسة البرمجيات الحرة.

[12] وايس، مارك ألين (2006). هياكل البيانات وتحليل الخوارزميات في لغة C++ ( الطبعة الثالثة). بوسطن: بيرسون أديسون-ويسلي. ص 145. ISBN 0-321-37531-9. OCLC 61278554 .

[join-based-13] 1 2 بليلوش، جاي إي؛ فيريزوفيتش، دانيال؛ صن، ييهان (2016)، "الربط المباشر للمجموعات المرتبة المتوازية"، ندوة حول الخوارزميات والهياكل المتوازية ، ACM، ص 253-264 ، arXiv : 1602.02120 ، doi : 10.1145/2935764.2935768 ، ISBN 978-1-4503-4210-0، S2CID 2897793 .

[14] بول إي. بلاك (13 أبريل 2015). "شجرة AVL" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا . تم الاسترجاع في 2 يوليو 2016 .

[15] ميلهورن، كورت؛ ساندرز، بيتر (2008). الخوارزميات وهياكل البيانات . برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ. doi : 10.1007/978-3-540-77978-0 . ISBN 978-3-540-77977-3.

[Dinesh-16] دينش ب. ميهتا؛ سرتاج ساهني، محرران. (15-12-2017). دليل هياكل البيانات وتطبيقاتها ( الطبعة الثانية). نيويورك: تشابمان آند هول/سي آر سي. doi : 10.1201/9781315119335 . ISBN 978-1-315-11933-5.

[17] شجرة حمراء-سوداء# إثبات الحدود

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[

[ 14 ]

[

[

17

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗