الشجرة في هيكل البيانات – بلغة بسيطة

يتم تعريف بنية أو هيكل بيانات الشجرة (the Tree Data Structure) على أنها مجموعة من الكائنات أو الكيانات تسمى العقد (Node) المرتبطة ببعضها البعض بشكل هرمي (بواسطة الحواف). الشجرة هي هيكل بيانات غير خطية لأنها تخزن البيانات بشكل هرمي بدلاً من تخزينها بالتسلسل. في هيكل بيانات الشجرة ، تُعرف العقدة الأولى باسم عقدة الجذر. تبدأ الشجرة من عقدة الجذر وتتطور. تحتوي كل عقدة على بيانات وتحتوي أيضًا على مراجع للعقد الفرعية. لا يمكن أبدًا أن تحتوي العقدة الجذرية على عقدة أصل.

ضرورة وجود شجرة في هيكل البيانات (Tree in Data Structures)

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

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

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

في ما يلي ، يتم وصف كل من هذه المصطلحات ومكونات الشجرة بإيجاز ، وفي النهاية ، يتم توفير رابط الوصول إلى جدول المصطلحات العامة للشجرة في هيكل البيانات.

• الجذر (Root): في هيكل بيانات الشجرة ، تكون العقدة الجذرية هي العقدة الأولى أو العقدة الأصلية. العقدة الجذرية هي العقدة التي نشأت منها الشجرة بأكملها. لا تحتوي العقدة الجذرية على أصل ولديها عقد فرعية فقط. في الصورة أعلاه ، تعتبر العقدة A جذر الشجرة.
• العقدة الأصلية (Parent Node): العقدة التي تقع مباشرة قبل عقدة مفترضة تسمى العقدة الأصلية لتلك العقدة المفترضة. في الصورة أعلاه ، B هو والد E و F.
• العقدة الفرعية (Childe Node): جميع العقد التي تكون مباشرة بعد عقدة مفترضة وتعتبر ورثتها هي أبناء تلك العقدة المفترضة. في الصورة أعلاه ، F و E هما أبناء B.
• الورقة (Leaf): العقدة التي ليس لها أطفال تسمى ورقة. عادةً ما تسمى العقد الحدودية للشجرة أو العقد الأخيرة من الشجرة بأوراق الشجرة. في الصورة أعلاه ، E ، F ، J ، K ، H ، أنا عبارة عن عقد ورقية.
• الحافة (Edge): الحافة عبارة عن اتصال بين عقدتين ويظهر بخط اتصال بين هاتين العقدتين. في الشجرة ذات العقد n ، سيكون عدد الحواف n-1. في الصورة أعلاه ، يسمى خط الاتصال بين A و B أو A و C أو B و F أو أي عقد أخرى تتصل ببعضها البعض بالحافة.
• الأشقاء (Siblings): يعني الأشقاء في الحياة الواقعية الأشخاص الذين لديهم نفس الوالدين ، وبالمثل في الأشجار ، تُعتبر العقد ذات الوالدين المشتركين أشقاء. في الصورة أعلاه ، I و H توأمان.
• المسار (Path): المسار عبارة عن عدد من الحواف المتتالية من العقدة المصدر إلى العقدة الوجهة. في الصورة أعلاه ، A ، C ، G ، K هي المسار من العقدة A إلى K.
• ارتفاع العقدة (Height of Node): يشير ارتفاع العقدة إلى عدد حواف أطول مسار بين تلك العقدة والطرف. في الصورة أعلاه ، تشكل A و C و G و K الارتفاع. ارتفاع A يساوي عدد الأضلاع بين A و K يساوي 3. وبالمثل ، فإن G لها ارتفاع يساوي واحدًا لأنه يحتوي على حافة واحدة فقط لعقدة الورقة التالية.
• مستويات العقدة (Levels of Node): يشير مستوى العقدة إلى إنشاء تلك العقدة. العقدة الجذرية عند المستوى صفر والعقدة الفرعية التالية في المستوى الأول وحفيدها في المستوى 2. في الصورة أعلاه ، مستوى H و I و J يساوي 3 ومستوى D و E و F و G يساوي 2.
• درجة العقدة (Degree of Node): تسمى درجة العقدة المفترضة عدد العقد الفرعية لتلك العقدة المفترضة. في الصورة أعلاه ، درجة D تساوي 2 ودرجة C تساوي 3.
• الزيارة (Visiting): عندما يتم التنقل في عقدة معينة وفقًا للبرنامج ، فإن التحقق من قيمة العقدة الحالية أو الوصول إليها يسمى بالزيارة.
• العقدة الداخلية (Internal Node): تُعرف العقدة التي تحتوي على طفل واحد على الأقل بالعقدة الداخلية. في الصورة أعلاه ، جميع العقد باستثناء E و F و J و K و H و I داخلية.
• العبور (Traversing): العبور هو عملية زيارة عقدة بترتيب معين. هناك ثلاثة أنواع من عمليات الاجتياز ، والتي تشمل عمليات الاجتياز التي تم فرزها مسبقًا وفرزها مسبقًا وفرزها لاحقًا.
• العقدة السلفية (Ancestor Node): أسلاف العقدة هي جميع العقد السابقة من الجذر إلى تلك العقدة. أي أن الآباء في الأجيال المختلفة المرتبطة بعقدة معينة هم أسلاف تلك العقدة. في الصورة أعلاه ، A و C و G هم أسلاف العقد K و J.
• السليل (Descendant): العقدة الموضوعة مباشرة بعد عقدة مفترضة تسمى سليل تلك العقدة المفترضة. في الصورة أعلاه ، K من الجيل G.
• الشجرة الفرعية (Sub Tree): تمثل أحفاد العقدة الشجرة الفرعية. يمكن أن تحتوي الشجرة باعتبارها بنية بيانات متكررة على العديد من الأشجار الفرعية داخل نفسها. في الصورة أعلاه ، تمثل العقد B و E و F شجرة فرعية.

