شجرة بحث ثنائية ذاتية التوازن

في علم الحاسوب ، تُعرف شجرة البحث الثنائية ذاتية التوازن (BST) بأنها أي شجرة بحث ثنائية قائمة على العقد ، تحافظ تلقائيًا على ارتفاعها (الحد الأقصى لعدد المستويات أسفل الجذر) صغيرًا في مواجهة عمليات الإضافة والحذف العشوائية للعناصر. ^{[ 1 ]} تتضمن هذه العمليات، عند تصميمها لشجرة بحث ثنائية ذاتية التوازن، تدابير وقائية ضد الزيادة غير المحدودة في ارتفاع الشجرة، ولذلك تُمنح هذه البنى البياناتية المجردة سمة "التوازن الذاتي".

بالنسبة للأشجار الثنائية المتوازنة الارتفاع ، يُعرَّف الارتفاع بأنه لوغاريتمي${\displaystyle O(\log n)}$في العدد${\displaystyle n}$من العناصر. هذا هو الحال بالنسبة للعديد من أشجار البحث الثنائية، مثل أشجار AVL وأشجار الأحمر والأسود . أشجار Splay وأشجار Treaps متوازنة ذاتيًا ولكنها ليست متوازنة الارتفاع، حيث لا يُضمن أن يكون ارتفاعها لوغاريتميًا بالنسبة لعدد العناصر.

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

تستغرق معظم العمليات على شجرة البحث الثنائية (BST) وقتًا يتناسب طرديًا مع ارتفاع الشجرة، لذا يُفضّل الحفاظ على ارتفاعها صغيرًا. يمكن أن تحتوي الشجرة الثنائية ذات الارتفاع h على 2⁰ ⁺ 2⁹ + ... + ^2h = 2h + ^{1 -} 1   عقدة على الأكثر . وبالتالي، لأي شجرة ذات ⁿ عقدة وارتفاع h :

${\displaystyle n\leq 2^{h+1}-1}$

وهذا يعني:

${\displaystyle h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor }$.

بمعنى آخر، الحد الأدنى لارتفاع شجرة ثنائية ذات n عقدة هو log ₂ ( n )، مقربًا إلى أقرب عدد صحيح أصغر ؛ أي،${\displaystyle \lfloor \log _{2}n\rfloor }$[ ^{1 ]​}

مع ذلك، قد تُنتج أبسط خوارزميات إدخال عناصر شجرة البحث الثنائية شجرةً بارتفاع n في حالات شائعة. على سبيل المثال، عند إدخال العناصر بترتيب المفاتيح المُرتّب ، تتحوّل الشجرة إلى قائمة مرتبطة ذات n عقدة. قد يكون الفرق في الأداء بين الحالتين هائلاً: على سبيل المثال، عندما n  =  1,000,000، يكون الحد الأدنى للارتفاع هو${\displaystyle \lfloor \log _{2}(1,000,000)\rfloor =19}$.

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

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

على الرغم من أنه من الممكن الحفاظ على BST بأقل ارتفاع مع التوقعات${\displaystyle O(\log n)}$في عمليات البحث والإضافة والحذف، تميل متطلبات المساحة الإضافية اللازمة للحفاظ على هذا الهيكل إلى أن تفوق انخفاض وقت البحث. على سبيل المثال، يضمن أن تكون شجرة AVL ضمن عامل 1.44 من الارتفاع الأمثل، بينما لا تتطلب سوى بتين إضافيتين من التخزين في تطبيق بسيط. ^{[ 1 ]} لذلك، تحافظ معظم خوارزميات BST ذاتية التوازن على الارتفاع ضمن عامل ثابت من هذا الحد الأدنى.

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

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

• شجرة AA
• شجرة AVL
• شجرة حمراء سوداء
• شجرة كبش الفداء
• شجرة التانغو
• تريب
• شجرة متوازنة الوزن

