الدليل الشامل لـ شجرة أدلسن فالسكي ولانديس

في علم الحاسوب، شجرة إي في إل (بالإنجليزية: AVL Trees) هي شجرة بحث ثنائية متزنة، وهي أول بنية بيانات تم اختراعها.

في شجرة AVL، ارتفاع الأشجار الجزئية لأية عقدة تختلف بواحد على الأكثر.

البحث، الإدخال، والحذف يتطلبون زمن (O(log n في كل من الحالات المتوسطة والأسوء، حيث أن n هو عدد العقد في شجرة قبل العملية. الإدخال والحذف قد يستلزم إعادة توازن الشجرة عن طريق دوران شجرة واحد أو أكثر.

شجرة AVL سميت نسبة لمخترعَيها السوفيتيين، غيورغي ماكسيموفيتش أدلسن-فالسكي (Adelson-Velskii) ويفغيني لانديس (Landis). الذين نشراها في مقالهما سنة 1962 «خوارزمية لتنظيم المعلومات».

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

عادة ما يتم مقارنة أشجار AVL مع أشجار أحمر-أسود لأنهما يدعمان نفس العمليات، ولأن أشجار أحمر-أسود يتطلبون زمن (O(log n في العمليات الأساسية. لأن أشجار AVL صارمون بالتوازن، هم أسرع من أشجار أحمر-أسود لتطبيقات المكثفة البحث.

من ناحية أخرى، أشجار أحمر-أسود هم أسرع بالإدخال والحذف.