شجرة الأصابع

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

ملخص

شجرة الأصابع تُستخدم كطابور بسيط مع عمليات إدخال وإخراج ذات تعقيد زمني ثابت O(1). تُضاف الأعداد الصحيحة من 1 إلى 21 من اليمين وتُستخرج من اليسار. تمثل المربعات القيم، ويمكن أن يحتوي "الرقم" (أزرق سماوي) على 1-4 أبناء، ويمكن أن يحتوي "العقدة" (أزرق داكن) على 2-3 أبناء، والدائرة البيضاء للقيمة "الفارغة"، وتمثل العقدة الحمراء قيمة "مفردة"، وتمثل العقد الخضراء قيم "عميقة". لاحظ أنه مع كل خطوة ننزلها في العمود الفقري، تتداخل القيم المفردة والأرقام مع مستوى جديد من العقد.

يذكر رالف هينز وروس باترسون أن شجرة الأصابع هي تمثيل وظيفي للتسلسلات المستمرة التي يمكن الوصول إلى نهاياتها في وقت ثابت مُعدَّل. ويمكن إجراء عمليات الربط والتقسيم في وقت لوغاريتمي بالنسبة لحجم الجزء الأصغر. كما يمكن تحويل هذا الهيكل إلى بنية بيانات عامة الأغراض من خلال تعريف عملية التقسيم بصيغة عامة، مما يسمح له بالعمل كتسلسل، أو قائمة انتظار ذات أولوية، أو شجرة بحث، أو قائمة انتظار بحث ذات أولوية، بالإضافة إلى أنواع أخرى من أنواع البيانات المجردة. ^{[ 1 ]}

الإصبع هو نقطة يمكن من خلالها الوصول إلى جزء من بنية البيانات؛ في لغات البرمجة الإجرائية، يُطلق عليه اسم المؤشر. ^{[ 2 ]} في شجرة الأصابع، تُمثل الأصابع هياكل تشير إلى نهايات التسلسل، أو العقد الطرفية. تُضاف الأصابع إلى الشجرة الأصلية لضمان الوصول إليها في وقت ثابت. في الصور الموضحة أدناه، تُمثل الأصابع الخطوط الممتدة من العمود الفقري إلى العقد.

تتكون شجرة الأصابع من طبقات مختلفة يمكن تمييزها من خلال العقد الموجودة على طول محورها . يمكن اعتبار محور الشجرة بمثابة الجذع، تمامًا كما أن للأشجار أوراقًا وجذرًا. على الرغم من أن أشجار الأصابع تُصوَّر غالبًا بمحور وفروع تتفرع من الجانبين، إلا أن هناك في الواقع عقدتين على المحور في كل مستوى، مُقترنتين لتشكيل هذا المحور المركزي. تقع البادئة على يسار المحور، بينما تقع اللاحقة على يمينه. ترتبط كل عقدة من هذه العقد بالمستوى التالي من المحور حتى تصل إلى الجذر. ^{[ 2 ]}

يحتوي المستوى الأول من الشجرة على القيم فقط، وهي العقد الورقية للشجرة، وعمقه صفر. المستوى الثاني عمقه واحد، والثالث عمقه اثنان، وهكذا. كلما اقتربنا من الجذر، زاد عمق الأشجار الفرعية للشجرة الأصلية (الشجرة قبل أن تصبح شجرة أصابع) التي تشير إليها العقد. وبهذه الطريقة، يكون النزول في الشجرة بمثابة الانتقال من الأوراق إلى جذر الشجرة، وهو عكس بنية بيانات الشجرة التقليدية. للحصول على هذه البنية المميزة وغير المألوفة، يجب التأكد من أن الشجرة الأصلية ذات عمق موحد. ولضمان توحيد العمق، عند تعريف كائن العقدة، يجب تحديد نوع العقدة الفرعية. تشير العقد الموجودة على العمود الفقري بعمق واحد وما فوق إلى أشجار، وبهذا التحديد يمكن تمثيلها بواسطة العقد المتداخلة. ^{[ 3 ]}

تحويل شجرة إلى شجرة إصبعية

سنبدأ هذه العملية بشجرة متوازنة من 2 إلى 3 فروع . ولكي تنجح شجرة الأصابع، يجب أن تكون جميع العقد الورقية مستوية أيضًا.

الإصبع هو "بنية توفر وصولاً فعالاً إلى عُقد الشجرة القريبة من موقع مميز". ^{[ 1 ]} لإنشاء شجرة أصابع، نحتاج إلى وضع أصابع على طرفي الشجرة الأيمن والأيسر وتحويلها كما لو كانت سحابًا . وهذا يمنحنا وصولاً ثابتًا ومُستهلكًا إلى نهايات التسلسل.

