The BinaryNode Class
هيكل العقدة (Node Structure)
لتمثيل الشجرة في الجافا، نحتاج كلاس بسيط يحتوي على البيانات ومؤشرين (يسار ويمين).
element: البيانات (AnyType).left: مؤشر للابن الأيسر.right: مؤشر للابن الأيمن.
class BinaryNode<AnyType> {
AnyType element;
BinaryNode<AnyType> left;
BinaryNode<AnyType> right;
// Constructor
BinaryNode(AnyType theElement) {
this(theElement, null, null);
}
}
Recursive Insert
كيف تعمل الإضافة؟
نستخدم دالة عودية (Recursive) تقارن القيمة الجديدة مع العقدة الحالية:
- إذا كانت العقدة
null(وصلنا ورقة)، أنشئ عقدة جديدة هنا. - إذا كانت القيمة أصغر، اذهب لليسار (Recursive).
- إذا كانت القيمة أكبر، اذهب لليمين (Recursive).
- إذا كانت مساوية، لا تفعل شيئاً (تجاهل التكرار).
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
if (t == null)
return new BinaryNode<>(x, null, null);
int compareResult = x.compareTo(t.element);
if (compareResult < 0)
t.left = insert(x, t.left);
else if (compareResult > 0)
t.right = insert(x, t.right);
else
; // Duplicate; do nothing
return t;
}
The Remove Operation
الحذف معقد لأنه قد يقطع الشجرة. لدينا 3 حالات:
1. Node is a Leaf (لا أطفال)
ببساطة، اجعل مؤشر الأب يشير إلى null. العقدة تختفي.
2. Node has One Child (طفل واحد)
تجاوز العقدة! اجعل مؤشر الأب يشير مباشرة إلى الطفل (الجد).
3. Node has Two Children (طفلان) 🔥
هنا تكمن الصعوبة. لا يمكننا الحذف مباشرة.
1. ابحث عن أصغر قيمة في الشجرة اليمنى (Min of Right Subtree).
2. انسخ تلك القيمة إلى العقدة المراد حذفها (استبدال البيانات).
3. احذف العقدة الأصلية لتلك القيمة الصغيرة (التي بالتأكيد ليس لها طفل أيسر، أي حالة 1 أو 2) .
Expression Trees (تطبيق عملي)
مثال: $(a + (b * c)) + (((d * e) + f) * g)$
- Inorder: يعطي التعبير الأصلي (مع الحاجة لأقواس).
- Postorder: يعطي صيغة Postfix (جاهزة للحساب بالمكدس).
- Preorder: يعطي صيغة Prefix.
شجرة بسيطة لـ: + * 5 4 3
(+)
/ \
(3) (*)
/ \
(4) (5)
BST Time Complexity
ما هو تعقيد الإضافة والحذف؟
المتوسط: $O(\log N)$ (إذا كانت الشجرة متوازنة).
الأسوأ: $O(N)$ (إذا كانت الشجرة خطية كالعمود).
انتبه: ليست دائماً Log N!
findMin() Logic
لإيجاد أصغر عنصر، اتجه لليسار دائماً حتى تصل للنهاية.
if (t == null) return null;
while (t.left != null)
t = t.left;
return t;