الشجرة الأسية

الشجرة الأسية هي نوع من أشجار البحث حيث يتناقص عدد أبناء العقدة الواحدة بشكل أسي مضاعف مع ازدياد عمقها. تُخزَّن القيم فقط في العقد الطرفية. تحتوي كل عقدة على مُقسِّم، وهو قيمة أقل من أو تساوي جميع القيم في الشجرة الفرعية، ويُستخدم هذا المُقسِّم أثناء البحث. تستخدم الأشجار الأسية بنية بيانات أخرى في العقد الداخلية تحتوي على مُقسِّمات الأبناء، مما يُتيح البحث السريع.

تحقق الأشجار الأسية التعقيد التقاربي الأمثل في بعض العمليات. ولها أهمية نظرية في المقام الأول.

الشجرة الأسية هي شجرة جذرية تحتوي كل عقدة فيها على مُقسِّم، وتحتوي كل عقدة طرفية على قيمة. قد تختلف القيمة عن قيمة المُقسِّم.${\displaystyle n}$يتم تعريف القيم بشكل متكرر:

• الجذر لديه${\displaystyle \Theta (n^{1/k})}$أطفال
• مُقسِّم الجذر هو نفسه مُقسِّم الابن الأيسر
• يتم تخزين عوامل تقسيم جميع الأبناء في بنية بيانات محلية
• الأشجار الفرعية هي أشجار أسية مع${\displaystyle \Theta (n^{1-1/k})}$قيم

شرط إضافي هو أن البحث عن قيمة باستخدام أدوات التقسيم يجب أن يُنتج العقدة الصحيحة (أي العقدة التي تحتوي على القيمة). لذلك، إذا كان جذر الشجرة الفرعية يحتوي على أداة التقسيم${\displaystyle s}$ويحتوي شقيقه الأيمن على الفاصل${\displaystyle s'}$إذاً، لا يمكن أن تحتوي هذه الشجرة الفرعية إلا على مفاتيح ضمن النطاق${\displaystyle [s,s')}$.

تستخدم الشجرة بنية بيانات ثابتة في كل عقدة داخلية للسماح بالبحث السريع عن القيم. يجب أن يكون من الممكن بناء هذه البنية باستخدام${\displaystyle d}$القيم في الزمن${\displaystyle O(d^{k-1})}$يُشار إلى وقت البحث في هذا الهيكل بـ${\displaystyle S(d)}$.

يمكن استخدام شجرة Fusion كهيكل بيانات.

• أندرسون، آرني (أكتوبر 1996). "فرز وبحث حتمي أسرع في الفضاء الخطي". وقائع المؤتمر السابع والثلاثين حول أسس علوم الحاسوب . الصفحات 135-141 . doi : 10.1109/SFCS.1996.548472 . ISBN  0-8186-7594-2. S2CID 13603426 . 
• أندرسون، آرني؛ ثورب، ميكيل (1 يونيو 2007). "المجموعات المرتبة الديناميكية مع أشجار البحث الأسية" . مجلة ACM . 54 (3): 13–es. arXiv : cs/0210006 . doi : 10.1145/1236457.1236460 . ISSN 0004-5411 . S2CID 8175703 .