| العملية | المتوسط | أسوأ حالة |
|---|
* مُستهلَك: متوسط على سلسلة طويلة من العمليات
مُصوِّر هياكل البيانات
بنية البيانات طريقة لحفظ البيانات بحيث تُجاب الأسئلة الأكثر تكرارًا بسرعة. اختر واحدة من إحدى عشرة بنية كلاسيكية، من المكدّس إلى الشجرة الحمراء-السوداء، واكتب قيمة، ثم اضغط عملية. تجري كل خطوة على الشاشة: أي عقدة تُقارَن، وأي رابط يتغيّر، ولماذا تدور شجرة أو تصعد قيمة، مع جملة تسمّي ما يحدث. تعدّ البطاقات عمل كل عملية، ويعطي جدول زمن تنفيذها. اختر بنية، واكتب قيمة، ثم اضغط عملية. تُعرض كل عملية خطوة بخطوة: تُبيّن العقد المميّزة ما يُقارَن أو يُنقَل أو يتغيّر، ويقول السطر أسفل الصورة ما يحدث ولماذا. يتيح لك «رجوع» و«خطوة» و«تشغيل» و«النهاية» المرور على الخطوات مجددًا. «ملء عشوائي» و«مسح» يبدآن من جديد، و«تراجع» يلغي عملية. تعرض البطاقات الحجم وارتفاع الأشجار وعمل العملية الأخيرة (المقارنات أو المحاولات أو روابط الأب المتّبعة) ورقمًا مهمًا للبنية؛ ويعطي الجدول زمن تنفيذ كل عملية.
كيف يعمل
- اختر بنية، مثل شجرة بحث ثنائية أو جدول تجزئة أو شجرة بادئات. تبدأ بمحتوى عشوائي؛ و«ملء عشوائي» و«مسح» يبدآن من جديد.
- اكتب قيمة واضغط عملية: دفع، إدخال في الطابور، إدراج، حذف، بحث، اجتياز، union أو find. تُعرض الخطوات وحدها؛ و«رجوع» و«خطوة» و«تشغيل» و«النهاية» تمرّ عليها مجددًا.
- اقرأ في السطر أسفل الصورة ما تفعله كل خطوة، وتابع في البطاقات الحجم والارتفاع وعمل العملية الأخيرة، وقارن أزمنة التنفيذ في الجدول.
القوائم والمكدّسات والطوابير
تحفظ أبسط البنى العناصر في صف. يعمل المكدّس من طرف واحد فقط، فآخر عنصر يدخل هو أول من يخرج، مثل كومة صحون؛ ويضيف الطابور في الخلف ويُخرج من الأمام، مثل صف أمام شبّاك. يعيش الطابور هنا في مخزن دائري: يدور الأمام والخلف حول مصفوفة ثابتة ويعودان إلى أولها بعد آخرها، وحين يمتلئ تُنسخ العناصر إلى مخزن ضعف حجمه. تربط القائمة المترابطة العقد بمؤشرات، فالإدراج في الرأس لا يكلّف شيئًا تقريبًا، لكن العثور على الذيل أو على فهرس يتطلب اتباع الروابط واحدًا تلو الآخر.
الأشجار والكومات وجداول التجزئة والمجموعات
تحفظ شجرة البحث الثنائية القيم الأصغر يسارًا والأكبر يمينًا، فيُنصّف البحث عدد المرشحين في كل خطوة ما دامت الشجرة كثيفة. وتضمن أشجار AVL والحمراء-السوداء ذلك بدورانات يمكنك مشاهدتها وتحمل أسماء حالاتها. ولا تحفظ الكومة في القمة إلا القيمة الأصغر أو الأكبر، وهذا كل ما يحتاجه طابور الأولويات. ويقفز جدول التجزئة مباشرة إلى دلو يُحسب من المفتاح وعليه أن يتعامل مع التصادمات؛ وتتشارك شجرة البادئات بدايات الكلمات؛ ويخبرك اتحاد-بحث في زمن شبه ثابت هل ينتمي عنصران إلى المجموعة نفسها.
الأسئلة المتداولة
أي بنية بيانات ينبغي أن أستخدم؟
يتوقف ذلك على الأسئلة التي تطرحها أكثر من غيرها. مكدّس أو طابور حين تُعالج العناصر بترتيب وصولها أو بعكسه؛ وجدول تجزئة للبحث عن مفتاح؛ وشجرة بحث متوازنة مثل AVL أو الحمراء-السوداء حين تحتاج أيضًا إلى المفاتيح مرتّبة أو إلى أقرب مفتاح؛ وكومة حين لا تحتاج إلا إلى أصغر عنصر أو أكبره؛ وشجرة بادئات للكلمات والبادئات؛ واتحاد-بحث لتتبّع مجموعات تندمج.
ما الفرق بين شجرة AVL والشجرة الحمراء-السوداء؟
كلتاهما تُبقي شجرة البحث الثنائية ضحلة، فيستغرق كل بحث وإدراج وحذف زمنًا يتناسب مع log n. شجرة AVL متوازنة بصرامة أكبر، إذ لا يزيد الفرق بين ارتفاعَي جانبَي كل عقدة على واحد، فيكون البحث أسرع قليلًا. أما الشجرة الحمراء-السوداء فتسمح بمرونة أكبر وتحتاج إلى دورانات أقل عند التغيير، ولهذا تستخدمها مكتبات قياسية كثيرة لخرائطها ومجموعاتها المرتّبة.
لماذا قد يكون جدول التجزئة بطيئًا في أسوأ الحالات؟
إذا وقعت مفاتيح كثيرة في الدلو نفسه، فعلى البحث أن يفحصها واحدًا واحدًا، تمامًا كما في القائمة. تنشر دالة التجزئة الجيدة المفاتيح بالتساوي، ويكبر الجدول قبل أن يزدحم كثيرًا، فيستغرق البحث في المتوسط زمنًا ثابتًا. جرّب جدولًا حجمه 10 مع أعداد تنتهي بالرقم نفسه، أو كلمات مقلوبة بعضها من بعض، وشاهد التصادمات تتراكم.
ماذا تعني الأرقام بجانب عقد AVL؟
إنها عوامل التوازن: ارتفاع الشجرة الفرعية اليسرى للعقدة ناقص ارتفاع اليمنى. في شجرة AVL يجب أن يكون كل عامل توازن −1 أو 0 أو +1. وحين يجعل إدراجٌ أو حذفٌ أحدها +2 أو −2، تدور الشجرة عند تلك العقدة؛ وتخبرك الحالة (LL أو RR أو LR أو RL) إلى أي جهة يميل الارتفاع الزائد، وتحدد هل يلزم دوران واحد أم اثنان.
هل يُرسَل أي شيء إلى خادم؟
لا. تعمل كل عملية في متصفحك، ويُحفظ محتوى كل بنية في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر