עץ חיפוש

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

עבור עץ G וצמתים v, u: העיקרון הוא שסדר בין צמתים קובע היכן ימוקמו צאצאים ביחס להורה.

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

להכנסת ערך חדש האלגוריתם מתחיל מהשורש. אם הערך קטן מהמפתח הנוכחי נעה שמאלה, ואם גדול נעה ימינה. התנועה נמשכת עד שמוצאים מקום ריק להוסיף את הצומת.

למחיקה יש שלוש אפשרויות: אם הצומת עלה (עלים) מוחקים אותו; אם יש לו בן אחד מעבירים את הבן להיות בן של האב; אם יש לו שני בנים מוצאים את העוקב, כלומר הקודקוד הקטן ביותר שגדול ממנו, שממנו אין בן שמאלי, מוחקים אותו ומחליפים במקום הצומת שנמחק. כדי לבצע זאת יעיל משתמר מצביע להורה (ההורה, הקודקוד שמעליו).

בממוצע, אם העץ מאוזן גובהו הוא כ-log n (log בסיס 2), והחיפוש לוגריתמי בזמן. במקרים גרועים, למשל הכנסת נתונים בסדר ממוין, העץ עלול להישרשר והגובה להגיע ל-n, מה שמביא לחיפוש איטי בצורת O(n). סיבוכיות זמן טיפוסית היא O(log n) במצב ממוצע ו-O(n) במקרה הגרוע.

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

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

עצים אדומים־שחורים: בכל צומת יש צבע אדום או שחור והם מקיימים חוקים שמגבילים אורכי מסלולים. חוקים אלו מונעים שחץ ארוך מדי ומבטיחים סיבוכיות לוגריתמית. האלגוריתם מסובך יותר מ-AVL, אך לעתים מהיר יותר.

עצי Splay: מבוססים על העלאת הצומת שנחפש לשורש. צמתים שניגשים אליהן לעתים קרובות יומרו קרובים לשורש. שיטה זו טובה כשיש הבדלי תדירות בגישה לפריטים.

עצי kd: משמשים לחיפוש נקודות במרחב רב־ממדי. הם מנצלים את המיקום הגיאומטרי של הנתונים.

קיימות מספר שיטות לעבור על כל צמתים בעץ. שלוש השיטות הנפוצות הן:

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

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

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

יש גם חיפוש בעומק (DFS, Depth-first search) ושיטתי ברוחב (BFS, Breadth-first search), שבו עוברים רמה אחר רמה.

עצי multiway: לכל אב יש עד m בנים. עצי B: וריאציה שבה כל העלים נמצאים באותה רמה ומספר הבנים אינו פחות ממחצית m. עצי B+: בריבוי זה המידע העיקרי מאוחסן בעלים באופן סדרתי.

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

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

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

בעץ כזה לכל צומת יש עד שני בנים: שמאלי וימני. כל מה שנמצא בצד שמאל קטן מהאב. כל מה שבימין גדול מהאב.

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

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

אם העץ מאוזן, החיפוש מהיר. אם הוא לא מאוזן, החיפוש איטי.

עצי AVL: שומרים על איזון בעץ בעזרת סיבובים. איזון מסייע בחיפושים מהירים.

עצים אדום-שחור: צובעים צמתים באדום ושחור וחוקי הצביעה שומרים על גובה קצר.

עצי Splay: מעלים צומת שנחפש לשורש. כך צמתים שבאים הרבה יהיו קרובים לשורש.

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

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

עץ תחיליות מפרק מילים לתווים. כך מחפשים מילים לפי אותיות.