الشجرة الكاملة في هيكل البيانات

الشجرة الثنائية الكاملة هي شجرة ممتلئة بالكامل باستثناء المستوى الأخير ، والتي يتم ملؤها من اليسار إلى اليمين قدر الإمكان. تحتوي الشجرة الثنائية الكاملة ذات الارتفاع h على عقد بين 2h و 2h+1. وفي الشجرة الثنائية الكاملة ، يمكن أن يكون للعقدة فرع واحد فقط.

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

خصائص الشجرة في هيكل البيانات

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

تكرار هيكل بيانات الشجرة

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

مثال لفهم خاصية التكرار للشجرة في هيكل البيانات بشكل أفضل

في الشكل أدناه ، ترى الشجرة رقم 1 مع العقدة الجذرية “A”. تعتبر الأشجار الفرعية الحالية بما في ذلك الأشجار 2 و 3 ذات الجذور “C” و “D” على التوالي أشجارًا مستقلة. وبالتالي تحتوي الشجرة على عدة أشجار فرعية ، وبالتالي تعتبر الشجرة بنية بيانات متكررة لأنها تحتوي على هيكل البيانات المكررة الخاصة بها.

ملاحظة: حتى العقد الورقية هي شجرة بحد ذاتها ، أي أن العقدة الورقية وحدها يمكن اعتبارها شجرة بدون عقد فرعية.

علاقة ثابتة بين عدد الحواف والعقد في هيكل بيانات الشجرة

إذا كانت هناك عُقد في الشجرة ، فسيكون عدد الحواف n-1. الحافة عبارة عن خط اتجاهي يربط عقدتين.

خاصية عمق العقدة في هيكل بيانات الشجرة

يتم تعريف عمق العقدة x على أنه طول المسار من الجذر إلى العقدة x. كل حافة تزيد من عمق العقدة بوحدة واحدة. لذلك ، يمكن اعتبار عمق العقدة x مساويًا لعدد العقد من العقدة الجذرية إلى العقدة x. عمق العقدة x يساوي:

depth=L+1
أو
العمق = عدد المستويات من الجذر إلى المستوى L زائد 1

في العلاقة أعلاه ، المستوى L هو المستوى الذي توجد فيه العقدة x. وتجدر الإشارة إلى أن المستوى الأول يبدأ بصفر.

ارتفاع عقدة الشجرة في هياكل البيانات

يمثل ارتفاع العقدة عدد حواف أطول مسار بين تلك العقدة والطرف. في ما يلي ، تمت مناقشة مسألة تنفيذ الشجرة في هيكل البيانات ؛ قبل ذلك ، أولاً ، تم تقديم سلسلة الدورات التدريبية لبناء البيانات وتصميم الخوارزمية لمزيد من التعلم.

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

