شجرة الغطاء

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

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

تستخدم شجرة التغطية تمثيلاً ضمنياً لتتبع النقاط المتكررة. وبالتالي، فهي لا تتطلب سوى مساحة O(n).