كيف لا يكون الحيرة من قبل الأشجار

تحويل تلك الشجرة رأسا على عقب!

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

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

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

ينمو أي نوع من الفروع التي تريدها!

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

هياكل البيانات الخطية في البرية

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

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

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

تتكون الأشجار - مثل القوائم المرتبطة - من العقد والروابط.

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

تحديد أجزاء من هيكل بيانات الشجرة

فيما يلي بعض المصطلحات الجيدة لمعرفة متى يتعلق الأمر بالحديث عن الأشجار:

  • الجذر: العقدة العليا للشجرة ، والتي لا تحتوي على أي روابط أو حواف متصلة بها
  • الرابط / الحافة: هو المرجع الذي تحتويه العقدة الأصل والتي تخبرها ما هي العقدة التابعة لها
  • تابع: أي عقدة لها عقدة أصلية مرتبطة بها
  • الأصل: أي عقدة لها مرجع أو رابط إلى عقدة أخرى
  • الأخوة: أي مجموعة من العقد هي أولاد العقد نفسها
  • داخلي: أي عقدة تحتوي على عقدة تابعة (جميع العقد الأصل بشكل أساسي)
  • الورقة: أي عقدة ليس لها عقدة فرعية في الشجرة

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

وطالما أنه يمكنك تذكر أن البيانات ذات طبيعة هرمية ، يجب أن يكون المصطلح أقل تقلقًا في التفكير.

قل الحقيقة (الشجرة)

بغض النظر عن الشكل الذي تبدو عليه الشجرة ، أو عدد فروعها أو أوراقها ، أو حجم نموها ، فهناك بعض "حقائق الأشجار" العالمية التي تجعل نفسها بديهية.

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

حقائق شجرة: سيكون للشجرة دائمًا رابط أقل من العدد الإجمالي للعقد

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

إذا كانت الشجرة تحتوي على عقد n ، فسيكون لها دائمًا عدد أقل من الحواف (n-1).

وإذا ألقينا نظرة على الشجرة ، فسيبدأ توضيح سبب ذلك. العقدة الجذرية هي عقدة لا يمكن أن يكون لها أي أبوين. لذلك ، لا يمكن أن يكون هناك أي شيء يشير إليه. إذا كان يجب أن تحتوي كل عقدة على عقدة أخرى تشير إليها عبر رابط / حافة (باستثناء العقدة الجذرية) ، فيمكننا دائمًا التأكد من أن مجموعتنا سيكون لها روابط n-1 عندما يكون n هو العدد الإجمالي للعقد في الشجرة. كم هو رائع (وقوي!) أنه يمكننا معرفة تلك المعلومات بسهولة ، دون الحاجة إلى عبور الشجرة ؟!

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

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

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

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

كم يبلغ طول شجرتك؟

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

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

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

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

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

عمق وارتفاع العقدة على بنية بيانات شجرة

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

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

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

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

الأشجار المتوازنة مقابل الأشجار غير المتوازنة

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

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

اكتشاف جذور الشجرة

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

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

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

وللتفكير ، كنا جميعا نقع تحت ظل الشجرة لفترة طويلة وليس لدينا أي فكرة.

مصادر

إذا كنت من عشاق الأشجار ، أو من عشاق الأشجار ، أو كنت ترغب فقط في معرفة المزيد ، فراجع هذه الروابط المفيدة!

  1. هياكل البيانات: مقدمة إلى الأشجار ، mycodeschool
  2. هياكل البيانات: الأشجار ، HackerRank
  3. الأشجار ، البروفيسور جوناثان كوهين
  4. هياكل بيانات الشجرة ، الأستاذ ديفيد شميدت
  5. موازنة الأشجار ، أستاذ ر. كلايتون