עץ kd

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

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

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

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

שם העץ מבוסס על כך שבתחילת השימוש בעצים מסוג זה הם נקראו על פי מספר הממדים שלהם. למשל, עץ kd בשני ממדים נקרא "2d tree" ועץ כללי על k ממדים נקרא "kd tree". כיום משתמשים בשם "kd tree" עבור כל עץ מסוג זה ללא קשר למספר הממדים שלו, וכך עץ kd 2 ממדי נקרא "2d kd tree".

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

34622459עץ kd