شجرة WAVL

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 7 صور
الموسوعة الحرة

في علم الحاسوب ، تُعرف شجرة WAVL أو شجرة AVL الضعيفة بأنها شجرة بحث ثنائية متوازنة ذاتيًا . سُميت أشجار WAVL بهذا الاسم نسبةً إلى أشجار AVL ، وهي نوع آخر من أشجار البحث المتوازنة، وترتبط ارتباطًا وثيقًا بكلٍ من أشجار AVL وأشجار الأحمر والأسود ، التي تندرج جميعها ضمن إطار عمل مشترك لأشجار البحث المتوازنة الرتب . ومثل أشجار البحث الثنائية المتوازنة الأخرى، تستطيع أشجار WAVL التعامل مع عمليات الإضافة والحذف والبحث في زمن قدره O (log n ) لكل عملية. [ 1 ] [ 2 ]

صُممت أشجار WAVL لتجمع بين بعض أفضل خصائص أشجار AVL والأشجار الحمراء والسوداء. إحدى مزايا أشجار AVL على الأشجار الحمراء والسوداء هي توازنها: فهي تتميز بارتفاعها الذي لا يتجاوز 100 سم.سجلφ⁡ن≈1.44سجل2⁡ن{\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}(لشجرة تحتوي على n عنصر بيانات، حيثφ{\displaystyle \varphi }( النسبة الذهبية )، بينما تتمتع الأشجار الحمراء والسوداء بارتفاع أقصى أكبر،2سجل2⁡ن{\displaystyle 2\log _{2}n}إذا تم إنشاء شجرة WAVL باستخدام عمليات الإضافة فقط، دون حذف، فإنها تتمتع بنفس الحد الأدنى لارتفاع شجرة AVL. من ناحية أخرى، تتميز أشجار الأحمر والأسود عن أشجار AVL بقلة عمليات إعادة هيكلة أشجارها. ففي أشجار AVL، قد تتطلب كل عملية حذف عددًا لوغاريتميًا من عمليات تدوير الشجرة ، بينما تتميز أشجار الأحمر والأسود بعمليات حذف أبسط تستخدم عددًا ثابتًا فقط من عمليات تدوير الشجرة. وتستخدم أشجار WAVL، مثل أشجار الأحمر والأسود، عددًا ثابتًا فقط من عمليات تدوير الشجرة، بل إن هذا الثابت أفضل من أشجار الأحمر والأسود. [ 1 ] [ 2 ]

تم تقديم أشجار WAVL بواسطة هاوبلر، سين ، وتارجان (2015) . كما قدم المؤلفون أنفسهم وجهة نظر مشتركة لأشجار AVL، وأشجار WAVL، والأشجار الحمراء والسوداء باعتبارها جميعها نوعًا من الأشجار المتوازنة الرتب. [ 2 ]

إطار عمل الأشجار المتوازنة الرتب

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

الشجرة الثنائية المرتبة هي شجرة ثنائية حيث يرتبط كل عقدة x برتبة r(x). اصطلاحًا، تكون رتبة العقدة الفارغة -1. بالنسبة للعقدة x التي ليست الجذر، يكون فرق الرتبة هور(ص(x))-ر(x){\displaystyle r(p(x))-r(x)}وتُسمى هذه العقدة " عقدة فرعية من النوع i" إذا كان فرق الرتبة يساوي i. العقدة من النوعأنا،ج{\displaystyle i,j}إذا كان الفرق في الرتبة بين الطفل الأيسر والطفل الأيمن هو i و j (بغض النظر عن الترتيب).

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

  • قاعدة AVL، التي تتوافق مع شجرة AVL : كل عقدة من النوع 1,1 أو 1,2.
  • قاعدة 2-3، والتي تتوافق مع شجرة 2-3 الثنائية: كل عقدة من النوع 0,1 أو 1,1، ولا يوجد والد لـ 0-طفل هو 0-طفل.
  • قاعدة الأحمر والأسود، التي تُقابل شجرة الأحمر والأسود : جميع فروق الرتب إما 0 أو 1، ولا يوجد أب لعقدة فرعية من النوع 0 هو عقدة فرعية من النوع 0. تجدر الإشارة إلى أن قاعدة الأحمر والأسود تُعمم قاعدة 2-3 بالسماح بوجود عقدة من النوع 0,0.

حتى الآن، جميع هذه القواعد متناظرة بالنسبة للعقدة اليسرى والعقدة اليمنى. بكسر هذا التناظر، تنشأ قواعد أخرى:

  • قاعدة 2-3 ذات الميل لليمين، والتي تتوافق مع شجرة 2-3 الثنائية ذات الميل لليمين: كل عقدة هي 1,1 أو 0,1، ولا يوجد والد لعقدة 0-طفل هو 0-طفل، ولا يوجد 0-طفل متبقٍ.
  • قاعدة 2-3 ذات الميل الأيسر، والتي تتوافق مع شجرة 2-3 الثنائية ذات الميل الأيسر: كل عقدة هي 1,1 أو 0,1، ولا يوجد والد لـ 0-طفل هو 0-طفل، ولا يوجد 0-طفل على اليمين.
  • قاعدة الأحمر والأسود المائلة لليمين، والتي تتوافق مع شجرة الأحمر والأسود المائلة لليسار: لا يوجد أب لعقدة فرعية من النوع 0 هو عقدة فرعية من النوع 0، ولا توجد عقدة فرعية من النوع 0 لعقدة من النوع 0،1 متبقية.
  • قاعدة الأحمر والأسود ذات الميل اليساري، والتي تتوافق مع شجرة الأحمر والأسود ذات الميل اليساري : جميع فروق الرتب هي 0 أو 1، ولا يوجد والد لعقدة 0-طفل هو عقدة 0-طفل، ولا توجد عقدة 0-طفل لعقدة 0,1 صحيحة.

يتم تعريف شجرة AVL الضعيفة بواسطة قاعدة AVL الضعيفة:

  • قاعدة AVL الضعيفة: جميع فروق الرتب هي 1 أو 2، وجميع العقد الورقية لها رتبة 0.

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

تعريف

كما هو الحال مع أشجار البحث الثنائية بشكل عام، تتكون شجرة WAVL من مجموعة من العقد ، من نوعين: عقد داخلية وعقد خارجية. تخزن العقدة الداخلية عنصر بيانات، وترتبط بعقدتها الأبوية (باستثناء عقدة الجذر المحددة التي ليس لها عقدة أبوية) وبعقدتين فرعيتين فقط في الشجرة، وهما العقدة الفرعية اليسرى والعقدة الفرعية اليمنى. أما العقدة الخارجية فلا تحمل أي بيانات، وترتبط فقط بعقدتها الأبوية في الشجرة. تُرتّب هذه العقد لتشكيل شجرة ثنائية، بحيث يكون لكل عقدة داخلية x عقدتان أبويتان للعقدتين الفرعيتين اليسرى واليمنى x هما x نفسها. تُشكّل العقد الخارجية أوراق الشجرة. [ 3 ] تُرتّب عناصر البيانات في الشجرة بطريقة تجعل عملية اجتياز الشجرة بترتيب داخلي تُدرج عناصر البيانات بترتيب مُرتب. [ 4 ]

ما يُميّز أشجار WAVL عن أنواع أشجار البحث الثنائية الأخرى هو استخدامها للرتب . وهي أرقام مُرتبطة بكل عقدة، تُقدّم تقريبًا للمسافة من العقدة إلى أبعد فرع ورقي لها. على عكس أشجار AVL، حيث تُعرّف الرتب بأنها تُساوي ارتفاعات العقد، فإن الرتب في أشجار WAVL لا تُساوي الارتفاعات دائمًا. يُعرّف فرق رتبة العقدة x بأنه الفرق بين رتبة والد x ورتبة x. يجب أن تُحقق الرتب الخصائص التالية: [ 1 ] [ 2 ]

  • خاصية العقدة الخارجية: كل عقدة خارجية لها رتبة 0 [ 5 ]
  • خاصية فرق الرتبة: إذا كانت رتبة عقدة غير جذرية هي r ، فإن رتبة عقدتها الأبوية يجب أن تكون إما r + 1 أو r + 2. بعبارة أخرى، يكون فرق الرتبة لأي عقدة غير جذرية إما 1 أو 2. [ 1 ]
  • خاصية العقدة الداخلية: يجب أن يكون للعقدة الداخلية التي تحتوي على طفلين خارجيين رتبة 1 بالضبط.

العمليات

البحث

يُشابه البحث عن المفتاح k في شجرة WAVL إلى حد كبير البحث عنه في أي بنية بيانات شجرة بحث ثنائية متوازنة. يبدأ البحث من جذر الشجرة، ثم يُقارن k بشكل متكرر مع قيمة البيانات المخزنة في كل عقدة على مسار من الجذر، مُتبعًا المسار إلى الابن الأيسر للعقدة عندما تكون قيمة k أصغر من قيمة تلك العقدة، أو مُتبعًا المسار إلى الابن الأيمن عندما تكون قيمة k أكبر من قيمة تلك العقدة. عند الوصول إلى عقدة قيمتها تساوي k ، أو إلى عقدة خارجية، يتوقف البحث. [ 6 ]

إذا توقف البحث عند عقدة داخلية، فقد تم العثور على المفتاح k . أما إذا توقف البحث عند عقدة خارجية، فقد تم العثور على الموضع الذي سيتم فيه إدراج k (إذا تم إدراجه). [ 6 ]

الإدخال

يتطلب إدخال عقدة داخلية بمفتاح k في شجرة WAVL البحث عن k في الشجرة، وصولًا إلى عقدة خارجية، ثم استبدال تلك العقدة الخارجية بالعقدة الداخلية الجديدة ذات فرعين خارجيين، وأخيرًا إعادة توازن الشجرة. يمكن تنفيذ خطوة إعادة التوازن إما من أعلى إلى أسفل أو من أسفل إلى أعلى، [ 2 ] ولكن إعادة التوازن من أسفل إلى أعلى هي الأقرب إلى أشجار AVL. [ 1 ] [ 2 ]

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

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

وبالتالي، تتألف عملية الإدراج بشكل عام من البحث، وإنشاء عدد ثابت من العقد الجديدة، وعدد لوغاريتمي من تغييرات الرتبة، وعدد ثابت من عمليات تدوير الشجرة. [ 1 ] [ 2 ]

الحذف

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

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

إذا لم يكن للعقدة أب، يُستعاد التوازن. إذا زاد فرق الرتبة بين العقدة وأبيها من 1 إلى 2، يُستعاد التوازن. وإلا، إذا كان للشقيق، وهو الابن الآخر للأب، فرق رتبة مقداره 2 مع الأب، يُخفَّض ترتيب الأب - أي يُقلَّل ترتيبه بتقليل فروق الرتب بينه وبين كلٍّ من أبنائه - وتُستكمل عملية إعادة التوازن مع اعتبار الأب القديم هو العقدة الجديدة. وإلا، إذا كان لابني الشقيق فرق رتبة مقداره 2 مع الشقيق، يُخفَّض ترتيب الأب والشقيق، وتُستكمل عملية إعادة التوازن مع اعتبار الأب القديم هو العقدة الجديدة.

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

بشكل عام، تتكون عملية الحذف من البحث لأسفل للعثور على عقدة ذات فرع خارجي، وإزالة عدد ثابت من العقد الجديدة، وعدد لوغاريتمي من تغييرات الرتبة، وعدد ثابت من عمليات تدوير الشجرة.[1][2]

من المفيد مقارنة نتيجة حذف عقدة، مما يؤدي إلى تدويرها على مستويات متعددة في شجرة AVL، مع التدوير وتغييرات الرتبة التي تُجرى في شجرة WAVL. في الصورة الثانية، حُذفت العقدة ذات القيمة 12، ثم أُجري تدوير لليمين، وأُسندت الرتبة صفر لجميع العقد الخارجية.

شجرة فيبوناتشي ذات الرتب
شجرة فيبوناتشي مع الرتب بعد الحذف

التعقيد الحسابي

تتضمن كل عملية بحث أو إدراج أو حذف في شجرة WAVL اتباع مسار واحد في الشجرة وتنفيذ عدد ثابت من الخطوات لكل عقدة في هذا المسار. في شجرة WAVL تحتوي على n عنصرًا ولم تخضع إلا لعمليات إدراج، يكون الحد الأقصى لطول المسار هوسجلφ⁡ن≈1.44سجل2⁡ن{\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}إذا حدثت عمليات الإضافة والحذف معًا، فإن أقصى طول للمسار هو2سجل2⁡ن{\displaystyle 2\log _{2}n}لذلك، في كلتا الحالتين، يكون أسوأ وقت لكل عملية بحث أو إدراج أو حذف في شجرة WAVL تحتوي على n عنصر بيانات هو O (log n ) .

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

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

أشجار AVL

شجرة AVL هي نوع من أشجار البحث الثنائية المتوازنة، حيث يجب ألا يتجاوز الفرق بين ارتفاعي فرعي كل عقدة داخلية واحدًا. [ 7 ] ارتفاع العقدة الخارجية يساوي صفرًا، وارتفاع أي عقدة داخلية يساوي دائمًا واحدًا زائد أكبر ارتفاع بين ارتفاعي فرعيها. بالتالي، فإن دالة الارتفاع في شجرة AVL تخضع لقيود شجرة WAVL، ويمكننا تحويل أي شجرة AVL إلى شجرة WAVL باستخدام ارتفاع كل عقدة كرتبة لها. [ 1 ] [ 2 ]

يكمن الاختلاف الرئيسي بين شجرة AVL وشجرة WAVL في وجود عقدة لها ولدان بنفس الرتبة أو الارتفاع. ففي شجرة AVL، إذا كان للعقدة x ولدان بنفس الارتفاع h ، فإن ارتفاع x يجب أن يكون h + 1 بالضبط . في المقابل، في شجرة WAVL، إذا كان للعقدة x ولدان بنفس الرتبة r ، فإن رتبة x يمكن أن تكون إما r + 1 أو r + 2. وذلك لأن الرتبة لا تساوي الارتفاع تمامًا في شجرة WAVL. هذه المرونة الأكبر في الرتب تؤدي أيضًا إلى مرونة أكبر في البنى: فبعض أشجار WAVL لا يمكن تحويلها إلى أشجار AVL حتى بتعديل رتبها، لأنها تتضمن عقدًا يختلف ارتفاع أبنائها بأكثر من واحد. [ 2 ] ومع ذلك، يمكننا القول إن جميع أشجار AVL هي أشجار WAVL. أشجار AVL هي أشجار WAVL بدون نوع العقدة التي يكون فيها كلا الولدين بفارق رتبة يساوي 2. [ 1 ]

إذا تم إنشاء شجرة WAVL باستخدام عمليات الإضافة فقط، فسيكون هيكلها مماثلاً لهيكل شجرة AVL التي تم إنشاؤها بنفس تسلسل الإضافة، وستكون رتبها مماثلة لرتب شجرة AVL المقابلة. ولا يمكن أن تختلف شجرة WAVL عن شجرة AVL إلا من خلال عمليات الحذف. ويعني هذا تحديدًا أن شجرة WAVL التي تم إنشاؤها من خلال عمليات الإضافة فقط يكون ارتفاعها على الأكثرسجلφ⁡ن≈1.44سجل2⁡ن{\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}[ 2 ]​

أشجار حمراء وسوداء

شجرة الأحمر والأسود هي شجرة بحث ثنائية متوازنة حيث يكون لكل عقدة لون (أحمر أو أسود)، وتفي بالخصائص التالية:

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

يمكن تعريف الأشجار الحمراء والسوداء بشكل مكافئ من حيث نظام الرتب المخزنة في العقد، والتي تستوفي المتطلبات التالية (مختلفة عن متطلبات الرتب في أشجار WAVL):

  • رتبة العقدة الخارجية دائماً  0 ورتبة العقدة الأصلية دائماً  1.
  • رتبة أي عقدة غير جذرية تساوي إما رتبة العقدة الأبوية أو رتبة العقدة الأبوية ناقص  1.
  • لا يوجد حافتان متتاليتان على أي مسار بين الجذر والورقة لهما فرق في الرتبة يساوي  صفرًا.

يمكن ملاحظة التكافؤ بين التعريفات القائمة على اللون والتعريفات القائمة على الرتبة، من جهة، بتلوين العقدة باللون الأسود إذا كانت رتبة العقدة الأب أعلى، وباللون الأحمر إذا كانت رتبة العقدة الأب مساوية لرتبة العقدة الأب. ومن جهة أخرى، يمكن تحويل الألوان إلى رتب بجعل رتبة العقدة السوداء مساوية لعدد العقد السوداء على أي مسار إلى عقدة خارجية، وبجعل رتبة العقدة الحمراء مساوية لرتبة العقدة الأب. [ 8 ]

يمكن تحويل رتب العقد في شجرة WAVL إلى نظام رتب للعقد، يفي بمتطلبات الأشجار الحمراء-السوداء، وذلك بقسمة كل رتبة على اثنين وتقريب الناتج إلى أقرب عدد صحيح. [ 9 ] وبفضل هذا التحويل، يوجد لكل شجرة WAVL شجرة حمراء-سوداء صالحة بنفس البنية. ولأن الأشجار الحمراء-السوداء لها أقصى ارتفاع2سجل2⁡ن{\displaystyle 2\log _{2}n}وينطبق الأمر نفسه على أشجار WAVL. [ 1 ] [ 2 ] ومع ذلك، توجد أشجار حمراء-سوداء لا يمكن إعطاؤها دالة رتبة صالحة لشجرة WAVL. [ 2 ]

على الرغم من أن أشجار WAVL، من حيث بنيتها الشجرية، تُعد حالات خاصة من أشجار الأحمر والأسود، إلا أن عمليات تحديثها تختلف. قد تُحدث عمليات تدوير الشجرة المستخدمة في تحديث أشجار WAVL تغييرات غير مسموح بها في أشجار الأحمر والأسود، لأنها ستؤدي فعليًا إلى إعادة تلوين فروع فرعية كبيرة من شجرة الأحمر والأسود، بدلًا من تغيير اللون على مسار واحد فقط في الشجرة. [ 2 ] وهذا يسمح لأشجار WAVL بإجراء عدد أقل من عمليات تدوير الشجرة لكل عملية حذف، في أسوأ الأحوال، مقارنةً بأشجار الأحمر والأسود. [ 1 ] [ 2 ]

مراجع

  1. 1 2 3 4 5 6 7 8 9 10 غودريتش ، مايكل ت .؛ تاماسيا، روبرتو (2015)، "4.4 أشجار AVL الضعيفة"، تصميم الخوارزميات وتطبيقاتها ، وايلي، ص 130-138 .
  2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 هاوبلر، برنارد؛ سين، سيدهارتا؛ تارجان، روبرت إي. (2015)، "الأشجار المتوازنة الرتب" (ملف PDF) ، معاملات ACM في الخوارزميات ، 11 (4): المادة 30، 26، doi : 10.1145/2689412 ، MR 3361215 .
  3. ^ جودريتش وتاماسيا (2015) ، القسم 2.3 الأشجار، ص 68-83.
  4. ↑ جودريتش وتاماسيا (2015) ، الفصل 3 أشجار البحث الثنائية، الصفحات 89-114.
  5. ↑ في هذا نتبع Goodrich & Tamassia (2015) . في النسخة التي وصفها Haeupler وSen و Tarjan (2015) ، تكون رتبة العقد الخارجية -1 . هذا الاختلاف لا يُحدث فرقًا يُذكر في عمليات أشجار WAVL، ولكنه يُسبب بعض التغييرات الطفيفة في صيغة تحويل أشجار WAVL إلى أشجار حمراء-سوداء.
  6. 1 2 Goodrich & Tamassia (2015) ، القسم 3.1.2 البحث في شجرة بحث ثنائية ، ص 95-96.
  7. ^ جودريتش وتاماسيا (2015) ، القسم 4.2 أشجار AVL، الصفحات من 120 إلى 125.
  8. ↑ جودريتش وتاماسيا (2015) ، القسم 4.3 الأشجار الحمراء والسوداء، الصفحات 126-129.
  9. ↑ في دراسة هاوبلر، سين وتارجان (2015) ، يتم التحويل عن طريق التقريب إلى الأسفل، لأن رتب العقد الخارجية هي -1 بدلاً من 0. يقدم جودريتش وتاماسيا (2015) صيغة تقوم أيضًا بالتقريب إلى الأسفل، ولكن نظرًا لأنهم يستخدمون الرتبة 0 للعقد الخارجية، فإن صيغتهم تعين بشكل خاطئ الرتبة 0 للأحمر والأسود للعقد الداخلية ذات رتبة WAVL 1.