دليل شامل: هياكل البيانات الشجرية (Trees)

١. وش هي الشجرة؟ 🌳

تعريف: في علم الحاسب، الشجرة هي نموذج تجريدي للهيكل الهرمي (Hierarchical) مكون من عُقد (Nodes) فيها علاقة أب–ابن (parent-child).

الخصائص الأساسية

هيكل بيانات غير خطي (عكس المصفوفات والقوائم المترابطة).
تنظيم هرمي للبيانات.
كل عقدة ممكن يكون لها أكثر من ابن.
فيه عقدة جذر (Root) وحدة في القمة.
مافي دورات (Cycles) – عكس الرسوم البيانية (Graphs).

تطبيقات من الواقع

استخدامات شائعة:

الهياكل التنظيمية: هرم الشركة.
أنظمة الملفات: المجلدات والملفات.
بيئات البرمجة: شجرة التركيب المجرد (Abstract Syntax Tree).
فهرسة قواعد البيانات: B-trees و B+ trees.
اتخاذ القرار: أشجار القرار في الذكاء الاصطناعي.

٢. مصطلحات الشجرة 📖

مصطلحات لازم تضبطها:

الجذر (Root): أعلى عقدة ومافيها أب (مثال: العقدة A).

عقدة داخلية (Internal Node): عقدة عندها على الأقل ابن واحد (العقد A, B, C, F).

عقدة خارجية / ورقة (External Node / Leaf): عقدة ماعندها أبناء (العقد E, I, J, K, G, H, D).

الأب (Parent): عقدة عندها ابن أو أكثر.

الابن (Child): عقدة عندها أب.

الأشقاء (Siblings): عقد تشترك في نفس الأب.

الأسلاف (Ancestors): الأب، الجد، الجد الأكبر، إلخ.

الأحفاد (Descendants): الابن، الحفيد، إلخ.

عمق العقدة (Depth): عدد الأسلاف (المسافة من الجذر).

ارتفاع الشجرة (Height): أكبر عمق لأي عقدة.

شجرة فرعية (Subtree): شجرة مكونة من عقدة وكل أحفادها.

مثال على شكل شجرة:

        A  (عمق 0، الجذر)
       / \
      B   C  (عمق 1)
     / \   \
    E   F   G  (عمق 2)
       / \   \
      I   J   K  (عمق 3)

ارتفاع الشجرة = ٣
العقد الداخلية: A, B, C, F
العقد الخارجية (الأوراق): E, I, J, G, K
الأشقاء: B و C ; I و J

٣. نوع البيانات المجرد (ADT) للشجرة 🔧

الأشجار تستخدم مواقع (positions) لتجريد العقد. الموقع هو طريقة نشير فيها للعقدة من دون ما نكشف تفاصيل بنيتها الداخلية.

الطرق العامة (Generic Methods)

الطريقة	الوصف	نوع الإرجاع
size()	ترجع عدد العقد في الشجرة	integer
isEmpty()	تتأكد إذا كانت الشجرة فاضية	boolean
iterator()	ترجع متجول (Iterator) على عناصر الشجرة	Iterator
positions()	ترجع مجموعة قابلة للتكرار تحتوي كل المواقع	Iterable

طرق الوصول (Accessor Methods)

الطريقة	الوصف	نوع الإرجاع
root()	ترجع موقع الجذر	Position
parent(p)	ترجع أب الموقع p	Position
children(p)	ترجع مجموعة قابلة للتكرار لأبناء p	Iterable
numChildren(p)	ترجع عدد أبناء p	Integer

طرق الاستعلام (Query Methods)

الطريقة	الوصف	نوع الإرجاع
isInternal(p)	تتأكد إذا p لها ابن واحد على الأقل	boolean
isExternal(p)	تتأكد إذا p ليس لها أبناء (ورقة)	boolean
isRoot(p)	تتأكد إذا p هو الجذر	boolean

٤. اجتياز الأشجار 🚶

الاجتياز (Traversal) هو طريقة منظمة نزور فيها كل عقد الشجرة مرة واحدة فقط.

الاجتياز بالترتيب المسبق (Preorder – NLR)

الخوارزمية:

Algorithm preOrder(v)
    visit(v)                    // نزور العقدة أول شيء
    for each child w of v
        preOrder(w)             // بعدين نزور أبناءها
                    

ترتيب الزيارة: الجذر → الشجرة الفرعية اليسرى → الشجرة الفرعية اليمنى

التطبيق: طباعة المستندات الهرمية، نسخ الشجرة.

الاجتياز بالترتيب المتأخر (Postorder – LRN)

الخوارزمية:

Algorithm postOrder(v)
    for each child w of v
        postOrder(w)            // نزور الأبناء أولاً
    visit(v)                    // بعدين نزور العقدة
                    

ترتيب الزيارة: الشجرة الفرعية اليسرى → الشجرة الفرعية اليمنى → الجذر

التطبيق: حساب مساحة التخزين، حذف شجرة، تقييم التعابير.

مثال:

على الشجرة:

        A
       /|\
      B C D

Preorder: A, B, C, D
Postorder: B, C, D, A

