ما هو اسم بنية البيانات التي تبدو مثل دبابيس البولينج؟

Question

بادئ ذي بدء ، آسف على العنوان. شخص ما الرجاء اقتراح واحد أفضل ، لم أكن أعرف حقًا كيفية التعبير عن سؤالي بشكل صحيح.

في الأساس ، أنا أبحث فقط عن اسم بنية البيانات حيث تبدو العناصر مثل هذا (تجاهل النقاط):

......5

....3...2

..4...1...6

9...2...3...1

اعتقدت أولاً أنه يمكن أن يكون نوعًا معينًا من "شجرة" ، ولكن ، كما تقول ويكيبيديا:

الشجرة هي [...] رسم بياني متصل بحشي حيث تحتوي كل عقدة على عقد صفر أو أكثر على الأكثر عقدة الوالدين

نظرًا لأنه يمكن أن يكون هناك أكثر من أحد الوالدين عن طريق العقدة في بنية البيانات التي أبحث عنها ، فربما لا تكون شجرة.

لذا ، هذا سؤالي:

ما هو اسم بنية البيانات التي يمكن أن تمثل البيانات مع الروابط التالية بين العناصر؟ (/ و كونها الروابط ، مرة أخرى ، تجاهل النقاط):

......5

...../..\

....3...2

.../..\./..\

..4...1...6

../.\./..\./..\

9...2...3...1

Answer 1

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

بادئ ذي بدء ، آسف على العنوان. شخص ما الرجاء اقتراح واحد أفضل ، لم أكن أعرف حقًا كيفية التعبير عن سؤالي بشكل صحيح.

العنوان على ما يرام ، لقد صعبة عندما فتحت السؤال. سأبدأ في وصفهم "دبابيس البولينج" الآن :)

      5

    3   2

  4   1   6

9   2   3   1

Answer 2

الشيء الأكثر شعبية الذي أظن أنه تم وضعه على هذا النحو مثلث باسكال. إنه الهيكل المستخدم للحساب معاملات ذات الحدين; ؛ كل عقدة هي مجموع والديها:

http://info.ee.surrey.ac.uk/personal/l.wood/publications/msc-thesis/fig36.gif.

usuallly ، عندما يتعلق الأمر بتنفيذ هذه الخوارزميات (يشار إلى هذه الفئة عادة "البرمجة الديناميكية") ، عادة ما يتم تمثيل هذا "الهيكل" كصفيف ثنائي الأبعاد بسيط. نرى هنا, ، فمثلا:

n\k  0  1  2  3  4
------------------
0    1  0  0  0  0 
1    1  1  0  0  0 
2    1  2  1  0  0 
3    1  3  3  1  0 
4    1  4  6  4  1 
5    1  5 10 10  5 
6    1  6 15 20 15

أعتقد أنه لا يوجد اسم رسمي لمثل هذا الهيكل ، ولكن في البرمجة الديناميكية مثل هذه الأشياء فقط ... صفائف.

لكن من الآن فصاعدًا Nulluserexception وتقترح أنا أسميها تمامًا "دبابيس البولينج" :-)

Answer 3

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

Answer 4

نظرًا لأنه يمكن أن يكون هناك أكثر من أحد الوالدين عن طريق العقدة في بنية البيانات التي أبحث عنها ، فربما لا تكون شجرة.

ما تبحث عنه ربما رسم بياني. أ شجرة هي حالة خاصة من الرسم البياني حيث يكون لكل عقدة والد واحد بالضبط. (باستثناء الجذر الذي يحتوي على لا شيء)