====== جستجوی نزدیک‌ترین همسایه ======
هدف پیدا کردن نزدیک‌ترین نقطه به نقطه‌ی داده شده است. پیاده‌سازی از این الگوریتم در [[آماده‌سازی:کدهای_آماده|کدهای آماده]] وجود دارد.
===== درخت $kd$ =====
در این قسمت درخت $kd$ را معرفی می‌کنیم که تعمیمی از درخت جستجوی دودویی (یک بعدی) به $k$ بعد است.

برای ساخت این درخت یک بعد را انتخاب می‌کنیم و نقاط را بر اساس میانه‌شان در آن بعد دو قسمت می‌کنیم. سپس این کار را در بعد دیگری روی هر کدام از فرزندان این گره انجام می‌دهیم.

زمان ساخت درخت $kd$ با مرتب‌سازی در هر مرحله $O(n\log^2 n)$ است.

جستجوی نزدیک‌ترین همسایه روی درخت $kd$:

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

از این درخت برای جستجوی بازه‌ای هم می‌توان استفاده کرد.

[[http://en.wikipedia.org/wiki/K-d_tree|مطالب بیشتر در مورد درخت $kd$]]