٥. الأشجار الثنائية 🌲

الشجرة الثنائية هي شجرة كل عقدة داخلية فيها عندها على الأكثر ابنين (بالضبط اثنين في الشجرة الثنائية المنتظمة – Proper binary tree). الأبناء مرتبين: ابن يسار وابن يمين.

خصائص الشجرة الثنائية

كل عقدة عندها على الأكثر ٢ من الأبناء.
الأبناء مرتبين (الفرق بين اليسار واليمين مهم).
ممكن تكون فاضية.
تعريف استرجاعي (Recursive): الشجرة الثنائية هي إما:
- شجرة بعقدة واحدة، أو
- شجرة جذرها عنده زوج مرتب من الأبناء، وكل ابن هو شجرة ثنائية.

خصائص الشجرة الثنائية المنتظمة (Proper Binary Tree)

قوانين مهمة:

نرمز: n = عدد العقد الكلي، e = العقد الخارجية، i = العقد الداخلية، h = الارتفاع

e = i + 1

عدد العقد الخارجية = عدد العقد الداخلية + ١

n = 2e - 1

مجموع العقد = ٢ × العقد الخارجية - ١

h ≤ i

الارتفاع ≤ عدد العقد الداخلية

h ≤ (n - 1)/2

الارتفاع ≤ (مجموع العقد - ١) ÷ ٢

e ≤ 2^h

العقد الخارجية ≤ ٢ أس الارتفاع

h ≥ log₂(e)

الارتفاع ≥ لوغاريتم e للأساس ٢

ADT للشجرة الثنائية

نوع البيانات المجرد للشجرة الثنائية (BinaryTree ADT) يزيد على Tree ADT بالطرق التالية:

left(p): يرجع الابن الأيسر للموقع p.
right(p): يرجع الابن الأيمن للموقع p.
sibling(p): يرجع الشقيق (الأخ) للموقع p.

هذي الطرق ترجع null إذا ماكان فيه ابن يسار/يمين أو شقيق.

٦. اجتياز الأشجار الثنائية 🔄

الاجتياز بالترتيب المتوسط (Inorder – LNR)

الخوارزمية:

Algorithm inOrder(v)
    if left(v) ≠ null
        inOrder(left(v))        // نزور الشجرة اليسرى
    visit(v)                    // نزور العقدة
    if right(v) ≠ null
        inOrder(right(v))       // نزور الشجرة اليمنى
                    

ترتيب الزيارة: الشجرة اليسرى → العقدة → الشجرة اليمنى

التطبيق: رسم شجرة ثنائية، إخراج عناصر شجرة البحث الثنائية (BST) مرتبة.

ملخص الاجتيازات للشجرة الثنائية

نوع الاجتياز	الترتيب	رمز مختصر	متى نستخدمه
Preorder	عقدة → يسار → يمين	NLR	نسخ الشجرة، التعابير بالبادئة (Prefix).
Inorder	يسار → عقدة → يمين	LNR	إخراج عناصر BST مرتبة، التعابير باللاحقة الوسطى (Infix).
Postorder	يسار → يمين → عقدة	LRN	حذف شجرة، التعابير باللاحقة (Postfix).

مثال كامل:

        A
       / \
      B   C

Inorder: B, A, C
Preorder: A, B, C
Postorder: B, C, A

اجتياز أويلر (Euler Tour)

اجتياز عام يزور كل عقدة ثلاث مرات:

على اليسار (L): قبل ما نعالج الشجرة اليسرى (preorder).
من تحت (B): بين الشجرة اليسرى واليمنى (inorder).
على اليمين (R): بعد ما نعالج الشجرة اليمنى (postorder).

اجتياز أويلر يشمل preorder و inorder و postorder كحالات خاصة.

٧. تطبيقات الأشجار الثنائية 💡

١. شجرة التعبير الحسابي (Arithmetic Expression Tree)

التركيب:

العقد الداخلية: العمليات (+ , - , × , ÷).
العقد الخارجية: المعاملات (أرقام، متغيرات).

مثال: (٢ × (أ - ١)) + (٣ × ب)

طباعة التعبير (Inorder):

Algorithm printExpression(v)
    if left(v) ≠ null
        print("(")
        inOrder(left(v))
    print(v.element())
    if right(v) ≠ null
        inOrder(right(v))
        print(")")
                    

الخرج: ((٢ × (أ - ١)) + (٣ × ب))

تقييم التعبير (Postorder):

Algorithm evalExpr(v)
    if isExternal(v)
        return v.element()
    else
        x ← evalExpr(left(v))
        y ← evalExpr(right(v))
        ◊ ← العملية المخزنة في v
        return x ◊ y
                    

٢. أشجار القرار (Decision Trees)

التركيب:

العقد الداخلية: أسئلة بإجابات نعم/لا.
العقد الخارجية: القرارات/النتائج.

التطبيقات: تعلم الآلة، ذكاء اصطناعي للألعاب، أنظمة التشخيص.

٨. طرق تنفيذ الأشجار 🔨

الهيكل المترابط (Linked Structure) للأشجار العامة

