עץ 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 עם נקודות יש צורך בזמן של ומקום של . לאחר שנבנה, ניתן למצוא בו נקודות בחיפוש טווח אורתוגונלי בסיבוכיות כאשר הוא ממד המרחב שבו נמצאות הנקודות ו- הוא מספר הנקודות בפלט.
מבני נתונים | ||
---|---|---|
מבנים מופשטים | רשימה • מחסנית • קבוצה • מולטי קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • Trie • X-fast trie • טריי y מהיר• עץ WAVL | |
הסתברותיים | מסנן בלום |
קישורים חיצוניים
[עריכת קוד מקור | עריכה]Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.