شجرة علوية

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

شجرة عالية${\displaystyle \Re }$يتم تعريفها لشجرة أساسية T ومجموعة${\displaystyle \partial {T}}$تتكون من رأسين على الأكثر، وتسمى رؤوس الحدود الخارجية.

تُستخدم الأشجار العليا للحفاظ على غابة ديناميكية (مجموعة من الأشجار) في ظل عمليات الربط والقطع.

الفكرة الأساسية هي الحفاظ على شجرة ثنائية متوازنة${\displaystyle \Re }$بارتفاع لوغاريتمي بالنسبة لعدد العقد في الشجرة الأصلية T (أي في${\displaystyle {\mathcal {O}}(\log n)}$الوقت)؛ تمثل الشجرة العليا بشكل أساسي التقسيم المتكرر للشجرة الأصلية T إلى مجموعات .

بشكل عام، قد يكون للشجرة T وزن على حوافها.

توجد علاقة تناظرية بين حواف الشجرة الأصلية T وعقد الأوراق في الشجرة العلوية.${\displaystyle \Re }$وكل عقدة داخلية من${\displaystyle \Re }$يمثل مجموعة تتشكل نتيجة اتحاد المجموعات التي هي أبنائها.

يمكن تهيئة بنية بيانات الشجرة العليا في${\displaystyle {\mathcal {O}}(n)}$وقت.

لذلك الشجرة العليا${\displaystyle \Re }$زيادة${\displaystyle ({\mathcal {T}},\partial {T})}$هي شجرة ثنائية بحيث

• عقد${\displaystyle \Re }$هي مجموعات من${\displaystyle ({\mathcal {T}},\partial {T})}$؛
• أوراق${\displaystyle \Re }$هي حواف T ؛
• تعتبر المجموعات الشقيقة جيرانًا بمعنى أنها تتقاطع في رأس واحد، ثم تكون مجموعتها الأصلية هي اتحادها.
• أصل${\displaystyle \Re }$هي الشجرة T نفسها، مع مجموعة من رأسين حدوديين خارجيين على الأكثر.

الشجرة ذات الرأس الواحد لها شجرة علوية فارغة، والشجرة ذات الحافة الواحدة لها عقدة واحدة فقط.

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

التحديثات الثلاثة التالية هي تحديثات الغابة المسموح بها للمستخدم.

• Link(v, w): حيث v و w هما رأسان في شجرتين مختلفتين _T1 و T2 . _تُرجع هذه الدالة شجرة علوية واحدة تمثل${\displaystyle \Re _{v}\cup \Re _{w}\cup {(v,w)}}$
• Cut(v, w) : يزيل الحافة${\displaystyle {(v,w)}}$من شجرة T مع شجرة علوية${\displaystyle \Re ,}$وبذلك يتم تحويلها إلى شجرتين T _v و T _w وإعادة شجرتين علويتين${\displaystyle \Re _{v}}$و${\displaystyle \Re _{w}}$.
• Expose(S) : يتم استدعاؤها كإجراء فرعي لتنفيذ معظم الاستعلامات على الشجرة العليا. تحتوي S على رأسين على الأكثر. تقوم هذه العملية بتحويل الرؤوس الخارجية الأصلية إلى رؤوس عادية، وتجعل الرؤوس من S رؤوس الحدود الخارجية الجديدة للشجرة العليا. إذا كانت S غير فارغة، فإنها تُرجع مجموعة الجذور الجديدة C.${\displaystyle \partial {C}=S.}$يفشل الأمر Expose({v,w}) إذا كانت الرؤوس من أشجار مختلفة.

يتم تنفيذ جميع تحديثات الغابة من خلال سلسلة من العمليات على الأكثر${\displaystyle {\mathcal {O}}(\log n)}$العمليات الداخلية، التي يتم حساب تسلسلها لاحقًا${\displaystyle {\mathcal {O}}(\log n)}$قد يحدث أثناء تحديث الشجرة أن تتحول مجموعة أوراق إلى مجموعة مسارات، والعكس صحيح. وتُجرى تحديثات الشجرة العليا حصريًا من خلال هذه العمليات الداخلية.

