أشجار البحث الثنائية – الإدراج والبحث والحذف واجتياز الأشجار

ماذا تعرض

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

طريقة الاستخدام

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

المعاملات القابلة للتغيير

• النمط شجرة البحث الثنائية, اجتياز الشجرة, شجرة التعبير
• ترتيب الإدراج الأولي عشوائي, تصاعدي (مرتب), المفتاح الأوسط أولًا (متوازن)
• العدد الأولي للمفاتيح 3–15 مفاتيح
• المفاتيح الأولية للإدراج (أعداد من 1 إلى 99، مثل 50 30 70؛ فارغ = توليد تلقائي)
• الاجتياز الترتيب السابق (NLR), الترتيب الأوسط (LNR), الترتيب اللاحق (LRN), حسب المستويات (BFS)
• تعبير نموذجي (3 + 4) * 5, 3 + 4 * 5, (8 - 2) / (1 + 2), 2 * (x + 3) - y / 4, (a + b) * (c - d) ^ 2, مخصص
• تعبير مخصص (فارغ = استخدام التعبير النموذجي)
• سرعة التشغيل 0.5–4 خطوة/s

أسئلة للاستكشاف

1. ما ارتفاع الشجرة عند إدراج سبعة مفاتيح بترتيب تصاعدي، وكم مقارنة تلزم لإيجاد أكبر مفتاح؟
2. لماذا يسرد الاجتياز بالترتيب الأوسط لشجرة البحث الثنائية المفاتيح دائمًا بترتيب تصاعدي؟
3. كيف يُكتب التعبير (3 + 4) * 5 بالصيغة اللاحقة، ولماذا لا نحتاج فيها إلى أقواس؟