هياكل البيانات الأساسية
هياكل البيانات الأساسية هي الطرق المنظمة لتخزين البيانات والوصول إليها — المصفوفات، القوائم المرتبطة، جداول التجزئة، الأشجار، الأكوام وما شابهها — التي تحدد كفاءة العمليات المبنية عليها.
Definition
هيكل البيانات هو طريقة لتنظيم وتخزين البيانات بحيث يمكن تنفيذ العمليات المحددة بواسطة نوع البيانات المجرد الخاص بها بكفاءة؛ هياكل البيانات الأساسية هي المجموعة الصغيرة من الهياكل ذات الأغراض العامة التي تُبنى منها معظم الهياكل الأخرى.
Scope
يغطي هذا المجال أنواع البيانات المجردة (القوائم، القواميس، قوائم الانتظار ذات الأولوية، المجموعات) والهياكل الملموسة التي تنفذها، بالإضافة إلى تكلفة عملياتها الأساسية (الإدراج، الحذف، البحث، التحديث) في أسوأ الحالات والتحليل المخصص. ويتناول كيف يشكل اختيار الهيكل أداء الخوارزمية ويرتبط بنماذج التصميم وخوارزميات الرسوم البيانية والسلاسل التي تعتمد على هذه الهياكل. ويستثني هياكل تخزين قواعد البيانات وأنظمة الملفات التي يتم تناولها في مجالات فرعية أخرى.
Sub-topics
Core questions
- ما هو نوع البيانات المجرد الذي يحتاجه التطبيق، وما هو الهيكل الملموس الذي ينفذه على أفضل وجه؟
- ما هي تكاليف أسوأ الحالات والتكاليف المخصصة لكل عملية على هيكل معين؟
- كيف توازن الهياكل بين الذاكرة والوقت، أو سرعة القراءة وسرعة التحديث؟
- كيف يؤدي الحفاظ على ثابت (الترتيب، التوازن، خاصية الكومة) إلى تحديد تكاليف التشغيل؟
- متى يكون الهيكل البسيط مفضلًا على هيكل أسرع من الناحية التقريبية ولكنه أكثر تعقيدًا؟
Key concepts
- نوع البيانات المجرد
- المصفوفات والقوائم المرتبطة
- المكدسات وقوائم الانتظار
- جداول التجزئة
- أشجار البحث الثنائية
- الأشجار المتوازنة
- الأكوام وقوائم الانتظار ذات الأولوية
- التحليل المخصص
- مقايضات الوقت والمساحة
Key theories
- أنواع البيانات المجردة مقابل التطبيقات
- يحدد نوع البيانات المجرد العمليات ودلالاتها بشكل مستقل عن التمثيل؛ يمكن لهياكل بيانات ملموسة متعددة تنفيذ نفس نوع البيانات المجرد بملفات تعريف أداء مختلفة، مما يتيح للمصممين التفكير في الصحة والتكلفة بشكل منفصل.
- التحليل المخصص
- بعض الهياكل (المصفوفات الديناميكية، أشجار سبليه) لديها عمليات مكلفة عرضية ولكن عمليات رخيصة في المتوسط على مدى تسلسل؛ يحدد التحليل المخصص (الأساليب التجميعية، المحاسبية، المحتملة) هذا المتوسط التكلفة بدقة.
Clinical relevance
تُعد هياكل البيانات الأساسية اللبنات الأساسية لجميع البرامج تقريبًا: تدعم جداول التجزئة القواميس وفهارس قواعد البيانات، وتنظم الأشجار المتوازنة وأشجار B أنظمة الملفات وقواعد البيانات، وتدفع قوائم الانتظار ذات الأولوية المجدولات ومحاكاة الأحداث، وغالبًا ما يحدد الاختيار الصحيح للهيكل ما إذا كان النظام قابلًا للتوسع.
History
تم تصنيف هياكل البيانات التأسيسية في كتاب كنوت The Art of Computer Programming بدءًا من عام 1968. وقد وسعت الأشجار ذاتية التوازن (أشجار AVL، 1962؛ الأشجار الحمراء والسوداء وأشجار B في السبعينيات) والهياكل المتقدمة مثل أكوام فيبوناتشي وأشجار سبليه (الثمانينيات، ويرجع الفضل في ذلك إلى تارغان والمتعاونين معه) هذا المجال، بينما قدم التحليل المخصص وصفًا دقيقًا لأدائها.
Key figures
- Donald Knuth
- Robert Sedgewick
- Robert Tarjan
- Rudolf Bayer
Related topics
Seminal works
- knuth1997vol1
- cormen2009
- sedgewick2011
Frequently asked questions
- كيف أختار بين جدول تجزئة وشجرة بحث متوازنة؟
- توفر جداول التجزئة بحثًا وإدراجًا متوقعًا O(1) ولكن بدون ترتيب، بينما توفر أشجار البحث المتوازنة عمليات O(log n) وتحافظ على المفاتيح مرتبة، مما يدعم استعلامات النطاق والتنقل المرتب. اختر التجزئة لعمليات البحث عن المفاتيح البحتة وشجرة عندما يكون الترتيب أو عمليات النطاق مهمة.
- ماذا تعني التكلفة المخصصة لهيكل البيانات؟
- التكلفة المخصصة هي متوسط التكلفة لكل عملية على مدى تسلسل عمليات في أسوأ الحالات. على سبيل المثال، تدفع المصفوفة الديناميكية أحيانًا O(n) لتغيير الحجم ولكن متوسطها O(1) لكل إضافة لأن عمليات تغيير الحجم نادرة نسبيًا مقارنة بالإضافات الرخيصة.