https://3rabica.org/index.php?action=history&feed=atom&title=%D8%B4%D8%AC%D8%B1%D8%A9_AVLشجرة AVL - تاريخ المراجعة2026-06-05T08:03:47Zتاريخ التعديل لهذه الصفحة في الويكيMediaWiki 1.43.7https://3rabica.org/index.php?title=%D8%B4%D8%AC%D8%B1%D8%A9_AVL&diff=1551189&oldid=prevعبد العزيز: بوت:صيانة المراجع2023-01-30T01:00:31Z<p>بوت:صيانة المراجع</p>
<p><b>صفحة جديدة</b></p><div>{{Infobox data structure}}<br />
[[ملف:AVLtreef.svg|تصغير|300بك|مثال لشجرة AVL]]<br />
في [[علم الحاسوب]]، '''شجرة إي في إل''' {{إنج|'''AVL Trees'''}} هي [[شجرة بحث ثنائية متزنة]] ، وهي أول [[بنية بيانات]] تم اختراعها.<ref>Robert Sedgewick, ''Algorithms'', Addison-Wesley, 1983, ISBN 0-201-06672-6, page 199, chapter 15: Balanced Trees.</ref><br />
في شجرة AVL، [[شجرة (بنية بيانات)#مصطلحات|ارتفاع]] الأشجار الجزئية لأية عقدة تختلف بواحد على الأكثر.<br />
البحث، الإدخال، والحذف يتطلبون زمن (O(log ''n'' في كل من الحالات المتوسطة والأسوء، حيث أن ''n'' هو عدد [[رأس (نظرية المخططات)|العقد]] في شجرة قبل العملية. الإدخال والحذف قد يستلزم إعادة توازن الشجرة عن طريق [[دوران شجرة]] واحد أو أكثر.<br />
<br />
شجرة AVL سميت نسبة لمخترعَيها [[الاتحاد السوفيتي|السوفيتيين]]، [[غيورغي أدلسن-فالسكي|غيورغي ماكسيموفيتش أدلسن-فالسكي]] (Adelson-Velskii) و[[يفغيني لانديس]] (Landis). الذين نشراها في مقالهما سنة [[1962]] «خوارزمية لتنظيم المعلومات».<ref>{{استشهاد بدورية محكمة|الأخير=Adelson-Velskii|الأول=G.|المؤلفون=E. M. Landis|سنة=1962|عنوان=An algorithm for the organization of information|صحيفة=Proceedings of the USSR Academy of Sciences|المجلد=146|صفحات=263–266}} {{أيقونة روسية}} English translation by Myron J. Ricci in ''Soviet Math. Doklady'', 3:1259–1263, 1962.</ref><br />
<br />
'''عامل التوازن''' لعقدة ما هو ارتفاع الشجرة الجزئية اليسرى ناقص ارتفاع الشجرة الفرعية اليمنى (أحيانا العكس). والعقدة مع عامل توازن 1، 0 أو -1 تعتبر متوازنة. عقدة مع عامل توازن غير ذلك تعتبر غير متوازنة وتتطلب إعادة توازن الشجرة. عامل التوازن إما أن يكون محفوظا في كل عقدة، أو يتم حسابه من ارتفاعات أشجاره الجزئية.<br />
<br />
عادة ما يتم مقارنة أشجار AVL مع [[شجرة أحمر أسود|أشجار أحمر-أسود]] لأنهما يدعمان نفس العمليات، ولأن أشجار أحمر-أسود يتطلبون زمن (O(log ''n'' في العمليات الأساسية. لأن أشجار AVL صارمون بالتوازن، هم أسرع من أشجار أحمر-أسود لتطبيقات المكثفة البحث.<ref>{{استشهاد ويب|الأخير = Pfaff|الأول = Ben|عنوان = Performance Analysis of BSTs in System Software| ناشر = Stanford University|سنة = 2004|شهر = June|مسار = https://web.stanford.edu/~blp/papers/libavl.pdf|تنسيق = PDF| مسار أرشيف = https://web.archive.org/web/20170809091546/http://stanford.edu/~blp/papers/libavl.pdf | تاريخ أرشيف = 9 أغسطس 2017 }}</ref><br />
من ناحية أخرى، أشجار أحمر-أسود هم أسرع بالإدخال والحذف.<br />
<br />
== عمليات ==<br />
[[ملف:AVL Tree Rebalancing.svg|تصغير|350بك|وصف مصور يظهر كيف أن عمليات دوران الشجرة تسبب إعادة توازن الشجرة. تمثل الأرقام العقد التي يتم موازنتها. المثلثات المعلمة بالحروف هي في حد ذاتها أشجار بحث ثنائية.]]<br />
<br />
العمليات الأساسية في شجرة AVL تشتمل على تنفيذ نفس الأعمال الممكن تنفيذها على [[شجرة بحث ثنائية]] غير متوازنة، ولكن تسبق التعديلات أو تليها عملية واحدة أو أكثر تسمى دوران شجرة، والتي تساعد على استعادة توازن ارتفاع الأشجار الجزئية.<br />
<br />
=== بحث ===<br />
البحث في شجرة AVL يتم بالضبط مثل أية شجرة بحث ثنائية غير متوازنة. بسبب توازن ارتفاع الشجرة، يستغرق البحث زمن (O(log ''n''، ولا يتم تعديل مبنى الشجرة في عملية البحث.<br />
<br />
إذا كان لكل عقدة سجلات أحجام شجرتها الجزئية (شاملا العقدة نفسها و[[شجرة (بنية بيانات)#مصطلحات|أحفادها]])، إذن يمكن استعادة العقدة بزمن (O(log ''n'' أيضا.<br />
<br />
<div style="text-align: center;">[[ملف:binary search tree delete.svg|تصغير|600بك|حذف عقدة مع ابنين من شجرة بحث ثنائية]]</div><br />
<br />
=== إدخال ===<br />
بعد إدخال عقدة، لابد من التحقق من تمسك كل من [[شجرة (بنية بيانات)#مصطلحات|أسلاف]] العقدة بقواعد AVL. لكل عقدة فحصت، إذا بقى عامل التوازن 1، 0 أو -1 إذن ليست هناك حاجة للدوران. من ناحية أخرى، إذا صار عامل التوازن ±2 إذن الشجرة الجزئية المبتدئة بهذه العقدة غير متوازنة. إذا تم الإدخال بشكل متسلسل، بعد كل إدخال، على الأكثر حالة واحدة من الحالات التالية يحب حلها لاستعادة قواعد AVL للشجرة كاملة.<br />
<br />
هنالك أربع حالات يجب التطرق لها، بحيث أن حالتين متماثلتان للاثنتين الأخرى ين. ليكن ''P'' جذر شجرة جزئية غير متوازنة، مع ''L'' الابن الأيسر و''R'' الابن الأيمن لـ ''P''.<br />
<br />
'''حالة يمين-يمين''' و'''حالة يمين-يسار''':<br />
* إذا كان معامل توازن ''P'' هو -2 إذن يفوق ارتفاع الشجرة الجزئية اليمنى ارتفاع الشجرة الجزئية اليسرى، ويجب فحص معامل توازن الابن الأيمن (''R''). الدوران الأيسر مع ''P'' كالجذر ضروري.<br />
* إذا كان معامل توازن ''R'' هو -1، نحتاج '''دوران يساري واحد''' (مع ''P'' كالجذر) (حالة يمين-يمين).<br />
* إذا كان معامل توازن ''R'' هو +1، نحتاج دوارنين. الدوران الأول هو '''دوران يميني''' مع ''R'' كالجذر. الدوران الثاني هو '''دوران يساري''' مع ''P'' كالجذر (حالة يمين-يسار).<br />
<br />
'''حالة يسار-يسار''' و'''حالة يسار-يمين''':<br />
* إذا كان معامل توازن ''P'' هو +2 إذن يفوق ارتفاع الشجرة الجزئية اليسرى ارتفاع الشجرة الجزئية اليمنى، ويجب فحص معامل توازن الابن الأيسر (''L''). الدوران الأيمن مع ''P'' كالجذر ضروري.<br />
* إذا كان معامل توازن ''L'' هو +1، نحتاج '''دوران يميني واحد''' (مع ''P'' كالجذر) (حالة يسار-يسار).<br />
* إذا كان معامل توازن ''L'' هو -1، نحتاج دوارنين. الدوران الأول هو '''دوران يساري''' مع ''L'' كالجذر. الدوران الثاني هو '''دوران يميني''' مع ''P'' كالجذر (حالة يسار-يمين).<br />
<br />
=== حذف ===<br />
إذا كانت العقدة [[شجرة (بنية بيانات)#مصطلحات|ورقة]] أو لها ابن واحد فقط، نزيلها.<br />
وإلا، نبدلها بإما الأكبر في الشجرة الجزئية اليسرى (السابق inorder predecessor) أو الأصغر في الشجرة الجزئية اليمنى (اللاحق inorder successor)، ونزيل العقدة.<br />
<br />
== مقارنة مع بنى بيانات أخرى ==<br />
كلا من أشجار AVL و[[شجرة أحمر أسود|أشجار أحمر-أسود]] هم أشجار بحث ثنائية متوازنة ذاتيا، ولذلك هم متشابهون رياضيا. عمليتا إعادة التوازن الأشجار مختلفة، ولكن كلاهما يحدث في زمن (O(log ''n''. الفرق الحقيقي بين الاثنتين هو تحديد الارتفاع.<br />
لشجرة بحجم <math> n </math>:<br />
<br />
ارتفاع شجرة AVL أقل بدقة من:<ref>{{استشهاد بكتاب|الأخير=Burkhard|الأول=Walt|عنوان=Advanced Data Structures|مسار=http://ieng6.ucsd.edu/~cs100s/public/Notes/CSE100Spring2010.pdf|تاريخ=Spring 2010|ناشر=[http://softreserves.ucsd.edu/ A.S. Soft Reserves], UC San Diego|مكان=La Jolla|صفحة=99|الفصل=AVL Dictionary Data Type Implementation| مسار أرشيف = https://web.archive.org/web/20200426144714/http://ieng6.ucsd.edu/~cs100s/public/Notes/CSE100Spring2010.pdf | تاريخ أرشيف = 26 أبريل 2020 | وصلة مكسورة = yes | تاريخ الوصول = أغسطس 2020 }}</ref><br />
:<math>\log_\varphi(n+2) - 1 = { \log_2(n+2) \over \log_2(\varphi) } - 1 = \log_\varphi(2) \cdot \log_2(n+2) - 1 \approx 1.44\log_2(n+2) - 1</math><br />
بحيث أن <math>\varphi</math> هو [[نسبة ذهبية|الرقم الذهبي]].<br />
ارتفاع شجرة أحمر-أسود هو على الأغلب <math>2\log_2(n+1)</math><br />
<br />
إن أشجار AVL أكثر صرامة بالتوازن من أشجار أحمر-أسود، مما يؤدي إلى إدخال وحذف أبطئ ولكن استرجاع أسرع.<br />
<br />
== انظر أيضا ==<br />
* [[شجرة (بنية بيانات)|شجرة]]<br />
* [[شجرة بحث ثنائية]]<br />
== مراجع ==<br />
{{مراجع}}<br />
<br />
== وصلات خارجية ==<br />
* [https://github.com/ZeR0God/exdgmime/wiki exdgmime library] by Dmitriy Vilkov: Straight C implementation could easily be taken from this library under GNU-LGPL and AFL v2.0 licenses.<br />
* [http://www.nist.gov/dads/HTML/avltree.html Description from the Dictionary of Algorithms and Data Structures]<br />
* [http://github.com/pgrafov/python-avl-tree/ Python Implementation]<br />
* [http://piumarta.com/software/tree/ Single C header file by Ian Piumarta]<br />
* [http://www.strille.net/works/media_technology_projects/avl-tree_2001/ AVL Tree Demonstration]<br />
* [http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html AVL tree applet – all the operations]<br />
* [http://github.com/fbuihuu/libtree Fast and efficient implementation of AVL Trees]<br />
* [https://github.com/mondrake/Rbppavl PHP Implementation]<br />
<br />
{{علم الحاسوب - بنى شجرية}}<br />
{{بنى بيانات}}<br />
{{تصنيف كومنز|AVL-trees}}<br />
{{شريط بوابات|علم الحاسوب}}<br />
<br />
[[تصنيف:أشجار ثنائية]]<br />
[[تصنيف:اختراعات سوفيتية]]<br />
[[تصنيف:بنى البيانات]]<br />
[[تصنيف:علم الحاسوب في 1962]]</div>عبد العزيز