مكونات العقدة:

العنصر (البيانات).
مرجع (Reference) للعقدة الأب.
قائمة أو تسلسل للعقد الأبناء.

هذا أنسب تنفيذ للأشجار العامة، مرن جداً.

الهيكل المترابط للأشجار الثنائية

مكونات العقدة (أبسط من العام):

العنصر.
مرجع للأب.
مرجع للابن الأيسر.
مرجع للابن الأيمن.

التمثيل بالمصفوفة (Array-Based Representation)

معادلة تحديد مكان العقدة:

rank(الجذر) = ٠
إذا العقدة هي ابن أيسر: rank(العقدة) = ٢ × rank(الأب) + ١
إذا العقدة هي ابن أيمن: rank(العقدة) = ٢ × rank(الأب) + ٢

مثال للترميز:

      A (0)
     / \
    B   D
   (1) (2)
   / \   \
  E   F   J
 (3) (4) (6)

المصفوفة: [A, B, D, E, F, _ , J, ...]

الفهرس: ٠, ١, ٢, ٣, ٤, ٥, ٦

العيب: يهدر مساحة إذا الشجرة مو كاملة (كثير من الخانات فاضية).
الميزة: وصول سريع للأب والأبناء باستخدام عمليات حسابية.

٩. تحليل التعقيد ⏱️

تنفيذ الهيكل المترابط

العملية	التعقيد الزمني	الشرح
size(), isEmpty()	O(1)	مخزنة كمتغير في الكلاس.
root(), parent(), left(), right()	O(1)	وصول مباشر بالمرجع.
isInternal(), isExternal(), isRoot()	O(1)	فحوصات بسيطة.
iterator(), positions()	O(n)	لازم نزور كل العقد n.
replace()	O(1)	تحديث مباشر للعنصر.
children(p)	O(1)	نرجع المرجع للقائمة.

تعقيد الاجتيازات

كل الاجتيازات (preorder, inorder, postorder): O(n)

كل عقدة نزورها مرة وحدة.
الشغل في كل عقدة O(1).
الوقت الكلي = n × O(1) = O(n).

تعقيد المساحة

الهيكل المترابط: O(n) – كل عنصر بكائن عقدة مستقل.
التمثيل بالمصفوفة: O(2^h) – حيث h الارتفاع (يمكن يهدر مساحة).
الاجتياز الاسترجاعي (Recursive): O(h) – عمق مكدس الاستدعاءات يساوي الارتفاع.

📌 أهم النقاط

مفاهيم أساسية:

الأشجار هرمية: الجذر فوق، الأوراق تحت، وعلاقات أب–ابن.
ثلاثة اجتيازات رئيسية: Preorder (NLR)، Inorder (LNR)، Postorder (LRN).
الشجرة الثنائية خاصة: على الأكثر ابناً، مرتبين يسار ويمين.
الارتفاع مهم: يحدد كفاءة كثير من العمليات.
الشجرة الثنائية المنتظمة: e = i + 1 (الخارجي = الداخلي + ١).
خيارات التنفيذ: مترابط (مرن) vs مصفوفة (مضغوط للأشجار الكاملة).

نصائح للمذاكرة:

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

📋 المحتويات

١. وش هي الشجرة؟ 🌳

الخصائص الأساسية

تطبيقات من الواقع

٢. مصطلحات الشجرة 📖

مصطلحات لازم تضبطها:

مثال على شكل شجرة:

٣. نوع البيانات المجرد (ADT) للشجرة 🔧

الطرق العامة (Generic Methods)

طرق الوصول (Accessor Methods)

طرق الاستعلام (Query Methods)

٤. اجتياز الأشجار 🚶

الاجتياز بالترتيب المسبق (Preorder – NLR)

الخوارزمية:

الاجتياز بالترتيب المتأخر (Postorder – LRN)

الخوارزمية:

مثال:

٥. الأشجار الثنائية 🌲

خصائص الشجرة الثنائية

خصائص الشجرة الثنائية المنتظمة (Proper Binary Tree)

قوانين مهمة:

ADT للشجرة الثنائية

٦. اجتياز الأشجار الثنائية 🔄

الاجتياز بالترتيب المتوسط (Inorder – LNR)

الخوارزمية:

ملخص الاجتيازات للشجرة الثنائية

مثال كامل:

اجتياز أويلر (Euler Tour)

٧. تطبيقات الأشجار الثنائية 💡

١. شجرة التعبير الحسابي (Arithmetic Expression Tree)

طباعة التعبير (Inorder):

تقييم التعبير (Postorder):

٢. أشجار القرار (Decision Trees)

٨. طرق تنفيذ الأشجار 🔨

الهيكل المترابط (Linked Structure) للأشجار العامة

الهيكل المترابط للأشجار الثنائية

التمثيل بالمصفوفة (Array-Based Representation)

مثال للترميز:

٩. تحليل التعقيد ⏱️

تنفيذ الهيكل المترابط

تعقيد الاجتيازات

تعقيد المساحة

📌 أهم النقاط

مفاهيم أساسية:

نصائح للمذاكرة: