شجرة التانغو

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

على وجه الخصوص، يبلغ ارتفاع الشجرة المرجعية ⌈ log ₂ ( n +1) ⌉ . وهذا يساوي طول أطول مسار، وبالتالي حجم أكبر شجرة مساعدة. من خلال الحفاظ على توازن معقول بين الأشجار المساعدة، يمكن حصر ارتفاعها في O (log log n ). وهذا هو مصدر ضمانات أداء الخوارزمية.

أولًا، نُعرّف لكل عقدة ابنها المُفضّل ، وهو ببساطة آخر عقدة تمّت زيارتها في عملية بحث تقليدية في شجرة البحث الثنائية. بتعبير أدق، لنفترض شجرة فرعية T ، جذرها p ، ولها ابنان l (يسار) و r (يمين). نُعيّن r الابن المُفضّل لـ p إذا كانت آخر عقدة تمّ الوصول إليها في T تقع في الشجرة الفرعية التي جذرها r ، ونُعيّن l الابن المُفضّل في غير ذلك. لاحظ أنه إذا كانت آخر عقدة تمّ الوصول إليها في T هي p نفسها، فإن l هو الابن المُفضّل بحكم التعريف.

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

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

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

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

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

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

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

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