مقدمة

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

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

في هذه الدورة، ستقوم ببناء شجرة AVL من الصفر بلغتك المفضلة: عقد ذات ارتفاع متتبع، وفحوصات التوازن، وحالات الدوران الأربع، وعمليات إدراج وحذف ذاتية التوازن. بعد ذلك، ستستخدم الفئة (class) التي انتهيت منها لحل مجموعة من تحديات التدريب.