ال${\displaystyle I({\mathcal {C}})}$يتم تحديثها عن طريق استدعاء دالة معرفة من قبل المستخدم مرتبطة بكل عملية داخلية.

${\displaystyle \mathrm {Merge} ({\mathcal {A}},{\mathcal {B}})}$

هنا ، A و B عبارة عن مجموعات قابلة للدمج ، وتُرجع الدالة C كمجموعة أصلية لـ A و B ، مع رؤوس حدودية تمثل رؤوس الحدود لـ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}.}$يحسب${\displaystyle I({\mathcal {C}})}$استخدام${\displaystyle I({\mathcal {A}})}$و${\displaystyle I({\mathcal {B}}).}$

${\displaystyle \mathrm {Split} ({\mathcal {C}})}$

هنا C هي المجموعة الجذرية${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}.}$يتم تحديثه${\displaystyle I({\mathcal {A}})}$و${\displaystyle I({\mathcal {B}})}$استخدام${\displaystyle I({\mathcal {C}})}$ثم يقوم بحذف المجموعة C من${\displaystyle \Re }$.

يتم تنفيذ عملية التقسيم عادةً باستخدام${\displaystyle \mathrm {Clean} ({\mathcal {C}})}$طريقة تستدعي طريقة المستخدم لتحديثات${\displaystyle I({\mathcal {A}})}$و${\displaystyle I({\mathcal {B}})}$استخدام${\displaystyle I({\mathcal {C}})}$والتحديثات${\displaystyle I({\mathcal {C}})}$بحيث يُعرف أنه لا توجد حاجة إلى تحديث معلق في عناصره الفرعية. ثم يتم تجاهل C دون استدعاء الدوال المعرفة من قبل المستخدم. غالبًا ما تكون عملية التنظيف مطلوبة للاستعلامات التي لا تتطلب تقسيمًا . إذا لم يستخدم التقسيم روتين التنظيف الفرعي، وكانت عملية التنظيف مطلوبة، فيمكن تحقيق تأثيرها مع زيادة في الحمل عن طريق دمج الدمج والتقسيم .

الوظيفتان التاليتان مماثلتان للوظيفتين السابقتين وتستخدمان للمجموعات الأساسية.

${\displaystyle \mathrm {Create} (v,w)}$

يُنشئ مجموعة C للحافة${\displaystyle (v,w).}$مجموعات${\displaystyle \partial {C}=\partial (v,w).}$${\displaystyle I({\mathcal {C}})}$يتم حسابها من الصفر.

${\displaystyle \mathrm {Eradicate} ({\mathcal {C}})}$

C هي مجموعة الحواف${\displaystyle (v,w).}$يتم استدعاء الدالة المعرفة من قبل المستخدم للمعالجة${\displaystyle I({\mathcal {C}})}$ثم يتم حذف المجموعة C من الشجرة العليا.

يمكن للمستخدم تحديد الاختيار${\displaystyle ({\mathcal {C}}){:}}$عمليةٌ تُحدِّد إحدى مجموعات فرعية لمجموعة جذرية (غير طرفية). يوفر الصندوق الأسود للشجرة العليا وظيفة البحث.${\displaystyle ({\mathcal {C}}){:}}$روتين يُنظّم استعلامات الاختيار وإعادة تنظيم الشجرة العليا (باستخدام العمليات الداخلية) بحيث يُحدد الحافة الوحيدة في تقاطع جميع المجموعات المُختارة. في بعض الأحيان، يجب حصر البحث في مسار مُحدد. يوجد نوع من البحث غير المحلي لهذه الأغراض. إذا كان هناك رأسان حدوديان خارجيان في المجموعة الجذرية C ، فسيتم البحث عن الحافة على هذا المسار فقط.${\displaystyle \pi ({\mathcal {C}})}$يكفي إجراء التعديل التالي: إذا كان أحد أبناء المجموعة الجذرية فقط هو مجموعة المسار، فسيتم تحديده افتراضيًا دون استدعاء عملية الاختيار .

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