للتحول، ابدأ بالشجرة المتوازنة 2-3.

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

يجمع الأشواك لتكوين شجرة قياسية مكونة من 2-3 أصابع.

يمكن وصف ذلك على النحو التالي: ^{[ 1 ]}

بيانات FingerTree a = فارغة | مفردة a | عميقة ( رقم a ) ( FingerTree ( عقدة a )) ( رقم a )بيانات العقدة أ = العقدة 2 أ أ | العقدة 3 أ أ أ

الأرقام في الأمثلة الموضحة هي العقد التي تحتوي على حروف. تُقسّم كل قائمة حسب البادئة أو اللاحقة لكل عقدة على العمود الفقري. في شجرة 2-3 المُحوّلة، يبدو أن قوائم الأرقام في المستوى الأعلى قد يكون طولها اثنين أو ثلاثة، بينما يكون طول قوائم المستويات الأدنى واحدًا أو اثنين فقط. ولضمان كفاءة بعض تطبيقات أشجار الأصابع، تسمح هذه الأشجار بوجود ما بين شجرة فرعية واحدة وأربع أشجار فرعية في كل مستوى.

يمكن تحويل أرقام شجرة الأصابع إلى قائمة على النحو التالي: ^{[ 1 ]}

نوع الرقم أ = واحد أ | اثنان أ أ | ثلاثة أ أ أ | أربعة أ أ أ أ

وهكذا، في الصورة، يحتوي المستوى الأعلى على عناصر من النوع أ ، ويحتوي المستوى التالي على عناصر من النوع العقدة أ لأن العقدة تقع بين العمود الفقري والأوراق، وهذا يعني بشكل عام أن المستوى النوني من الشجرة يحتوي على عناصر من النوع $Node^{n}$ a ، أو شجرتين أو ثلاث شجرات بعمق n. هذا يعني أن سلسلة من n عنصرًا تُمثَّل بشجرة بعمق Θ(log n ). والأفضل من ذلك، أن العنصر الذي يقع على بُعد d من أقرب طرف يُخزَّن على عمق Θ(log d) في الشجرة. ^{[ 1 ]}

يمكن تطبيق هذه العملية أيضاً على أشجار أخرى، مثل شجرة 2-3-4 على اليمين. وهذا يُساعد على إدراك أن الأرقام هي في الواقع التعليقات التوضيحية الموجودة داخل الشجرة، وأن كل رقم مرتبط مفهومياً بشجرة فرعية قد تكون فارغة.

تخفيضات

${\begin{aligned}\mathrm {instance} &\ Reduce\ Node\ \mathrm {where} &&\\&reducer\ (\prec )\ (Node2\ a\ b)\ z&=&\ a\ \prec (b\ \prec \ z)\\&reducer\ (\prec )\ (Node3\ a\ b\ c)\ z&=&\ a\ \prec (\ b\prec (c\ \prec \ z))\\\\&reducel\ (\succ )\ z\ (Node2\ b\ a)\ &=&\ (z\ \succ \ b)\ \succ \ a\\&reducel\ (\succ )\ z\ (Node3\ c\ b\ a)\ &=&\ ((z\ \succ \ c)\succ \ b)\succ \ a\\\end{aligned}}$ ${\begin{aligned}\mathrm {instance} &\ Reduce\ FingerTree\ \mathrm {where} &&\\&reducer\ (\prec )\ (Empty)\ z\ &=&\ z\\&reducer\ (\prec )\ (Single\ x)\ z&=&\ x\ \prec \ z\\&reducer\ (\prec )\ (Deep\ pr\ m\ sf)\ z&=&\ pr\ \prec '\ (m\ \prec ''\ (sf\ \prec '\ z))\\&\ \ \ \ where\\&\ \ \ \ \ \ \ \ (\prec ')\ =reducer\ (\prec )\\&\ \ \ \ \ \ \ \ (\prec '')\ =reducer\ (reducer\ (\prec ))\\\\&reducel\ (\succ )\ z\ (فارغ)\ &=&\ z\\&reducel\ (\succ )\ z\ (مفرد\ \ x)\ &=&\ z\ \succ \ x\\&reducel\ (\succ )\ z\ (عميق\ \ pr\ m\ sf)\ &=&\ ((z\ \succ '\ pr)\ \succ ''\ m)\ \succ '\ sf)\\&\ \ \ \ حيث&\ \ \ \ \ \ \ \ (\succ ')\ =reducel\ (\succ )\\&\ \ \ \ \ \ \ \ (\succ '')\ =reducel\ (reducel\ (\succ ))\\\end{aligned}}$

