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

تحتاج هذه المقالة إلى مصادر إضافية للتحقق . يُرجى المساعدة في تحسين هذه المقالة بإضافة مصادر موثوقة . قد يتم الطعن في المواد غير الموثقة وإزالتها. البحث عن المصادر:  "Self-balancing binary search tree" – news  · journalist  · books  · scholar  · JSTOR ( November 2010 ) ( Learn how and when to remove this message )

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

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

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

تستغرق معظم العمليات على شجرة البحث الثنائية (BST) وقتًا يتناسب طرديًا مع ارتفاع الشجرة، لذا فمن المستحسن الحفاظ على الارتفاع صغيرًا. يمكن للشجرة الثنائية ذات الارتفاع h أن تحتوي على 2 ⁰ +2 ¹ +···+2 ^h  = 2 ^{h +1} −1 عقدة على الأكثر . ويترتب على ذلك أنه بالنسبة لأي شجرة بها n عقدة وارتفاع 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 )، مقربًا للأسفل ؛ أي . ^[1]${\displaystyle \lfloor \log _{2}n\rfloor }$

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

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

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

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

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

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

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

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

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

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

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

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