ما هي شجرة AVL؟

تتتبع كل عقدة في شجرة AVL **ارتفاعها** (height) الخاص: وهو عدد الحواف في أطول مسار نزولاً إلى الورقة. يبلغ ارتفاع الورقة 1، ويُحسب ارتفاع الشجرة الفرعية الفارغة كـ 0. من خلال ارتفاع طفلي العقدة، يمكنك حساب **معامل التوازن** (balance factor): height(left) - height(right).

تكون العقدة متوازنة عندما يكون معامل توازنها -1 أو 0 أو 1. قاعدة شجرة AVL بسيطة: **يجب أن تظل كل عقدة على حدة متوازنة طوال الوقت.** كلما أدت عملية إدراج أو حذف إلى دفع معامل توازن العقدة إلى 2 أو -2، تقوم الشجرة بإجراء **دوران** (rotation): وهو إعادة ترتيب محلية لعدد قليل من المؤشرات التي تستعيد التوازن في وقت ثابت دون كسر ترتيب شجرة البحث.

هناك أربع حالات للدوران (يسار-يسار، يمين-يمين، يسار-يمين، يمين-يسار)، لكنها جميعاً تتلخص في لبنتين أساسيتين: دوران يسار واحد ودوران يمين واحد. ستقوم ببناء كليهما من الصفر في الدروس القليلة القادمة.