شجرة ديكارتية

تُشكّل الأشجار الديكارتية جزءًا من بنية بيانات فعّالة لاستعلامات الحد الأدنى للنطاق . يُحدّد مُدخل هذا النوع من الاستعلامات سلسلة فرعية متصلة من السلسلة الأصلية؛ ويجب أن يكون مُخرج الاستعلام هو القيمة الدنيا في هذه السلسلة الفرعية. ^{[ 9 ]} في الشجرة الديكارتية، يُمكن إيجاد هذه القيمة الدنيا عند السلف المشترك الأدنى للقيمتين الأقصى يسارًا والأقصى يمينًا في السلسلة الفرعية. على سبيل المثال، في السلسلة الفرعية (12، 10، 20، 15، 18) من سلسلة المثال، تُشكّل القيمة الدنيا للسلسلة الفرعية (10) السلف المشترك الأدنى للقيمتين الأقصى يسارًا والأقصى يمينًا (12 و18). نظرًا لإمكانية إيجاد السلف المشترك الأدنى في وقت ثابت لكل استعلام، باستخدام بنية بيانات تشغل مساحة تخزين خطية ويُمكن إنشاؤها في وقت خطي، فإنّ نفس الحدود تنطبق على مسألة تقليل النطاق. ^{[ 10 ]}

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

