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

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

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

شرح التعريف:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ختاماً:

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