Get best of the week

أشجار حمراء سوداء في جافا سكريبت

صورة

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

ابحث عن الحلول الموجودة


كان الهدف الرئيسي من الفكرة هو فهم تنفيذ الخوارزمية وتصورها. كانت الخطوة الأولى هي البحث عن تنفيذ مع تفسيرات كاملة ومفهومة ورمز شبيبة. في عملية البحث ، كان من المحزن أن المؤلفين في بعض الأحيان لم يكتملوا المصدر ، على سبيل المثال ، هناك خوارزمية الإدراج ، ولكن لا يوجد حذف. أو يقومون بتصور مثل هذا ، لكنهم لا يقدمون روابط للمصدر. ثم وجدت هذا المقال الممتاز. ولكن على الأقل قتل ، ما زلت لا أفهم لماذا أدخل المؤلف الرمز بالصور ولم يقدم رابطًا إلى شفرة المصدر عند الطلب في التعليقات. هناك أيضًا حزمة npm red-black-tree ، والشفرة المصدر الكاملة لها هي: "قيد التقدم ..." في الملف التمهيدي. وجد أيضًا تنفيذًا شائعًا أشجار حمراء سوداء على شبيبة ، والتي تعتمد عليها الكثير من الحزم وملايين التنزيلات في الأسبوع ، ولكن الرمز موجود منذ خمس سنوات.

تحديد الأولويات وتحديد المهام


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

معنى أشجار حمراء سوداء


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

More articles:


All Articles