• [سليتور وتارجان 1983]. يمكننا الحفاظ على مجموعة ديناميكية من الأشجار الموزونة في${\displaystyle {\mathcal {O}}(\log n)}$الوقت لكل رابط وقطع، مع دعم الاستعلامات حول أقصى وزن للحافة بين أي رأسين في${\displaystyle O(\log n)}$وقت.
  • مخطط البرهان: يتضمن الحفاظ على أقصى وزن عند كل عقدة ( ⁠${\displaystyle {\max }_{wt}}$) على مسار مجموعتها، إذا كانت مجموعة نقطية، فـ${\displaystyle {\max }_{wt}({\mathcal {C}})}$يتم تهيئتها كـ${\displaystyle -\infty .}$عندما تكون المجموعة عبارة عن اتحاد مجموعتين، فإنها تمثل القيمة القصوى للمجموعتين المدمجتين. إذا أردنا إيجاد أقصى قيمة لـ wt بين v و w، فإننا نقوم بما يلي:${\displaystyle {\mathcal {C}}=\mathrm {Expose} (v,w),}$وتقديم تقرير${\displaystyle {\max }_{wt}({\mathcal {C}}).}$
• [سليتور وتارجان 1983]. في سيناريو التطبيق المذكور أعلاه، يمكننا أيضًا إضافة وزن مشترك x إلى جميع الحواف على مسار معين v · · · w in${\displaystyle {\mathcal {O}}(\log n)}$وقت.
  • مخطط البرهان: نُدخل وزنًا يُسمى إضافي ( C ) ليتم إضافته إلى جميع الحواف في${\displaystyle \pi ({\mathcal {C}}).}$والتي يتم الحفاظ عليها بشكل مناسب  ؛ يتطلب split( C ) أنه لكل مسار فرعي A من C ، نقوم بتعيين${\displaystyle {\max }_{wt}(A):={\max }_{wt}({\mathcal {A}})+\mathrm {extra} ({\mathcal {C}})}$و${\displaystyle \mathrm {extra} ({\mathcal {A}}):=\mathrm {extra} ({\mathcal {A}})+\mathrm {extra} ({\mathcal {C}})}$بالنسبة لـ C  := join( A , B )، نُعيّن${\displaystyle {\max }_{wt}({\mathcal {C}}):=\max\{{\max }_{wt}({\mathcal {A}}),{\max }_{wt}({\mathcal {B}})\}}$و${\displaystyle \mathrm {extra} ({\mathcal {C}}):=0}$وأخيرًا، لإيجاد أقصى وزن على المسار v · · · w ، نضع${\displaystyle {\mathcal {C}}:=\mathrm {Expose} (v,w)}$ثم العودة${\displaystyle {\max }_{wt}({\mathcal {C}})}$.
• [جولدبيرج وآخرون، 1991]. يمكننا طلب الوزن الأقصى في الشجرة الأساسية التي تحتوي على رأس معين v في${\displaystyle {\mathcal {O}}(\log n)}$وقت.
  • مخطط البرهان: يتطلب هذا الاحتفاظ بمعلومات إضافية حول حافة المسار غير العنقودي ذات الوزن الأقصى في عنقود تحت عمليات الدمج والتقسيم.
• يمكن إيجاد المسافة بين رأسين v و w في${\displaystyle {\mathcal {O}}(\log n)}$الوقت${\displaystyle \mathrm {length} (\mathrm {Expose} (v,w))}$.
  • مخطط البرهان: سنحتفظ بطول المسار العنقودي ( C ). يُحتفظ بالطول كأقصى وزن، باستثناء أنه إذا تم إنشاء C عن طريق دمج (دمج)، فإن طول ( C ) هو مجموع الأطوال المخزنة مع مساراته الفرعية.
• الاستفسارات المتعلقة بقطر الشجرة وصيانتها اللاحقة تستغرق${\displaystyle {\mathcal {O}}(\log n)}$وقت.
• يمكن الاحتفاظ بالمركز والوسيط من خلال عمليات الربط (الدمج) والقص (التقسيم) والاستعلام عنهما من خلال البحث غير المحلي في${\displaystyle {\mathcal {O}}(\log n)}$وقت.

