TechCodeview

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

الشجرة أعلاه هي أ شجرة البحث الثنائية . شجرة البحث الثنائية هي شجرة تكون فيها كل عقدة على الجانب الأيسر لها قيمة أقل من العقدة الأصلية، والعقدة الموجودة على الجانب الأيمن لها قيمة أعلى من العقدة الأصلية. في الشجرة أعلاه، n1 هي العقدة الجذرية، وn4، n6، n7 هي العقد الورقية. العقدة n7 هي أبعد عقدة من العقدة الجذرية. يحتوي n4 وn6 على حافتين ويوجد ثلاث حواف بين العقدة الجذرية والعقدة n7. بما أن n7 هو الأبعد عن العقدة الجذرية؛ وبالتالي فإن ارتفاع الشجرة أعلاه هو 3.

الآن سوف نرى ما إذا كانت الشجرة أعلاه متوازنة أم لا. تحتوي الشجرة الفرعية اليسرى على العقد n2 وn4 وn5 وn7، بينما تحتوي الشجرة الفرعية اليمنى على العقدتين n3 وn6. تحتوي الشجرة الفرعية اليسرى على عقدتين ورقيتين، أي n4 وn7. هناك حافة واحدة فقط بين العقدة n2 وn4 وحافتين بين العقدتين n7 وn2؛ ولذلك فإن العقدة n7 هي الأبعد عن العقدة الجذرية. ارتفاع الشجرة الفرعية اليسرى هو 2. تحتوي الشجرة الفرعية اليمنى على عقدة ورقية واحدة فقط، أي n6، ولها حافة واحدة فقط؛ وبالتالي، فإن ارتفاع الشجرة الفرعية اليمنى هو 1. والفرق بين ارتفاعات الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى هو 1. وبما أننا حصلنا على القيمة 1، فيمكننا القول أن الشجرة أعلاه هي شجرة متوازنة الارتفاع. يجب إجراء عملية حساب الفرق بين الارتفاعات لكل عقدة مثل n2 وn3 وn4 وn5 وn6 وn7. عندما نقوم بمعالجة كل عقدة سنجد أن قيمة k لا تزيد عن 1، لذلك يمكننا القول أن الشجرة أعلاه عبارة عن شجرة متوازنة شجرة ثنائية .

في الشجرة أعلاه، n6 وn4 وn3 هي العقد الورقية، حيث n6 هي العقدة الأبعد من العقدة الجذرية. توجد ثلاث حواف بين العقدة الجذرية والعقدة الورقية؛ وبالتالي، فإن ارتفاع الشجرة أعلاه هو 3. عندما نعتبر n1 بمثابة العقدة الجذرية، فإن الشجرة الفرعية اليسرى تحتوي على العقد n2 وn4 وn5 وn6، بينما تحتوي الشجرة الفرعية على العقدة n3. في الشجرة الفرعية اليسرى، n2 عبارة عن عقدة جذر، وn4 وn6 عبارة عن عقد ورقية. من بين العقد n4 وn6، n6 هي العقدة الأبعد عن العقدة الجذرية، وn6 لها حافتان؛ وبالتالي، فإن ارتفاع الشجرة الفرعية اليسرى هو 2. الشجرة الفرعية اليمنى لديها أي طفل على يسارها ويمينها؛ وبالتالي، فإن ارتفاع الشجرة الفرعية اليمنى هو 0. وبما أن ارتفاع الشجرة الفرعية اليسرى هو 2 والشجرة الفرعية اليمنى هو 0، فإن الفرق بين ارتفاع الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى هو 2. وفقًا للتعريف، فإن الفرق بين ارتفاع الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى يجب ألا يكون أكبر من 1. في هذه الحالة، يصبح الفرق 2، وهو أكبر من 1؛ ولذلك، فإن الشجرة الثنائية المذكورة أعلاه هي شجرة بحث ثنائية غير متوازنة.

لماذا نحتاج إلى شجرة ثنائية متوازنة؟

دعونا نفهم الحاجة إلى شجرة ثنائية متوازنة من خلال مثال.

الشجرة أعلاه عبارة عن شجرة بحث ثنائية لأن جميع عقد الشجرة الفرعية اليسرى أصغر من العقدة الأصلية وجميع عقد الشجرة الفرعية اليمنى أكبر من العقدة الأصلية. لنفترض أننا نريد العثور على القيمة 79 في الشجرة أعلاه. أولاً، نقارن قيمة العقدة n1 بـ 79؛ بما أن قيمة 79 لا تساوي 35 وهي أكبر من 35 فننتقل إلى العقدة n3 أي 48. وبما أن القيمة 79 لا تساوي 48 و79 أكبر من 48 فننتقل إلى اليمين طفل 48. قيمة الطفل الأيمن للعقدة 48 هي 79 وهي تساوي القيمة المراد البحث عنها. عدد القفزات المطلوبة للبحث عن عنصر 79 هو 2 والحد الأقصى لعدد القفزات المطلوبة للبحث عن أي عنصر هو 2. متوسط ​​الحالة للبحث عن عنصر هو O(logn).

الشجرة المذكورة أعلاه هي أيضًا شجرة بحث ثنائية لأن جميع عقد الشجرة الفرعية اليسرى أصغر من العقدة الأصلية وجميع عقد الشجرة الفرعية اليمنى أكبر من العقدة الأصلية. لنفترض أننا نريد العثور على القيمة 79 في الشجرة أعلاه. أولاً، نقارن القيمة 79 بالعقدة n4، أي 13. وبما أن القيمة 79 أكبر من 13، فإننا ننتقل إلى الابن الأيمن للعقدة 13، أي n2 (21). قيمة العقدة n2 هي 21 وهي أصغر من 79، لذا ننتقل مرة أخرى إلى يمين العقدة 21. قيمة الابن الأيمن للعقدة 21 هي 29. وبما أن القيمة 79 أكبر من 29، فإننا ننتقل إلى اليمين الطفل الأيمن للعقدة 29. قيمة الطفل الأيمن للعقدة 29 هي 35 وهو أصغر من 79 لذلك ننتقل إلى الطفل الأيمن للعقدة 35، أي 48. القيمة 79 أكبر من 48، لذلك ننتقل إلى الطفل الأيمن للعقدة 48. قيمة العقدة الفرعية اليمنى 48 هي 79 وهي تساوي القيمة المراد البحث عنها. في هذه الحالة، عدد القفزات المطلوبة للبحث عن عنصر هو 5. في هذه الحالة، أسوأ حالة هي O(n).

إذا زاد عدد العقد، تكون الصيغة المستخدمة في المخطط الشجري 1 أكثر كفاءة من الصيغة المستخدمة في المخطط الشجري 2. لنفترض أن عدد العقد المتوفرة في كلتا الشجرتين أعلاه هو 100000. للبحث عن أي عنصر في مخطط الشجرة البيانية2، الوقت المستغرق هو 100000 ميكروثانية، في حين أن الوقت المستغرق للبحث عن عنصر في المخطط الشجري هو سجل (100000) وهو ما يساوي 16.6 ميكروثانية. يمكننا أن نلاحظ الفرق الهائل في الوقت بين الشجرتين أعلاه. لذلك نستنتج أن شجرة التوازن الثنائية توفر البحث بشكل أسرع من بنية بيانات الشجرة الخطية.