ابزار کاربر
ابزار سایت
جستجوی نزدیک‌ترین همسایه
هدف پیدا کردن نزدیک‌ترین نقطه به نقطه‌ی داده شده است. پیاده‌سازی از این الگوریتم در کدهای آماده وجود دارد.
درخت $kd$
در این قسمت درخت $kd$ را معرفی می‌کنیم که تعمیمی از درخت جستجوی دودویی (یک بعدی) به $k$ بعد است.
برای ساخت این درخت یک بعد را انتخاب می‌کنیم و نقاط را بر اساس میانه‌شان در آن بعد دو قسمت می‌کنیم. سپس این کار را در بعد دیگری روی هر کدام از فرزندان این گره انجام می‌دهیم.
زمان ساخت درخت $kd$ با مرتب‌سازی در هر مرحله $O(n\log^2 n)$ است.
جستجوی نزدیک‌ترین همسایه روی درخت $kd$:
مشابه درخت جستجوی دودویی درخت را از ریشه به برگ طی می‌کنیم. این برگ را به عنوان بهترین جواب فعلی در نظر می‌گیریم. مسیر را به سمت ریشه برمی‌گردیم و اگر جواب بهتر شد، فرزند دیگر آن گره را هم بررسی می‌کنیم. متوسط زمان این کار $O(\log n)$ است.
از این درخت برای جستجوی بازه‌ای هم می‌توان استفاده کرد.