يتم تطبيق هيكل بيانات الشجرة عمليًا واستخدامه في العالم الحقيقي. بعض هذه التطبيقات مذكورة أدناه.

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

يعد التنقل في نموذج كائن المستند (Document Object Model | DOM) أحد أهم استخدامات الشجرة. يسمح “العبور” عبر الشجرة للمبرمجين بالوصول إلى العقد ذات الصلة ، وبالتالي السماح بالوصول إلى جميع الأشقاء في عقدة معينة. تصبح بنية بيانات الشجرة مسارًا لمترجم HTML للتنقل عبر مستند HTML بأكمله.

البحث مع هيكل بيانات الشجري

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

على الرغم من أن شجرة البحث الثنائية توفر إمكانية البحث الأمثل ، إلا أنه يجب أيضًا مراعاة الحاجة إلى مزيد من الجهد لإنشاء شجرة البحث الثنائية. التعقيد الزمني أو ترتيب التنفيذ للبحث عن عنصر في شجرة البحث الثنائية يساوي O (H) ، حيث H هو ارتفاع الشجرة. لا تجعل O (H) البحث فعالاً فحسب ، بل تسمح أيضًا بالإدراج والحذف في كل عقدة في الشجرة. ومن ثم ، فإن تنظيم البيانات في شجرة ممكن أيضًا من خلال الإدراج والحذف الفعال في كل عقدة.

القرار بمساعدة هيكل الشجرة

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

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

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

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

ولكن إذا كان التطبيق ذو الصلة لديه القدرة على عرض أفضل فيلم مقترح للمستخدم تلقائيًا ، فهل من الممكن العثور على فيلم جديد لم يشاهده المستخدم حتى الآن وإمكانية استمتاع المستخدم بهذا الفيلم هو الحد الأقصى؟ للإجابة على هذا السؤال ، تم اقتراح تطبيق مهم آخر لهيكل الشجرة ، أي التعلم الآلي ، والذي تمت مناقشته بمزيد من التفصيل.

تطبيق هيكل بيانات الشجرة في التعلم الآلي

لكي يتخذ الجهاز قرارات للمستخدم تلقائيًا ، يحتاج الجهاز إلى الكثير من البيانات التاريخية والكثير من اتجاهات البيانات حول اختيار بيانات المستخدم اليدوي ، بحيث يتكيف الجهاز مع اختيارات المستخدم السابقة.

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

بافتراض وجود برنامج يقوم بتشغيل الخوارزمية باستخدام بنية بيانات الشجرة للوصول إلى نتيجة بناءً على مجموعة البيانات المحددة (في هذه الحالة ، تكون النتيجة أفضل فيلم ممكن). في البداية ، تبدأ بنية البيانات بأي بيانات يتم توفيرها لها. ثم يكرر البرنامج نفسه باستخدام كل جزء من البيانات ، ويصل إلى نتائج خاطئة بشكل متكرر. ولكن بمجرد أن يصل البرنامج إلى عدد كبير من التكرارات ، فإن ميله إلى استخلاص استنتاجات خاطئة سينخفض ​​لأنه سيكون لديه الآن إحصاءاته الخاصة (على سبيل المثال ، ما هي الفئة التي يشاهدها المستخدم أكثر ، وما هي أنواع الأفلام التي يتخطاها عادة ، وما هي أنواع الأفلام التي يتركها غير مكتمل ، وما إلى ذلك).

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

ملاحظة: ما ورد أعلاه هو مجرد بعض الأوصاف التي تسمح لنا بربط هيكل بيانات الشجرة بمواقف العالم الحقيقي وهذه مجرد فكرة عالية المستوى عن كيفية تطبيق هيكل بيانات الشجرة في التعلم الآلي أو اتخاذ القرار أو تنظيم الملفات في الجهاز.

تطبيقات أخرى لهيكل بيانات الشجرة

من بين الاستخدامات الأخرى لهيكل الشجرة ، يمكن ذكر ما يلي:

• الشجرة الهرمية (Heap Tree): نوع من الأشجار يستخدم للفرز الهرمي.
• شجرة البادئة (Trie) هي نسخة معدلة من الشجرة المستخدمة في توجيه المودم إلى معلومات جهاز التوجيه.
• يتم استخدام B-tree في بعض أنظمة إدارة قواعد البيانات.
• يستخدم المفسرون (Compiler) شجرات بناء الجملة للتحقق من بناء جملة البرنامج (التحليل السینتکس).