محاضرة الأشجار الثنائية

مقدمة عن الأشجار

الأشجار هي نوع من أنواع بُنى المعطيات غير الخطية (Non-Linear Data Structures)، حيث لا توجد علاقة ترتيب كلي بين عناصرها ولكن هناك علاقة ترتيب جزئي.

ملاحظة هامة: الأشجار تنظم البيانات بشكل هرمي (Hierarchical) مما يجعلها مناسبة للعديد من التطبيقات مثل تنظيم الملفات وقواعد البيانات.

تعريف الشجرة

الشجرة هي مجموعة منتهية من العناصر تسمى عقد (Nodes) مرتبطة بعضها ببعض بروابط (Links or Edges)، وهي منظمة تنظيماً هرمياً (Hierarchical) لا يحوي حلقات مغلقة.

خصائص الشجرة:

توجد عقدة مميزة ووحيدة نسميها الجذر (Root)
العقد المتبقية تجزأ إلى n ≥ 0 من المجموعات المنفصلة تسمى الأشجار الفرعية (Sub-trees)
كل شجرة فرعية تتألف بدورها من عقدة جذر وأشجار فرعية أخرى (تعريف عودي)

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

المصطلح التعريف مثال الجذر (Root) العقدة الأعلى في الشجرة وليس لها أب العقدة A الأب (Parent) عقدة لها شجرة فرعية واحدة على الأقل العقدة D أب للعقد H, I, J الابن (Child) عقدة لها أب مباشر واحد العقدة H ابن للعقدة D الأخ (Sibling) عقدتان لهما نفس الأب العقد H, I, J أخوة السلف (Ancestor) جميع العقد على المسار من الجذر إلى العقدة A, D سلفان للعقدة H الخلف (Descendant) جميع العقد في الأشجار الفرعية للعقدة K, L, M خلفاء للعقدة H درجة العقدة (Degree) عدد الأبناء المباشرين للعقدة درجة العقدة A هي 3 درجة الشجرة الدرجة العظمى للعقد في الشجرة درجة الشجرة هي 3

أنواع العقد

العقدة الداخلية (Internal Node)

عقدة لها عقدة ولد واحدة على الأقل (لها أبناء)

مثال: العقد A, B, C, D, E, H

الورقة (Leaf Node)

عقدة ليس لها أبناء (درجتها = 0)

مثال: العقد K, L, F, G, M, I, J

الجذر (Root Node)

العقدة الأعلى في الشجرة وليس لها أب

مثال: العقدة A

أبعاد الشجرة

ارتفاع الشجرة (Height)

طول أطول مسار من الجذر إلى الورقة (عدد الوصلات)

height(A) = 3

height(B) = 2

height(M) = 0

عمق العقدة (Depth)

طول المسار من الجذر إلى العقدة (عدد الوصلات)

depth(A) = 0

depth(B) = 1

depth(M) = 3

مستوى العقدة (Level)

عمق العقدة (Level(x) = Depth(x))

Level 0: A

Level 1: B, C, D

Level 2: E, F, G, H, I, J

Level 3: K, L, M

البُعد التعريف قيم في مثالنا حجم الشجرة (Volume) عدد العقد الكلي في الشجرة 13 عرض الشجرة (Width) العدد الأعظمي للعقد في مستوى واحد 6 (في المستوى 2) عدد الوصلات (Edges) عدد الوصلات في الشجرة حجم الشجرة - 1 = 12

تطبيقات الأشجار

أنظمة الملفات

تنظيم المجلدات والملفات في نظم التشغيل بشكل هرمي

أشجار البحث

أشجار البحث الثنائية (BST) للبحث السريع

قواعد البيانات

فهرسة البيانات باستخدام أشجار B و B+

تطبيقات أخرى:

تمثيل العبارات الرياضية (Expression Trees)
أشجار اتخاذ القرار (Decision Trees)
شجرة الكومة (Heap) لفرز البيانات
تحليل الصياغة في المترجمات (Syntax Trees)
بناء القواميس المعجمية (Dictionaries)
الشبكات الحاسوبية (Spanning Trees)

تمثيل الأشجار

القوائم الخطية

تمثيل الشجرة باستخدام الأقواس المتداخلة

A(B(E(K,L),F),C(G),D(H(M)),J))

القوائم المترابطة

كل عقدة تحتوي على بيانات وروابط للأبناء

                                struct Node {

                                  int data;

                                  Node* children[];

                                };

الابن الأيسر - الأخ الأيمن

تمثيل باستخدام ابن أيسر وأخ أيمن

                                struct Node {

                                  int data;

                                  Node* leftChild;

                                  Node* rightSibling;

                                };

تحويل التمثيل إلى أشجار ثنائية:

بتدوير تمثيل "الابن الأيسر - الأخ الأيمن" بزاوية 45 درجة نحصل على شجرة ثنائية:

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

الشجرة الثنائية هي شجرة حيث كل عقدة لها على الأكثر ابنان (ابن أيسر وابن أيمن).

تعريف الشجرة الثنائية:

                        // الشجرة الثنائية هي:
                        // 1. شجرة فارغة (∅)
                        // 2. أو تتكون من:
                        //    - عقدة جذر
                        //    - شجرة ثنائية يسارية
                        //    - شجرة ثنائية يمينية
                    

الفروقات بين الأشجار الثنائية والأشجار العامة:

النقطة	الشجرة العامة	الشجرة الثنائية
الشجرة الفارغة	غير مسموحة	مسموحة
تمييز الأبناء	لا يوجد تمييز	ابن أيسر وابن أيمن
الدرجة القصوى	غير محددة	2

الخلاصة

الأشجار الثنائية: هي بنى معطيات هرمية غير خطية حيث كل عقدة لها على الأكثر ابنان (ابن أيسر وابن أيمن).

مميزات الأشجار الثنائية:

كفاءة عالية في عمليات البحث والإدراج والحذف
سهولة التمثيل في الذاكرة
تستخدم كأساس للعديد من بنى المعطيات المتقدمة
مناسبة للتطبيقات التي تتطلب اتخاذ قرارات ثنائية

في المحاضرة القادمة:

سنستكمل مع أشجار البحث الثنائية (Binary Search Trees) وتطبيقاتها في البحث والفرز.

محتويات المحاضرة