يمكن أيضًا تفسير مسألة تقليل المدى نفسها تفسيرًا بديلًا من حيث البحث في المدى ثنائي الأبعاد. يمكن استخدام مجموعة من عدد محدود من النقاط في المستوى الديكارتي لتكوين شجرة ديكارتية، وذلك بترتيب النقاط حسب مواقعها.${\displaystyle x}$- الإحداثيات واستخدام${\displaystyle y}$- الإحداثيات بهذا الترتيب كتسلسل للقيم التي تشكلت منها هذه الشجرة. إذا${\displaystyle S}$هي مجموعة فرعية من نقاط الإدخال داخل شريحة رأسية معينة محددة بواسطة المتباينات${\displaystyle L\leq x\leq R}$،${\displaystyle p}$هي النقطة الواقعة في أقصى اليسار في${\displaystyle S}$(الذي يحتوي على الحد الأدنى)${\displaystyle x}$(الإحداثيات)، و${\displaystyle q}$هي النقطة الواقعة في أقصى اليمين${\displaystyle S}$(الشخص الذي يتمتع بأقصى قدر من${\displaystyle x}$(الإحداثيات) ثم السلف المشترك الأدنى لـ${\displaystyle p}$و${\displaystyle q}$في الشجرة الديكارتية، تمثل النقطة السفلية في الشريحة. استعلام نطاق ثلاثي الجوانب، حيث تتمثل المهمة في سرد ​​جميع النقاط داخل منطقة محددة بثلاث متباينات.${\displaystyle L\leq x\leq R}$و${\displaystyle y\leq T}$يمكن الإجابة على هذا السؤال من خلال إيجاد هذه النقطة السفلية${\displaystyle b}$مقارنة بـ${\displaystyle y}$-تنسيق إلى${\displaystyle T}$و(إذا كانت النقطة تقع داخل المنطقة ثلاثية الأضلاع) الاستمرار بشكل متكرر في اللوحين المحصورين بينهما${\displaystyle p}$و${\displaystyle b}$وبين${\displaystyle b}$و${\displaystyle q}$وبهذه الطريقة، بعد تحديد النقطتين الأقصى يسارًا والأدنى يمينًا في اللوح، يمكن سرد جميع النقاط داخل المنطقة ثلاثية الجوانب في وقت ثابت لكل نقطة. ^{[ 3 ]}

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

الشجرة الديكارتية لتسلسل مُرتب هي ببساطة رسم بياني للمسارات ، جذره عند أقصى نقطة في اليسار. يتحول البحث الثنائي في هذه الشجرة إلى بحث تسلسلي في المسار. مع ذلك، يستخدم بناء مختلف الأشجار الديكارتية لتوليد أشجار بحث ثنائية ذات عمق لوغاريتمي من تسلسلات مُرتبة من القيم. يمكن القيام بذلك عن طريق توليد أرقام أولوية لكل قيمة، واستخدام تسلسل الأولويات لتوليد شجرة ديكارتية. يمكن النظر إلى هذا البناء بشكل مكافئ في الإطار الهندسي الموصوف أعلاه، حيث${\displaystyle x}$إحداثيات مجموعة من النقاط هي القيم في تسلسل مُرتب و${\displaystyle y}$-الإحداثيات هي أولوياتهم. ^{[ 14 ]}

طُبقت هذه الفكرة من قِبل سايدل وأراغون (1996) ، اللذين اقترحا استخدام الأرقام العشوائية كأولويات. تُسمى شجرة البحث الثنائية ذاتية التوازن الناتجة عن هذا الاختيار العشوائي "تريب" (treap )، نظرًا لجمعها بين خصائص شجرة البحث الثنائية وخصائص الكومة الدنيا. يمكن إجراء عملية إدراج في التريب عن طريق إدخال المفتاح الجديد كطرف في شجرة موجودة، واختيار أولوية له، ثم إجراء عمليات تدوير للشجرة على طول مسار من العقدة إلى جذر الشجرة لإصلاح أي انتهاكات لخاصية الكومة ناتجة عن هذا الإدراج؛ وبالمثل، يمكن إجراء عملية حذف عن طريق إجراء تغيير ثابت على الشجرة متبوعًا بسلسلة من عمليات التدوير على طول مسار واحد في الشجرة. ^{[ 14 ]} يستخدم نوع مختلف من بنية البيانات هذه، يُسمى شجرة الضغط (zip tree)، نفس فكرة الأولويات العشوائية، ولكنه يُبسط عملية توليد الأولويات عشوائيًا، ويُجري عمليات الإدراج والحذف بطريقة مختلفة، عن طريق تقسيم التسلسل وشجرته الديكارتية المرتبطة به إلى تسلسلين فرعيين وشجرتين، ثم إعادة دمجهما. ^{[ 15 ]}

إذا تم اختيار أولويات كل مفتاح عشوائيًا وبشكل مستقل مرة واحدة عند إدخال المفتاح في الشجرة، فإن الشجرة الديكارتية الناتجة ستتمتع بنفس خصائص شجرة البحث الثنائية العشوائية ، وهي شجرة تُحسب بإدخال المفاتيح في تبديل مُختار عشوائيًا بدءًا من شجرة فارغة، مع الحفاظ على بنية الشجرة السابقة دون تغيير وإدخال العقدة الجديدة كإحدى أوراق الشجرة. وقد دُرست أشجار البحث الثنائية العشوائية لفترة أطول بكثير من أشجار البحث التقليدية، ومن المعروف أنها تتصرف بشكل جيد كأشجار بحث. ويبلغ الطول المتوقع لمسار البحث لأي قيمة معينة على الأكثر${\displaystyle 2\ln n}$ويكون للشجرة بأكملها عمق لوغاريتمي (أقصى مسافة من الجذر إلى الورقة) باحتمالية عالية . وبشكل أكثر دقة، يوجد ثابت${\displaystyle C}$بحيث يكون العمق${\displaystyle \leq C\ln n}$مع اقتراب الاحتمالية من الواحد كلما ازداد عدد العقد إلى ما لا نهاية. وينطبق هذا السلوك الجيد نفسه على شبكات التريب. كما أنه من الممكن، كما اقترح أراغون وسيدل، إعادة ترتيب أولويات العقد التي يتم الوصول إليها بشكل متكرر، مما يؤدي إلى تحركها نحو جذر شبكة التريب وتسريع عمليات الوصول المستقبلية لنفس المفاتيح. ^{[ 14 ]}

يصف ليفكوبولوس وبيترسون (1989) خوارزمية فرز تعتمد على الأشجار الديكارتية. ويصفان الخوارزمية بأنها مبنية على شجرة يكون فيها العنصر الأقصى عند الجذر، ^{[ 16 ]} ولكن يمكن تعديلها بسهولة لدعم شجرة ديكارتية مع مراعاة أن يكون العنصر الأدنى عند الجذر. ولضمان الاتساق، سيتم وصف هذه النسخة المعدلة من الخوارزمية أدناه.

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

1. قم بإنشاء شجرة ديكارتية لتسلسل الإدخال
2. قم بتهيئة قائمة انتظار ذات أولوية، تحتوي في البداية على جذر الشجرة فقط
3. طالما أن قائمة الانتظار ذات الأولوية غير فارغة:
   • ابحث عن القيمة الدنيا في قائمة الانتظار ذات الأولوية وقم بإزالتها
   • أضف هذه القيمة إلى تسلسل الإخراج
   • أضف أبناء الشجرة الديكارتية للقيمة المحذوفة إلى قائمة الانتظار ذات الأولوية

كما يُبين ليفكوبولوس وبيترسون، بالنسبة لتسلسلات الإدخال شبه المرتبة، سيظل حجم قائمة الانتظار ذات الأولوية صغيرًا، مما يسمح لهذه الطريقة بالاستفادة من الإدخال شبه المرتب والعمل بسرعة أكبر. وبالتحديد، فإن أسوأ وقت تشغيل لهذه الخوارزمية هو${\displaystyle O(n\log k)}$، أين${\displaystyle n}$هو طول التسلسل و${\displaystyle k}$هو المتوسط، على جميع قيم المتسلسلة، لعدد أزواج قيم المتسلسلة المتتالية التي تُحيط بالقيمة المُعطاة (أي أن القيمة المُعطاة تقع بين قيمتي المتسلسلة). كما تُثبت هذه الطريقة حدًا أدنى ينص على أنه لأي قيمة${\displaystyle n}$و(غير ثابت)${\displaystyle k}$يجب على أي خوارزمية فرز تعتمد على المقارنة أن تستخدم${\displaystyle \Omega (n\log k)}$مقارنات لبعض المدخلات. ^{[ 16 ]}

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