[Powered by Google Translate] كيف تمثل كل أفراد عائلتك في الكمبيوتر؟
يمكننا ببساطة استخدام قائمة،
ولكن هناك تسلسل هرمي واضح هنا.
>> دعونا نقول اننا بدأنا مع جدته، عظيم بك، أليس.
لديها 2 أبناء، بوب
وجدك، تشارلي.
تشارلي لديه 3 أطفال،
عمك، ديف، عمتك، حواء، والدك، فريد.
كنت الطفل الوحيد فريد.
>> لماذا تنظيم أفراد عائلتك بهذه الطريقة
أن يكون أفضل من تمثيل قائمة بسيطة؟
أحد الأسباب هو أن هذه البنية الهرمية،
يسمى 'شجرة' على مزيد من المعلومات من قائمة بسيطة.
نحن نعرف العلاقات الأسرية بين الجميع
فقط من خلال دراسة شجرة.
أيضا، يمكن أن تسرع
نظرة من الزمن بشكل كبير، إذا يتم فرز البيانات شجرة.
>> لا يمكننا الاستفادة من ذلك هنا، ولكن سنرى مثال على ذلك قريبا.
يتم تمثيل كل شخص من عقدة على الشجرة.
يمكن يكون العقد العقد التابعة
فضلا عن العقدة الأصل.
هذه هي المصطلحات الفنية،
حتى عند استخدام الأشجار لأشياء إلى جانب الأسر.
عقدة أليس يوجد 2 الأطفال والآباء والأمهات لا،
بينما عقدة تشارلي لديه 3 أطفال والوالدين 1.
>> A عقدة طرفية واحد هو أن ليس لديها أي الأطفال
على الحافة الخارجية من شجرة.
العقدة أعلى من شجرة، العقدة الجذر،
لا يوجد لديه الأصل.
>> شجرة ثنائية هو نوع معين من الشجرة،
الذي لديه كل عقدة، على الأكثر، 2 الأطفال.
هنا هو البنية عقدة من شجرة ثنائية في C.
كل عقدة لديه بعض البيانات المرتبطة بها
و 2 مؤشرات إلى العقد الأخرى.
>> في شجرة عائلتنا،
كان اسم كل البيانات المرتبطة الشخص.
هنا وهو الباحث، على الرغم من أنه يمكن أن يكون أي شيء.
كما اتضح،
وشجرة ثنائية لا يمكن أن يكون تمثيل جيد للأسرة،
لأن الناس كثيرا ما يكون الأطفال أكثر من 2.
>> شجرة ثنائية البحث
هو خاص، ونوع من أمر شجرة ثنائية
الذي يسمح لنا أن ننظر إلى القيم بسرعة.
ربما لاحظتم
أن كل عقدة تحت جذر شجرة
يسمى جذر شجرة أخرى، وقال 'الشجرة الفرعية ".
هنا، جذر الشجرة هو 6،
والاطفال و2، هو جذر شجرة فرعية.
>> في شجرة البحث الثنائية
كل القيم من عقدة الشجرة الفرعية الحق
أكبر من القيمة للعقدة. هنا: 6.
حسنا، القيم في الشجرة الفرعية عقدة اليسرى
هي أقل من القيمة للعقدة.
إذا نحن بحاجة للتعامل مع قيم مكررة،
يمكننا تغيير أي من هذين إلى عدم المساواة فضفاضة،
يعني القيم مماثلة يمكن أن تقع إما على اليمين أو اليسار،
ما دمنا تتفق حول هذا الموضوع طوال الوقت.
هذه الشجرة هي شجرة البحث الثنائية
لأنه يتبع هذه القواعد.
>> هذه هي الطريقة التي سينظر إذا لجأنا إلى كافة العقد البنيات C.
إذا لاحظت أن الطفل مفقود،
مؤشر فارغ.
كيف يمكننا التحقق لمعرفة ما إذا 7 هو في شجرة؟
نبدأ من جذورها.
سبعة أكبر من 6، لذلك إذا كان في شجرة، يجب أن يكون إلى اليمين.
ثم، من أقل من 8، لذلك يجب أن يترك.
هنا، لقد وجدنا 7.
الآن، سنقوم تحقق من وجود 5.
خمسة هو أقل من 6، لذلك يجب أن تكون إلى اليسار.
خمسة أكبر من 2،
لذلك يجب أن يكون على حق،
وأنه هو أيضا أكبر من 4، لذلك يجب أن يكون الحق مرة أخرى.
ومع ذلك، ليس هناك طفل هنا.
مؤشر فارغ.
هذا يعني أن 5 ليس لدينا في شجرة.
>> يمكننا البحث في شجرة ثنائية مع التعليمات البرمجية التالية:
في كل عقدة، ونحن تحقق لمعرفة ما إذا كنا قد وجدت
القيمة نحن نبحث عن.
إذا لم نجد ذلك، فإننا تحديد ما إذا كان ينبغي أن يكون
وعلى اليسار أو اليمين تأكد من أن الشجرة الفرعية.
وسوف تستمر هذه الحلقة أسفل الشجرة
حتى لا تكون عقدة تابعة على اليسار أو اليمين إما.
>> تذكر أن 5 لم يكن في الشجرة.
كيف يمكننا إدراج ذلك؟
عملية تبدو مشابهة للبحث.
نحن تكرار أسفل الشجرة بدءا من 6،
من اليسار إلى 2،
الحق إلى 4،
ومرة أخرى الحق، لكن 4 لا يوجد لديه طفل في هذا الجانب.
وسوف يكون هذا الموقف الجديد لل5،
وسوف تبدأ مع عدم وجود أطفال.
>> مدى السرعة هي عمليات على شجرة البحث الثنائية؟
تذكر أن Bigohnotation تسعى لتوفير الحد الأعلى.
في أسوأ الحالات،
يمكن أن يكون لدينا ببساطة شجرة قائمة مرتبطة
وهذا يعني أن الإدراج أو الحذف، والبحث
يمكن أن يستغرق وقتا طويلا يتناسب مع عدد العقد في الشجرة.
هذا هو O (N).
>> على سبيل المثال، ما يلي هو البحث الثنائي صالح شجرة.
ومع ذلك، إذا كنا في محاولة لايجاد 9،
علينا أن تجتاز كل عقدة.
فإنه ليس أفضل من قائمة مرتبطة.
من الناحية المثالية، فإننا نريد كل عقدة
لدينا ثنائي شجرة بحث لدينا 2 الأطفال.
بهذه الطريقة، الإدراج، والحذف والبحث
وتتخذ، في أسوأ الأحوال، O (سجل ن) مرة.
يمكن للشجرة من قبل أن يكون أكثر توازنا،
مثل هذا.
الآن، وتبحث عن أي قيمة يأخذ، على الأكثر، 3 خطوات.
هذه الشجرة متوازنة،
معنى هذا هو الحد الأدنى لها عمق
نسبة إلى عدد العقد.
>> تبحث عن القيمة في شجرة ثنائية متوازنة البحث
يشبه البحث الثنائية على مجموعة فرزها.
في الواقع، إذا نحن لسنا بحاجة لإدراج أو حذف البنود،
يتصرفون تماما بنفس الطريقة.
ومع ذلك، فإن هيكل الشجرة هو أفضل
لمعالجة الإدراج والحذف
>> اسمي Bannus فان دير Kloot.
هذا هو CS50.