AVL Tree عبارة عن شجرة بحث ثنائية متوازنة. قدم المنشور أشجار البحث الثنائية. تعتمد أوقات البحث والإدراج والحذف للشجرة الثنائية على ارتفاع الشجرة. في أسوأ الحالات، الارتفاع هو O(n). إذا كانت الشجرة متوازنة تمامًا - أي شجرة ثنائية كاملة - فإن ارتفاعها هو log n. هل يمكننا الحفاظ على شجرة متوازنة تماما؟ نعم، ولكن القيام بذلك سيكون مكلفا. الحل الوسط هو الحفاظ على شجرة متوازنة بشكل جيد - أي أن ارتفاعات الشجرتين الفرعيتين لكل عقدة هي نفسها تقريبًا.

أشجار AVL متوازنة بشكل جيد. تم اختراع أشجار AVL في عام 1962 من قبل اثنين من علماء الكمبيوتر الروس، G. M. Adelson-Velsky و E. M. Landis (ومن هنا جاء اسم AVL). في شجرة AVL، يكون الفرق بين ارتفاعات الشجرتين الفرعيتين لكل عقدة هو 0 أو 1. يمكن إثبات أن الحد الأقصى لارتفاع شجرة AVL هو O(log n).

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