عمليات قائمة الانتظار المزدوجة

تُعدّ أشجار الأصابع أيضًا هياكل طوابير مزدوجة فعّالة . سواءً كان الهيكل مستمرًا أم لا، فإن جميع العمليات تستغرق وقتًا مُستهلكًا قدره Θ(1). يمكن مقارنة هذا التحليل بهياكل الطوابير المزدوجة الضمنية لأوكاساكي، والفرق الوحيد هو أن نوع FingerTree يخزن العقد بدلًا من الأزواج. ^{[ 1 ]}

طلب

يمكن استخدام أشجار الأصابع لبناء أشجار أخرى. ^{[ 4 ]} على سبيل المثال، يمكن إنشاء قائمة انتظار ذات أولوية عن طريق تسمية العقد الداخلية وفقًا لأدنى أولوية لأبنائها في الشجرة، أو يمكن إنشاء قائمة/مصفوفة مفهرسة عن طريق تسمية العقد وفقًا لعدد الأوراق في أبنائها. ومن التطبيقات الأخرى متواليات الوصول العشوائي، الموضحة أدناه، والمتواليات المرتبة ، وأشجار الفترات . ^{[ 1 ]}

تُتيح أشجار الأصابع إمكانية إضافة عناصر وعكسها وحذفها بكفاءة زمنية مُعدّلة O(1)، وإلحاق عناصر وتقسيمها بكفاءة زمنية O(log n)؛ كما يُمكن تكييفها لتكون تسلسلات مُفهرسة أو مُرتبة. ومثل جميع هياكل البيانات الوظيفية، فهي مُستدامة بطبيعتها ؛ أي أن الإصدارات القديمة من الشجرة تُحفظ دائمًا.

تسلسلات الوصول العشوائي

تُتيح أشجار الأصابع تنفيذ متواليات الوصول العشوائي بكفاءة. وهذا من شأنه أن يدعم عمليات تحديد المواقع السريعة، بما في ذلك الوصول إلى العنصر رقم n وتقسيم المتوالية عند موضع معين. ولتحقيق ذلك، نُضيف إلى شجرة الأصابع أحجامًا. ^{[ 1 ]}

newtype Size = Size { getSize :: N } deriving ( Eq , Ord )مثال على حجم أحادي حيث ∅ = الحجم 0 الحجم m ⊕ الحجم n = الحجم ( m + n )

يرمز الحرف N إلى الأعداد الطبيعية. النوع الجديد ضروري لأنه يحمل أنواعًا مختلفة من المونيدات. ولا يزال هناك حاجة إلى نوع جديد آخر لعناصر المتتالية الموضحة أدناه.

newtype Elem a = Elem { getElem :: a } newtype Seq a = Seq ( FingerTree Size ( Elem a ))مثال قياس ( العنصر أ ) الحجم حيث || العنصر || = الحجم 1

تُظهر هذه الأسطر البرمجية أن `instance` يُمثل حالة أساسية لقياس الأحجام، وأن العناصر بحجم واحد. لا يُسبب استخدام ` newtype s` أي تأثير سلبي على وقت التشغيل في لغة Haskell، لأنه في المكتبة، يتم إخفاء نوعي ` Size` و` Elem` عن المستخدم باستخدام دوال مُغلِّفة.

مع هذه التغييرات، أصبح من الممكن الآن حساب طول التسلسل في وقت ثابت.

النشر الأول

تم نشر أشجار الأصابع لأول مرة في عام 1977 بواسطة ليونيداس ج. غيباس ، ^{[ 5 ]} وتم تحسينها بشكل دوري منذ ذلك الحين (على سبيل المثال، نسخة تستخدم أشجار AVL ، ^{[ 6 ]} أشجار الأصابع غير الكسولة، أشجار الأصابع 2-3 الأبسط المعروضة هنا، ^{[ 1 ]} أشجار B وما إلى ذلك).

التطبيقات

استُخدمت أشجار الأصابع لاحقًا في مكتبات Haskell الأساسية (في تطبيق Data.Sequence )، ويوجد تطبيق لها في OCaml ^{[ 7 ]} مُشتق من تطبيق Rocq مُثبت صحته . ^{[ 8 ]} كما يوجد تطبيق مُوثق في Isabelle (مساعد البرهان) يُمكن من خلاله توليد برامج بلغة Haskell ولغات أخرى (وظيفية). ^{[ 9 ]} يُمكن تطبيق أشجار الأصابع مع أو بدون التقييم الكسول ، ^{[ 10 ]} ولكن التقييم الكسول يُتيح تطبيقات أبسط.

