Tree Properties

الفصل العاشر: الخصائص الرياضية للأشجار

الهدف: التمييز بين أنواع الأشجار (m-ary, Full)، وحساب عدد العقد والحواف بدقة.
1

What is a Tree؟

التعريف الرياضي

الشجرة هي رسم بياني غير موجه (Undirected Graph) يحقق شرطين معاً:

  • Connected: متصل (يوجد مسار بين أي نقطتين).
  • Acyclic: لا يحتوي على أي دورة (No simple circuits).

Forest (الغابة): مجموعة من الأشجار المنفصلة (Graph بدون دورات ولكن قد يكون غير متصل).

A
B
C

Tree ✅

A
B
C

Not Tree ❌ (Cycle)

2

Rooted Trees Terminology

عندما نختار رأساً ليكون "الجذر" ونوجه الحواف بعيداً عنه، نحصل على Rooted Tree.

Parent (الأب) الرأس $u$ الذي يتصل به $v$ مباشرة من جهة الجذر.
Child (الابن) الرأس $v$ الذي أبوه هو $u$.
Siblings (الإخوة) رؤوس لها نفس الأب.
Ancestors (الأجداد) كل الرؤوس في المسار من الجذر إلى الرأس.
Leaf (الورقة): رأس ليس له أبناء (Degree Out = 0).
Internal Vertex: رأس له ابن واحد على الأقل (ليس ورقة).
3

m-ary Trees

أنواع الأشجار حسب التفريغ

  • m-ary Tree: كل عقدة داخلية لها على الأكثر $m$ أبناء.
  • Full m-ary Tree: كل عقدة داخلية لها بالضبط $m$ أبناء.
  • Binary Tree: هي m-ary tree حيث $m=2$.

Counting Theorems (قوانين العد)

Tree with $n$ vertices $\to$ $n-1$ edges

Full m-ary Tree:

$n = m \cdot i + 1$

$l = (m-1)i + 1$

$i = (l-1)/(m-1)$

$n$: Total vertices
$i$: Internal vertices
$l$: Leaves
🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / الفرق الدقيق

Full m-ary Tree Definition

هل الشجرة التي فيها عقدة لها ابن واحد وعقدة أخرى لها ابنان تعتبر "Full Binary Tree"؟
لا!
في الـ Full Binary Tree، كل عقدة داخلية يجب أن يكون لها بالضبط 2 أبناء. لا يُسمح بـ 1.

FORMULA / الارتفاع

Height of m-ary Tree

لشجرة $m$-ary كاملة بـ $l$ ورقة:
أقل ارتفاع ممكن (Balanced): $h = \lceil \log_m l \rceil$.
هذا القانون يحدد كفاءة الأشجار في تخزين البيانات (كما في BST).

→ السابق (Ch 9) الفصل التالي (Ch 11) ←