עץ R

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

הכנסה

כדי להכניס ערך לעץ R, מבוצע מעבר על צמתים בעץ החל מצומת השורש. בכל שלב נבחנים המלבנים בצומת, ועל ידי היוריסטיקה מסוימת נבחר מלבן מסוים שמייצג תת-עץ כמועמד מתאים להכנסת הערך תחתיו. ייתכן שיהיו כמה מלבנים שיענו לקריטריון של ההיוריסטיקה ואלגוריתם ההכנסה יצטרך להכריע ביניהם. 
לאחר בחירת צומת מתאים האלגוריתם ממשיך לבצע מעבר בצורה רקורסיבית בתוך צומתי הבנים שלו עד להגעה לצומת עלה מתאים. אם צומת העלה מלא (יש בו כבר  ערכים, ובשל כך מתרחשת גלישה - overflow), צריך לפצל אותו לפני שההכנסה תתבצע. כאן מבוצע שימוש בהיוריסטיקה נוספת לפיצול הערכים לשתי קבוצות מתאימות. בכל מקרה, לאחר הכנסה לצומת עלה, בודקים אם צריך לעדכן את הערך של המלבן בצומת האב, וכך הלאה בצורה רקורסיבית.
בדומה לעץ +B, גם כאן לאחר פיצול צומת עלה ההכנסה מפעפעת למעלה, כך שלאחר הפיצול מוכנס ערך חדש לצומת האב של העלה. לאחר מכן אם נדרש גם צומת האב מפוצל, וכך האלגוריתם ממשיך לפי הצורך בצורה רקורסיבית עד הגעה לצומת השורש. אם גם צומת השורש מלא ונדרש לפצל אותו, נוצר שורש חדש והגובה של העץ גדל בהתאמה.

בחירת תת-עץ להכנסה

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

עדכון

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

מחיקה

מחיקה של ערך מצומת בעץ R כרוכה תחילה במציאה של הצומת שמכיל את הערך שביקשו למחוק אותו (פעולת חיפוש), ואם נמצא צומת מתאים, מחיקה של הערך מאותו צומת. המחיקה עלולה לגרור צורך בעדכון של ערך מלבן בצומת האב.
במהלך המחיקה ייתכן שיהיה צורך למחוק ערך מצומת השורש. אם הערך היחיד שיש בצומת השורש הוא לא עלה, מתבצעת מחיקה של צומת השורש וסימון ערך הבן היחיד שלו כצומת שורש חדש. פעולה כזו מקטינה את הגובה של העץ.
בנוסף, על עץ R מוגדר תנאי לכמות מינימום של ערכים בצומת, לכן יש להתייחס גם אליו במהלך מחיקה. הטיפול בתנאי זה יתבצע בצורה שונה מזו שבה הוא מתבצע במבנה נתונים כמו עץ +B. בעץ +B, אם מגיעים למצב שבו רמת התפוסה של ערכים בצומת מסוים היא מתחת למינימום הנדרש (מצב של חמיקה - underflow), ניתן לפי הצורך להפעיל אלגוריתם מיזוג לשני צומתי אחים - מכיוון שהעץ מכיל אינדקס חד ממדי שהערכים ממויינים לפיו. לעומת זאת, במידע רב ממדי, התכונה הזאת לא מתקיימת בהכרח.
לכן, במקום זאת, גוטמן הציע לבצע הכנסה מחדש של כל הערכים שנותרו בצומת שהיה בתת-תפוסה, ולמחוק אותו לחלוטין מהעץ. שיטה זו מאפשרת מימוש פשוט יותר של האלגוריתם כי היא עושה שימוש באלגוריתם של פעולת ההכנסה ונמנעת מאלגוריתם מיזוג ייעודי. כמו כן יש לה יתרון בעבודה עם בסיסי נתונים, מאחר שהדפים שדרושים להכנסה מחדש היו צריכים להיטען לחוצץ בזיכרון הפנימי כבר במהלך החיפוש של הרשומה שביקשו למחוק. כמו כן, מחיקה של נתונים פוגעת באיכות המלבנים החוסמים בעץ (על ידי יצירת שטחים ריקים וחפיפות בין מלבנים שכבר לא הכרחיות), והכנסה של נתונים מחדש אמורה לצמצם תופעות אלו.

חיפוש תחום

החיפוש הסטנדרטי בעץ R הוא חיפוש תחום (range searching) בו מחפשים עצמים שנמצאים בתחום מסוים במרחב שניתן כקלט. בעץ R קלט של חיפוש כזה הוא מלבן (שמכונה בשמות 'תחום', 'חלון', ו'מלבן שאילתה'), והתוצאה הרצויה היא קבוצה של העצמים שמוצבעים מעלי העץ וחופפים לאותו מלבן או מוכלים בו. מקרה פרטי לחיפוש כזה הוא כשהקלט מייצג נקודה.
חיפוש תחום נעשה בצורה דומה לחיפוש בעץ +B. כל צומת פנימי בעץ מכיל קבוצת ערכים שמייצגים מלבנים וקבוצת מצביעים לצומתי בנים, וכל עלה מכיל מצביעים לעצמים עצמם במרחב. החיפוש מתחיל בצומת השורש של העץ, ונעשית בדיקה לכל מלבן בקבוצת המלבנים בצומת האם יש חפיפה כלשהי בינו לבין קלט החיפוש. אם יש חפיפה כזו צריך להמשיך לבצע את החיפוש בצומת הבן בצורה דומה. החיפוש ממשיך בצורה רקורסיבית כך שהאלגוריתם יבקר בכל הצמתים שבהם הייתה חפיפה כלשהי לקלט החיפוש.
כשמגיעים לעלה, ייתכן מצב של חפיפה שגויה (false overlap) שבו המלבן החוסם המינימלי חופף לקלט החיפוש, אבל העצם החסום (שהוא לא בהכרח מלבן) לא חופף אליו. בשל כך יש לבדוק את החפיפה גם עבור העצם שמוצבע מהעלה. כשנמצאת חפיפה בין עצם באחד העלים לקלט החיפוש, אותו עצם מתווסף לקבוצת הערכים של התוצאה. ייתכן שבחיפוש מסוים לא יימצא אף עצם מתאים.

חיפוש השכן הקרוב ביותר

ישנן פעולות חיפוש נוספות שנפוצות בעץ R. למשל, חיפוש השכן הקרוב ביותר (nearest neighbor search), שמטרתו למצוא עצם שהוא השכן שקרוב ביותר במרחב ה-n ממדי לנקודה או למלבן מסוימים שניתנים כקלט.
אלגוריתם בצורה של הסתעף וחסום לביצוע חיפוש כזה בעץ R הוצע על ידי Roussopoulos‏, Kelley ו-Vincent בשנת 1995. לצורך האלגוריתם מוגדרות שתי מטריקות בין נקודה במרחב ה-n ממדי לנקודה אחרת במלבן n-ממדי באותו מרחב: מטריקת מרחק מינימלי, ומטריקת מרחק מינימקס. שיפור של האלגוריתם שמייעל את החישובים ומשתמש במטריקת מרחק מינימלי בלבד הוצג על ידי Cheung ו-Fu בשנת 1998.