עץ kd

עץ kd הוא עץ חיפוש שמאחסן נקודות במרחב k-ממדי. k-ממדי פירושו שלכל נקודה יש k קואורדינטות, כלומר k מספרים שמגדירים את מיקומה.

ברור יותר בדוגמה בת שני ממדים: בשורש העץ מחלקים את הנקודות לפי קואורדינטת ה-x, כמו אם הנחנו ישר אנכי שמחלק את המישור לשמאל ולימין. נקודות מימין הולכות לתת-העץ הימני, ונקודות שמשמאל, לתת-העץ השמאלי. בשכבה הבאה מחלקים לפי קואורדינטת ה-y עם ישר אופקי. כך מחליפים בין x ל-y בכל רמה.

בעץ kd כללי החלוקה נעשית על ידי מישור ממדי-משנה (מישור בעל מימד k-1), ושומרים על מחזור של הקואורדינטות. כלומר בכל רמה משתנה הקואורדינטה שמשתמשים בה לחלוקה.

שמו של העץ נובע ממספר הממדים שלו: בעבר כינו אותם לפי המימד, והשם kd נשאר לשימוש הכללי. שימוש נפוץ בעצי kd הוא חיפוש תחום אורתוגונלי, מציאת כל הנקודות שבתוך קופסה צירית (קופסה שמיושרת לפי הצירים). עצים אלו מאפשרים לבצע חיפושים כאלה במהירות יחסית ובשימוש במקום נמוך.

כדי לבנות עץ kd עם n נקודות נדרש זמן O(n log n) והזיכרון הוא O(n). אחרי הבנייה, חיפוש טווח אורתוגונלי נע בסיבוכיות O(n^{1-1/k}+r), כאשר k הוא הממד ו-r הוא מספר התוצאות.

עץ kd הוא מבנה נתונים שמאחסן נקודות במרחב. נקודה היא מקום עם מספרים שמגלים איפה היא.

בדוגמה של שני ממדים, יש לכל נקודה x ו-y. בשורש העץ חוצים את המישור בקו אנכי לפי x. נקודות מימין הולכות לצד ימין, ונקודות משמאל הולכות לצד שמאל. בשכבה הבאה חוצים בקו אופקי לפי y. החיתוכים מתחלפים בכל רמה.

בממדים אחרים חוצים במישור מתאים, וחוזרים על סדר הקואורדינטות.

השם kd קשור למספר הממדים. משתמשים בעץ הזה כדי למצוא במהירות את כל הנקודות שבתוך קופסה. קופסה זו היא אזור שמיושר לפי הצירים, כמו מלבן או קובייה.

העץ חוסך מקום ועוזר למצוא נקודות מהר יותר מאשר לבדוק כל נקודה בנפרד.