الشجرة البيانية من أهم مفاهيم الخوارزميات

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

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

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

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

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

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

أما الرؤوس (د)، (ر)،(ه) و (و) فتسمى أوراق و أي رأس لا يحوي على أي بناء يسمى ورقة.

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

المسار من الرأس الي الرأس الاخر هو مجموعه الحواف التي تأخذك من الرأس الي الرأس الاخر. إذاً ما هو طول المسار؟ طول المسار من الرأس الي الرأس الآخر : هي عدد الحواف التي نسلكها من الرأس لنصل الي الرأس الاخر.

من الشكل أعلاه طول المسار من الرأي (أ) الي الرأس (د) =2 .

لنرجع لتعريف ما هو عمق الرأس؟

عمق الرأس : هو عدد الحواف التي تربط الرأس بالجذر، ونستنتج ان عمق الجذر= 0، وأن أكبر عمق هو عمق الأوراق، وعمق الشجرة هي عدد الحواف من الجذر إلى أبعد ورقة، ونستنتج أن عمق الإبن أكبر من عمق أبيه – عكس الحقيقة طبعا 🙂 .

إرتفاع الرأس : إرتفاع الرأس هو عدد الحواف من الرأس نفسه إلى أبعد ورقة مرتبط بها، وإرتفاع الشجرة هو عدد الحواف من الجذر الي أبعد ورقة، نستنتج أن إرتفاع الأوراق =0 .

هذه هي الأساسيات يجب معرفتها عن الشجرة البيانية، هل هذا كل شيء ؟ ليس بعد، فلتعلم ان هنالك أنواع عديدة للشجرة البيانية أهمها:

AVL Tree، B+ Tree، B- Tree، Red _Black Tree، Binary Tree

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

الشجرة الثنائية التامةفي هذا النوع كل رأس ما عدا الأوراق يملك إبنان إثنان، وكل الأورق لها نفس الإرتفاع، الآن هل تخيلت كيف يكون شكل هذه الشجرة ؟ إذا كانت الشجرة التامة مكونة من (ن) رأس ما هو الارتفاع ؟ ستجد أن إرتفاع الشجرة سيكون مساوي ل (لـــو(ن) للأساس 2) إذا كان لدينا كسر فنأخذ أقرب عدد صحيح أقل من الكسر، جرب ذلك بنفسك لشجرة تحوي 7 رؤوس .

الشجرة الثنائية الخطيةهذا النوع كل رأس أو عقده يمتلك إبن واحد فقط. تخيل كيف يكون شكل هذه الشجرة إذا كان لها عدد (ن) من الرؤوس فما هو إرتفاعها . قد سميت خطيه لأن كل الرؤوس في خط واحد، وارتفاعها = ن-1، جرب ان ترسم شجره خطية من 5 عقد أو رؤوس ستجد أن إرتفاع الشجرة هو 4 .

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

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

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

شجرة البحث الثنائيةهي شجرة ثنائية لكن مع ترتيب قيم الرؤوس بطريقة معينة . ما هي الطريقة؟

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

شجرة بحث
شجرة بحث

ولماذا سميت شجرة بحث؟ سميت شجرة بحث لأنها تسهل عملية البحث بصورة كبيرة جدا .

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

هكذا تعلمت كيف تسهل شجرة البحث الثنائية عناء البحث .

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

سامي محمد آدم

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

‫8 تعليقات

  1. سلام عليكم تحية طيبة الى العاملين على هذة المدونة الجيدة
    سوالي هو اني محتاج الى تمثيل العلاقات الرياضية في شجرة بحث مثلا y=a*b/(e-d)*c ولكم مني جزيل الشكر والامتنان

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

  2. مهتمة جدا بشجرة ذات الحدين حيث اننى رسمت رسمه متعلق بقانون ذات الحدين وخرجت منه بشجره بالفعل وكان ذلك منذ اكثر من سنتين فى بحثى عن اصل e : euler number e=2.71828..,والذى من وجة نظرى هو اصل لجميع العلوم على الارض المبنى على الواحد الصحيح وفوائده المركبة زمنيا ..والان اعاود قراءة كل موضوع متعلق بهذه الشجره فاجد توصيفا له جيد هنا وفى ماده Data Structureخاصة بعد أن قررت الدخول لهذا المجال- مجال البرمجه- وشجعنى اكثر استكمال بحثى بعد ان علمت ان البرمجه بأى لغة كانت أساسها الهياكل البيانيه .. شكرا على تبسيط وتوضيح المعلومات . استمتعت كثيرا برؤيه ما ابحث عنه هنا واضحا . شكرا جزيلا .

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

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

مقالات ذات صلة

زر الذهاب إلى الأعلى
إغلاق