شبكة من أشجار البحث الثنائية مع الوراثة وتعدد الأشكال

Python Hard classes

مهمة «شبكة من أشجار البحث الثنائية مع الوراثة وتعدد الأشكال»

نفّذ صنف `Node` لعقدة شجرة بحث ثنائية (BST) مع دوال `insert` و `search` و `delete`. أنشئ صنف `BST` الذي يخزن الجذر ويحتوي على الدوال `insert` (إضافة قيمة)، `search` (البحث عن قيمة، يُرجع `True`/`False`)، `delete` (إزالة قيمة)، و `get_height` (ارتفاع الشجرة). ثم أنشئ صنف `AVLTree` يرث من `BST`، ويعيد تعريف `insert` و `delete` لدعم التوازن (مع التدويرات). بيانات الإدخال: سلسلة من الأوامر. الأوامر: `"insert x"` — أضف x، `"delete x"` — أزل x (إذا كان موجودًا)، `"search x"` — أخرج `"found"` أو `"not found"`، `"height"` — أخرج ارتفاع الشجرة. بالنسبة لـ `AVLTree`، بعد كل إضافة/إزالة، يتم التحقق من التوازن (فرق ارتفاعات الأشجار الفرعية <= 1) ويتم تنفيذ التدوير المناسب. القيود: -10^9 <= x <= 10^9، عدد الأوامر يصل إلى 10^5.

تنسيق الإدخال

السطر الأول: عدد صحيح واحد n (1 <= n <= 10^5) — عدد الأوامر. ثم n سطرًا، كل سطر يحتوي على أمر: insert x, delete x, search x, أو height.

تنسيق الإخراج

لكل أمر `search`، أخرج "found" أو "not found" في سطر منفصل. بالنسبة لأمر `height`، أخرج عددًا صحيحًا واحدًا — ارتفاع الشجرة (ارتفاع الشجرة الفارغة = 0).

أمثلة

مثال 1

الإدخال

الإخراج

مثال 2

الإدخال

2
0 0 0
2 -2 2 -2

الإخراج

main.py