شرح هياكل البيانات
كل برنامج يحفظ بياناته في مكان ما، وطريقة حفظها هي التي تحدد ما يكون سريعًا وما يكون بطيئًا. يمكن البحث في قائمة من مليون اسم اسمًا اسمًا، أو ترتيبها بحيث تكفي عشرون مقارنة للعثور على أي اسم. هياكل البيانات هي هذه الترتيبات: حفنة من الأفكار، أغلبها أقدم من الحاسوب الشخصي، موجودة داخل كل قاعدة بيانات ونظام تشغيل ومتصفح ولعبة.
ما فائدة بنية البيانات
تُختار بنية البيانات بحسب الأسئلة التي عليها أن تجيب عنها. يحتاج سجل مكالمات الهاتف إلى آخر مكالمة أولًا، وتحتاج مهام الطابعة إلى أقدمها أولًا، ويحتاج القاموس إلى معنى كلمة واحدة بين مئة ألف، ويحتاج مخطط الطرق إلى أقرب تقاطع لم يُزر بعد. تجعل كل بنية بعض العمليات سريعة على حساب غيرها، ويصف ترميز O الكبير هذه المقايضة: O(1) يعني أن الزمن لا يزيد مع عدد العناصر n، وO(log n) أن مضاعفة n تضيف خطوة واحدة، وO(n) أن الزمن يزيد بالتناسب مع n.
المكدّسات والطوابير والطوابير المزدوجة
يضيف المكدّس ويزيل من الطرف نفسه: آخر من يدخل أول من يخرج. سجلات التراجع وزر الرجوع واستدعاءات البرنامج قيد التشغيل كلها مكدّسات. ويضيف الطابور في الخلف ويزيل من الأمام: أول من يدخل أول من يخرج، مثل ضغطات لوحة المفاتيح أو طابور الطباعة. ويتيح الطابور المزدوج الأمرين من الطرفين. وتستغرق الثلاثة زمنًا ثابتًا لكل عملية. كثيرًا ما يُحفظ الطابور في مخزن دائري، وهو مصفوفة ثابتة يعود فيها الأمام والخلف إلى البداية بعد آخر خانة؛ وحين يمتلئ تُنسخ العناصر إلى مصفوفة ضعف حجمه. يكلّف النسخ O(n)، لكنه نادر إلى حد أن كل عملية تبقى في المتوسط O(1)، وهذا ما يسمى حدًا مستهلكًا.
القوائم المترابطة
تحفظ القائمة المترابطة كل قيمة في عقدة معها مؤشر إلى العقدة التالية. لا يغيّر الإدراج أو الحذف إلا مؤشرًا أو اثنين دون إزاحة أي شيء، لكن لا يمكن القفز إلى العقدة العاشرة: علينا اتباع الروابط من الرأس. تصل القائمة التي لا تعرف إلا رأسها إلى الذيل في O(n) خطوة؛ والقوائم الحقيقية تحفظ عادة مؤشر ذيل أيضًا، والقوائم مزدوجة الترابط مؤشرًا إلى الخلف، وهكذا يُبنى سجل المتصفح أو ذاكرة LRU المؤقتة.
أشجار البحث الثنائية
تحفظ شجرة البحث الثنائية عند كل عقدة القيم الأصغر في الشجرة الفرعية اليسرى والأكبر في اليمنى. يقارن البحث ثم يذهب يسارًا أو يمينًا، ويقرأ الاجتياز الترتيبي القيم مرتّبة. حذف الورقة هو إزالتها فحسب، والعقدة ذات الابن الواحد يحل محلها ذلك الابن، والعقدة ذات الابنين يحل محلها لاحقها الترتيبي، أي أصغر قيمة في شجرتها الفرعية اليمنى. ويستغرق ذلك كله زمنًا يتناسب مع ارتفاع الشجرة: نحو log n حين تكون كثيفة، لكنه n حين تصل القيم مرتّبة فتنحطّ الشجرة إلى قائمة.
أشجار AVL والحمراء-السوداء
تصلح الأشجار ذاتية التوازن شكلها بعد كل تغيير. تُبقي شجرة AVL، التي ابتكرها أديلسون-فيلسكي ولانديس عام 1962، الفرق بين ارتفاعَي الشجرتين الفرعيتين لكل عقدة واحدًا على الأكثر؛ وحين يبلغ عامل توازن عقدة ±2، يعيد دوران واحد (الحالتان LL وRR) أو دورانان (LR وRL) التوازن. وتلوّن الشجرة الحمراء-السوداء عقدها بحيث يكون الجذر أسود، ولا يكون لعقدة حمراء ابن أحمر، ويمر كل مسار نازل بالعدد نفسه من العقد السوداء، فلا يزيد أطول مسار على ضعف أقصرها. وهي تصلح نفسها بإعادة التلوين وبضعة دورانات على الأكثر، وهي الشجرة الموجودة داخل TreeMap في Java وstd::map في C++ ومجدول Linux.
الكومات وطوابير الأولويات
الكومة الثنائية شجرة ثنائية تامة محفوظة في مصفوفة بلا أي مؤشرات: ابنا الموضع i في 2i + 1 و2i + 2. في الكومة الصغرى لا يزيد أي أب على أبنائه، فتكون أصغر قيمة دائمًا في الجذر. توضع القيمة الجديدة في النهاية وتصعد متجاوزة الآباء الأكبر؛ وعند استخراج الجذر تُنقل القيمة الأخيرة إلى القمة ثم تنزل. كلتا العمليتين O(log n)، ويمكن تحويل مصفوفة كاملة إلى كومة في O(n). تشغّل الكومات طوابير الأولويات في أقصر مسارات ديكسترا ومحاكاة الأحداث ومجدولات أنظمة التشغيل، ومنها يأتي الترتيب بالكومة.
جداول التجزئة
يحوّل جدول التجزئة المفتاح إلى فهرس في مصفوفة بدالة تجزئة ويذهب إليه مباشرة. قد تقع مفاتيح مختلفة على الفهرس نفسه: هذا هو التصادم. يحفظ التسلسل قائمة صغيرة في كل دلو؛ أما العنونة المفتوحة، مثل الفحص الخطي، فتجرّب الخانات التالية حتى تجد خانة شاغرة، وعليها عند حذف مفتاح أن تترك شاهد قبر حتى يتابع البحث اللاحق الفحص. مع دالة تجزئة جيدة ومعامل تحميل (مفاتيح لكل دلو) يُبقى منخفضًا بتكبير الجدول، يكلّف الإدراج والبحث والحذف O(1) في المتوسط. أما الدالة الضعيفة، مثل جمع رموز حروف الكلمة، فترسل الكلمات المقلوبة إلى الدلو نفسه. وخلف dict في Python وكائنات JavaScript وفهارس قواعد البيانات جداولُ تجزئة.
أشجار البادئات واتحاد-بحث
تحفظ شجرة البادئات (trie) السلاسل بحرف واحد في كل مستوى، فتتشارك الكلمات ذات البداية الواحدة مسارًا، وتعلّم عقدةٌ موضع انتهاء الكلمة. يستغرق العثور على كلمة طولها L عدد L من الخطوات مهما كان عدد الكلمات المحفوظة، وكل الكلمات ذات البادئة الواحدة في شجرة فرعية واحدة؛ هكذا يعمل الإكمال التلقائي والمدقق الإملائي. ويحفظ اتحاد-بحث العناصر في مجموعات منفصلة، كل منها شجرة يسمّي جذرها المجموعة. يتبع Find روابط الأب حتى الجذر؛ ويعلّق Union جذرًا تحت آخر. ومع الاتحاد حسب الرتبة وضغط المسار، تكلّف السلسلة الطويلة من العمليات زمنًا شبه ثابت لكل عملية، هو دالة أكرمان العكسية α(n)، التي لا تتجاوز 4 لأي n واقعي. وعليها تعتمد خوارزمية كروسكال لشجرة الامتداد الصغرى.
الأسئلة المتداولة
ما الفرق بين المصفوفة والقائمة المترابطة؟
تحفظ المصفوفة عناصرها متجاورة في الذاكرة، فيمكن الوصول إلى أي موضع فورًا، لكن الإدراج في الوسط يعني إزاحة كل ما بعده. ويمكن للقائمة المترابطة أن تدرج في أي مكان بتغيير المؤشرات، لكن الوصول إلى موضع يعني السير من الرأس. كما تستفيد المصفوفات من ذاكرة المعالج المؤقتة أكثر بكثير، ولهذا تكون في التطبيق عادة أسرع.
ماذا يعني الزمن المستهلك؟
متوسط الكلفة لكل عملية على سلسلة طويلة، حتى لو كانت عملية منفردة مكلفة أحيانًا. المخزن الدائري الذي يتضاعف حين يمتلئ ينسخ أحيانًا العناصر الـ n كلها، لكن لأن النسخ يقلّ كلما كبر المخزن، تكلّف n إضافة O(n) إجمالًا، أي O(1) لكل إضافة في المتوسط.
هل الكومة هي نفسها شجرة البحث الثنائية؟
لا. تضع شجرة البحث الثنائية كل شجرة فرعية يسرى قبل عقدتها وكل يمنى بعدها، فتستطيع سرد القيم كلها بالترتيب والعثور على أي قيمة بسرعة. أما الكومة فلا تعد إلا بأن يأتي كل أب قبل أبنائه، وهذا يكفي للعثور على الأصغر أو الأكبر فورًا، لكنه لا يكفي للبحث عن قيمة عشوائية.
كيف يعرف اتحاد-بحث أن عنصرين متصلان؟
يتبع روابط الأب من كل عنصر حتى جذر شجرته. فإن وصل كلاهما إلى الجذر نفسه فهما في المجموعة نفسها. ثم يجعل ضغط المسار كل عقدة على الطريق تشير مباشرة إلى الجذر، فيستغرق السؤال التالي عنهما خطوة واحدة.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
افتح مُصوِّر هياكل البيانات