هيكلة البيانات بواسطة الشجرة Tree

مفهوم الشجرة Tree:

الشجرة هو هيكل البيانات الغير خطية تتكون من عقد متصلة بواسطة حواف، وتشكل الشجرة هيكل هرمي، حيث يتم ترتيب العناصر الموجودة في الشجرة في مستويات متعددة، وتحتوي كل عقدة على بعض البيانات، ويمكن أن تكون البيانات من أي نوع.

لماذا يتم استخدام الشجرة لهيكلة البيانات؟

هياكل البيانات الأخرى مثل المصفوفات والقائمة المرتبطة والمكدس وقائمة الانتظار هي هياكل بيانات خطية تخزن البيانات بالتسلسل، من أجل إجراء أي عملية في هيكلة البيانات خطية فإن تعقيد الوقت يزداد مع زيادة حجم البيانات، لكنها غير مقبولة في عالم الحوسبة اليوم.

تسمح هياكل بيانات الشجرة المختلفة بالوصول الأسرع والأسهل إلى البيانات؛ لأنها بنية بيانات غير خطية.

مصطلحات مهمة في الشجرة لهيكلة البيانات:

العقدة (Node): وهي كيان يحتوي على قيمة ومؤشرات لعقده الفرعية، تسمى العقد الأخيرة من كل مسار بالعقدة الطرفية (leaf) أو العقد الخارجية التي لا تحتوي على رابط أو مؤشر للعقد الفرعية، والعقدة التي تحتوي على عقدة فرعية على الأقل تسمى عقدة داخلية.

حافة (Edge): هو الرابط بين أي عقدتين.

جذر (Root): هو العقدة العلوية للشجرة، بمعنى آخر، عقدة الجذر هي العقدة التي ليس لها أي عقدة أصل.

العقدة الفرعية (Child): إذا كانت العقدة سليلة لأي عقدة ، فإن العقدة تُعرف بالعقدة الفرعية.

الأصل (Parent): إذا كانت العقدة تحتوي على أي عقدة فرعية، فيُقال إن هذه العقدة هي أصل تلك العقدة الفرعية.

الأشقاء: تُعرف العقد التي لها نفس عقدة الأصل باسم الأشقاء.

ارتفاع العقدة (Height): ارتفاع العقدة هو عدد الحواف من عقدة معينة إلى أعمق عقدة (أي أطول مسار من عقدة معينة إلى عقدة الطرفية).

عمق العقدة: هو عدد الحواف من الجذر إلى عقدة معينة.

ارتفاع الشجرة: هو ارتفاع عقدة الجذر أو عمق أعمق عقدة.

درجة العقدة: درجة العقدة هي العدد الإجمالي لفروع تلك العقدة.

غابة: تسمى مجموعة من الأشجار المفككة غابة.

أنواع الشجرة لهيكلة البيانات:

• الشجرة الثنائية.

• شجرة البحث الثنائية.

• شجرة AVL.

• B-tree.

تطبيقات الشجرة في هيكلة البيانات:

1. تُستخدم أشجار البحث الثنائية للتحقق بسرعة من وجود عنصر في مجموعة أم لا.

2. الكومة (Heap) هي نوع من الأشجار تُستخدم لترتيب الكومة.

3. يتم استخدام نسخة معدلة من شجرة تسمى (Tries) في أجهزة التوجيه الحديثة لتخزين معلومات التوجيه.

4. تستخدم قواعد البيانات الأكثر شيوعًا “B-Trees” و “T-Trees”، وهي متغيرات هيكل الشجرة التي تعلمناها أعلاه لتخزين بياناتها.

5. يستخدم المترجمون شجرة بناء الجملة للتحقق من صحة بناء الجملة لكل برنامج تكتبه.