انظر أيضاً

مراجع

1 2 3 4 5 6 7 8 9 هينز، رالف؛ باترسون، روس (2006)، "أشجار الأصابع: بنية بيانات بسيطة للأغراض العامة" (ملف PDF) ، مجلة البرمجة الوظيفية ، 16 (2): 197-217 ، doi : 10.1017/S0956796805005769 ، S2CID 6881581 .
1 2 جيبانسكي، أندرو. "أشجار الأصابع - أندرو جيبانسكي" . andrew.gibiansky.com . تم الاطلاع عليه بتاريخ 26-10-2017 .
↑ "أشجار الأصابع المرسومة بشكل صحيح (أتمنى ذلك)" . الرياضيات الجيدة، الرياضيات السيئة . تم الاسترجاع في 26-10-2017 .
↑ ساركار، أبهيروب. "شجرة الأصابع - بنية البيانات المثلى؟" . abhiroop.github.io . مؤرشف من الأصل بتاريخ 26-10-2017 . تم الاطلاع عليه بتاريخ 26-10-2017 .
↑ غيباس، إل جيه ؛ مكريت، إي إم؛ بلاس، إم إف؛ روبرتس، جيه آر ( 1977)، "تمثيل جديد للقوائم الخطية"، وقائع المؤتمر السنوي التاسع لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 49-60 .
↑ تساكاليديس، أ.ك. (1985)، "أشجار AVL للبحث الموضعي"، المعلومات والتحكم ، 67 ( 1-3 ): 173-194 ، doi : 10.1016/S0019-9958(85)80034-6.
↑ أخبار كاميل الأسبوعية
↑ ماثيو سوزو :: أشجار الأصابع التابعة في Coq
^ نوردهوف ، بنديكت. كورنر، ستيفان. لاميش ، بيتر (28 أكتوبر 2010). "أشجار الأصابع" . أرشيف الأدلة الرسمية . تم الاسترجاع في 26 نوفمبر 2021 .
↑ كابلان، هـ.؛ تارجان، ر. إي. ( 1995)، "قوائم مستمرة مع ربط عبر التباطؤ المتكرر"، وقائع الندوة السنوية السابعة والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة ، ص 93-102 .

روابط خارجية

[:0-1] 1 2 3 4 5 6 7 8 9 هينز، رالف؛ باترسون، روس (2006)، "أشجار الأصابع: بنية بيانات بسيطة للأغراض العامة" (ملف PDF) ، مجلة البرمجة الوظيفية ، 16 (2): 197-217 ، doi : 10.1017/S0956796805005769 ، S2CID 6881581 .

[:1-2] 1 2 جيبانسكي، أندرو. "أشجار الأصابع - أندرو جيبانسكي" . andrew.gibiansky.com . تم الاطلاع عليه بتاريخ 26-10-2017 .

[3] "أشجار الأصابع المرسومة بشكل صحيح (أتمنى ذلك)" . الرياضيات الجيدة، الرياضيات السيئة . تم الاسترجاع في 26-10-2017 .

[4] ساركار، أبهيروب. "شجرة الأصابع - بنية البيانات المثلى؟" . abhiroop.github.io . مؤرشف من الأصل بتاريخ 26-10-2017 . تم الاطلاع عليه بتاريخ 26-10-2017 .

[5] غيباس، إل جيه ؛ مكريت، إي إم؛ بلاس، إم إف؛ روبرتس، جيه آر ( 1977)، "تمثيل جديد للقوائم الخطية"، وقائع المؤتمر السنوي التاسع لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 49-60 .

[6] تساكاليديس، أ.ك. (1985)، "أشجار AVL للبحث الموضعي"، المعلومات والتحكم ، 67 ( 1-3 ): 173-194 ، doi : 10.1016/S0019-9958(85)80034-6.

[7] أخبار كاميل الأسبوعية

[8] ماثيو سوزو :: أشجار الأصابع التابعة في Coq

[9] نوردهوف ، بنديكت. كورنر، ستيفان. لاميش ، بيتر (28 أكتوبر 2010). "أشجار الأصابع" . أرشيف الأدلة الرسمية . تم الاسترجاع في 26 نوفمبر 2021 .

[10] كابلان، هـ.؛ تارجان، ر. إي. ( 1995)، "قوائم مستمرة مع ربط عبر التباطؤ المتكرر"، وقائع الندوة السنوية السابعة والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة ، ص 93-102 .

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]