Trees & BST

الفصل السادس: الأشجار وشجرة البحث الثنائية

الهدف: الانتقال من البيانات الخطية إلى الهرمية، وفهم خوارزميات البحث السريع (BST).
1

Fundamental Terminology

مصطلحات الشجرة

  • Root (الجذر): العقدة الوحيدة التي ليس لها أب (Parent) .
  • Leaf (الورقة): العقدة التي ليس لها أبناء (Children) .
  • Siblings (الأخوة): عقد لها نفس الأب.
  • Depth (العمق): طول المسار من الجذر إلى العقدة (Root depth = 0).
  • Height (الارتفاع): طول أطول مسار من العقدة إلى ورقة (Leaf height = 0).
A
Root
B
C
D
E
F
2

Tree Traversals

كيف تزور كل العقد في الشجرة؟ هناك 3 طرق رئيسية:

Preorder (قبل)

Node → Left → Right

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

Inorder (بين)

Left → Node → Right

تزور اليسار، ثم العقدة، ثم اليمين.
في الـ BST: يطبع العناصر مرتبة تصاعدياً!

Postorder (بعد)

Left → Right → Node

تزور الأبناء أولاً، ثم العقدة.
مفيد لحذف الشجرة (Deleting) أو حساب حجم الملفات.

3

Binary Search Tree (BST)

قاعدة الـ BST الذهبية

Left Subtree < Node < Right Subtree

المميزات: البحث، الإضافة، والحذف تأخذ $O(\log N)$ في المتوسط.
(لأننا نستبعد نصف الشجرة في كل خطوة).
العيوب (Worst Case): إذا كانت الشجرة غير متوازنة (مثل القائمة المتصلة)، يصبح التعقيد $O(N)$.
🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / أصعب عملية

Removing Node with 2 Children

لا يمكنك حذف العقدة مباشرة!
الحل: استبدل قيمتها بأصغر قيمة في اليمين (Min of Right Subtree)، ثم احذف تلك العقدة الصغيرة (التي سيكون لها طفل واحد أو لا شيء) .

TRACING / تتبع

Expression Tree Traversal

شجرة التعبير $a + b * c$:
Inorder: $a + b * c$ (المعادلة الأصلية).
Postorder: $a b c * +$ (Postfix).
Preorder: $+ a * b c$ (Prefix).

→ السابق (Ch 5) الفصل التالي (Ch 7) ←