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

ما هي شجرة البحث الثنائية؟

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

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

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

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

تعقيد الوقت في شجرة البحث الثنائية

إذا كانت شجرة البحث الثنائية عبارة عن شجرة متوازنة تقريبًا، فإن جميع العمليات سيكون لها تعقيد زمني قدره يا (تسجيل الدخول) لأن البحث مقسم إما إلى الشجرة الفرعية اليسرى أو اليمنى.

خوارزمية التجميع k

إذا كانت شجرة البحث الثنائية إما منحرفة إلى اليسار أو إلى اليمين، فستكون جميع العمليات ذات تعقيد زمني قدره على) لأننا بحاجة إلى اجتياز العناصر ن.

ما هي شجرة AVL؟

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

كيف يحدث التوازن الذاتي لشجرة البحث الثنائية؟

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

دعونا نفهم التوازن الذاتي من خلال مثال.

لنفترض أننا نريد إدراج 10، 20، 30 في شجرة AVL.

فيما يلي طرق إدراج 10، 20، 30 في شجرة AVL:

إذا كان ترتيب الإدراج هو 30، 20، 10.

الخطوة 1: أولاً، نقوم بإنشاء شجرة بحث ثنائية، كما هو موضح أدناه:

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

كما نلاحظ، فإن الشجرة النهائية تتبع خاصية شجرة البحث الثنائية والشجرة المتوازنة؛ ولذلك، فهي شجرة AVL.

وفي هذه الحالة كانت الشجرة تركت شجرة غير متوازنة، لذلك نقوم بالتدوير الصحيح على العقدة.

foreach

إذا كان ترتيب الإدراج هو 10، 20، 30.

الخطوة 1: أولاً نقوم بإنشاء شجرة بحث ثنائية كما هو موضح أدناه:

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

كما يمكننا أن نلاحظ، فإن الشجرة النهائية تتبع خاصية شجرة البحث الثنائية و أ شجرة متوازنة ; ولذلك، فهي شجرة AVL.

إذا كان ترتيب الإدراج هو 30، 10، 20

الخطوة 1: أولاً نقوم بإنشاء شجرة البحث الثنائية كما هو موضح أدناه:

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

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

فرز المصفوفة في جافا

كما نلاحظ في الشجرة أعلاه، فإن الشجرة تتبع خاصية شجرة البحث الثنائي والشجرة المتوازنة؛ ولذلك، فهي شجرة AVL.

إذا كان ترتيب الإدراج هو 10، 30، 20

الخطوة 1: أولاً، نقوم بإنشاء شجرة البحث الثنائية، كما هو موضح أدناه:

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

ومع ذلك، فإن الشجرة المذكورة أعلاه غير متوازنة، لذا نحتاج إلى إجراء التدوير الأيسر على العقدة. بمجرد إجراء التدوير الأيسر، ستتحرك العقدة 20 لأعلى، وستتحرك العقدة 10 لأسفل كما هو موضح أدناه:

كما نلاحظ في الشجرة أعلاه، فإن الشجرة تتبع خاصية شجرة البحث الثنائي والشجرة المتوازنة؛ ولذلك، فهي شجرة AVL.

الاختلافات بين شجرة البحث الثنائية وشجرة AVL