• تُستخدم الأشجار العليا في أحدث الخوارزميات لحساب الاتصال الديناميكي ثنائي الحواف . في هذه المسألة، كما هو الحال في الاتصال الديناميكي ، يخضع الرسم البياني لعمليات حذف وإضافة الحواف، بالإضافة إلى الاستعلامات التي تسأل عما إذا كان زوج من الرؤوس متصلًا ثنائي الحواف، أو ما إذا كان هناك جسر يفصل بينهما. يقدم هولم ، ودي ليشتنبرغ، وثورب ^{[ 1 ]} خوارزمية حتمية بوقت تحديث مُعدَّل.${\displaystyle O(\log ^{4}n)}$، و${\displaystyle O(\log n/\log \log n)}$وقت الاستعلام. وقد حسّن العمل اللاحق الذي قام به هولم وروتنبرغ وثورب هذا إلى وقت تحديث مُستهلك قدره${\displaystyle O(\log ^{2}n\log ^{2}\log n)}$، وكذلك باستخدام الأشجار العليا ^{[ 2 ] [ 3 ]}

• يمكن الحفاظ على الرسم البياني مما يسمح بتحديث مجموعة الحواف وطرح استعلامات حول اتصال الرؤوس من الدرجة الثانية. التعقيد المُستهلك للتحديثات هو${\displaystyle O(\log ^{5}n)}$يمكن تنفيذ الاستعلامات بشكل أسرع. الخوارزمية ليست بسيطة.${\displaystyle I({\mathcal {C}})}$الاستخدامات${\displaystyle \Theta (\log ^{2}n)}$^{[ 4 ]} مساحة.

• يمكن استخدام الأشجار العليا لضغط الأشجار بطريقة لا تقل سوءًا عن ضغط DAG ، بل قد تكون أفضل بشكل كبير. ^{[ 5 ]}

تم تنفيذ الأشجار العليا بطرق متنوعة، بعضها يتضمن التنفيذ باستخدام تقسيم متعدد المستويات (الأشجار العليا وخوارزميات الرسم البياني الديناميكي جاكوب هولم وكريستيان دي ليشتنبرغ. تقرير فني)، وحتى باستخدام أشجار سليتور-تارجان st (عادة مع حدود زمنية مستهلكة)، وأشجار فريدريكسون الطوبولوجية (مع حدود زمنية في أسوأ الحالات) (ألستروب وآخرون. الحفاظ على المعلومات في الأشجار الديناميكية بالكامل باستخدام الأشجار العليا).

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

• ربط/قطع الشجرة
• شجرة جولات أويلر
• خوارزمية ديناميكية
• اتصال ديناميكي

• ستيفن ألستروب، جاكوب هولم، كريستيان دي ليشتنبرغ، وميكيل ثوروب ، الحفاظ على المعلومات في الأشجار الديناميكية بالكامل مع الأشجار العليا ، معاملات ACM على الخوارزميات (TALG)، المجلد. 1 (2005)، 243-264، دوى : 10.1145 / 1103963.1103966
• ستيفن ألستروب، جاكوب هولم، كريستيان دي ليشتنبرغ، وميكيل ثورب ، خوارزميات حتمية متعددة اللوغاريتمات ديناميكية بالكامل للاتصال، والشجرة الممتدة الدنيا، والحافة الثنائية، والاتصال الثنائي ، مجلة ACM، المجلد 48، العدد 4 (يوليو 2001)، 723-760، doi : 10.1145/502090.502095
• دونالد كنوث . فن برمجة الحاسوب : الخوارزميات الأساسية ، الطبعة الثالثة. أديسون-ويسلي، 1997. ISBN 0-201-89683-4القسم 2.3: الأشجار، الصفحات  308-423.
• توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7القسم 10.4: تمثيل الأشجار الجذرية، الصفحات  214-217. الفصول 12-14 (أشجار البحث الثنائية، الأشجار الحمراء والسوداء، تعزيز هياكل البيانات)، الصفحات  253-320.

• الحفاظ على المعلومات في الأشجار الديناميكية بالكامل ذات الأشجار العليا. ألستروب وآخرون
• الأشجار العليا ذاتية التعديل. تارجان وويرنيك، وقائع المؤتمر السادس عشر لجمعية علم النبات التطبيقي، 2005
• الأشجار ذات القمم المتفرعة. هولم، روتنبرغ، وريل، 2022