يمكن استخدام أشجار البحث الثنائية ذاتية التوازن بطريقة طبيعية لإنشاء قوائم مرتبة والحفاظ عليها ، مثل قوائم الانتظار ذات الأولوية . كما يمكن استخدامها للمصفوفات الترابطية ؛ حيث تُدرج أزواج المفتاح والقيمة ببساطة بترتيب يعتمد على المفتاح فقط. وبهذا المعنى، تتمتع أشجار البحث الثنائية ذاتية التوازن بعدد من المزايا والعيوب مقارنةً بمنافسها الرئيسي، جداول التجزئة . إحدى مزايا أشجار البحث الثنائية ذاتية التوازن هي أنها تسمح بتعداد سريع (بل مثالي تقاربياً) للعناصر بترتيب المفتاح ، وهو ما لا توفره جداول التجزئة. أما أحد عيوبها فهو أن خوارزميات البحث فيها تصبح أكثر تعقيداً عندما يكون هناك عناصر متعددة بنفس المفتاح. تتمتع أشجار البحث الثنائية ذاتية التوازن بأداء بحث أفضل في أسوأ الحالات من معظم جداول التجزئة ^{[ 2 ] .}${\displaystyle O(\log n)}$مقارنة ب${\displaystyle O(n)}$)، لكن أداءها في المتوسط ​​أسوأ (${\displaystyle O(\log n)}$مقارنة ب${\displaystyle O(1)}$).

يمكن استخدام أشجار البحث الثنائية ذاتية التوازن لتنفيذ أي خوارزمية تتطلب قوائم مرتبة قابلة للتغيير، وذلك لتحقيق الأداء الأمثل في أسوأ الحالات. على سبيل المثال، إذا تم تنفيذ فرز الشجرة الثنائية باستخدام شجرة بحث ثنائية ذاتية التوازن، فسنحصل على حل بسيط للغاية وسهل الوصف ولكنه مثالي من الناحية التقاربية.${\displaystyle O(n\log n)}$خوارزمية الفرز. وبالمثل، تستغل العديد من الخوارزميات في الهندسة الحسابية تنويعات على أشجار البحث الثنائية ذاتية التوازن لحل مشاكل مثل مشكلة تقاطع القطع المستقيمة ومشكلة تحديد موقع النقطة بكفاءة. (مع ذلك، بالنسبة للأداء في الحالة المتوسطة، قد تكون أشجار البحث الثنائية ذاتية التوازن أقل كفاءة من الحلول الأخرى. من المرجح أن يكون فرز الشجرة الثنائية، على وجه الخصوص، أبطأ من فرز الدمج أو الفرز السريع أو فرز الكومة ، بسبب تكلفة موازنة الشجرة بالإضافة إلى أنماط الوصول إلى الذاكرة المؤقتة ).

تُعدّ أشجار البحث الثنائية ذاتية التوازن هياكل بيانات مرنة، إذ يسهل توسيعها لتسجيل معلومات إضافية بكفاءة أو تنفيذ عمليات جديدة. على سبيل المثال، يمكن تسجيل عدد العقد في كل شجرة فرعية التي تمتلك خاصية معينة، مما يسمح بحساب عدد العقد في نطاق مفاتيح معين التي تمتلك تلك الخاصية.${\displaystyle O(\log n)}$الوقت. يمكن استخدام هذه الإضافات، على سبيل المثال، لتحسين استعلامات قواعد البيانات أو خوارزميات معالجة القوائم الأخرى.

• بنية بيانات البحث
• خوارزمية داي-ستاوت-وارن
• شجرة الاندماج
• قائمة التخطي
• فرز

• قاموس الخوارزميات وهياكل البيانات: شجرة البحث الثنائية المتوازنة الارتفاع
• مكتبة GNU libavl ، وهي مكتبة مرخصة بموجب رخصة LGPL، تحتوي على تطبيقات لأشجار ثنائية مكتوبة بلغة C، مع توثيق.