עץ חיפוש

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

הגדרות[עריכת קוד מקור | עריכה]

עבור עץ G וצמתים-u,v

  • צומת v הינו צאצא של u אם קיים מסלול מכוון מצומת u ל- v.
  • u אב-קדמון של v אם v צאצא של u.
  • תת-עץ של G ששורשו v הוא עץ מכוון שצמתיו הם v עצמו וכל הצאצאים של v, והקשתות שלו הן הקשתות המחברות צמתים אלו ב- G.
  • דרגת צומת v היא מספר הבנים של v.
  • עלה הוא צמת ללא בנים.
  • צומת פנימי הוא צומת שאינו עלה.
  • עומק של צומת v הוא מספר הקשתות משורש העץ אל v (המרחק מהשורש).
  • גובה של צומת v הוא מספר הקשתות מ-v לצאצא הרחוק ביותר של v (עלה).
  • גובה העץ הוא הגובה של שורשו.

עץ חיפוש בינארי[עריכת קוד מקור | עריכה]

עץ חיפוש בינארי המכיל 9 איברים

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

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


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

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

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

עצים בינאריים נפוצים[עריכת קוד מקור | עריכה]

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

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

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

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

מסלולי מעבר[עריכת קוד מקור | עריכה]

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

שלוש השיטות הפשוטות והנפוצות ביותר הן -

סדר תחילי (preorder traversal)[עריכת קוד מקור | עריכה]

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

function visit(node)
   print node.value
   if node.left  != null then visit(node.left)
   if node.right != null then visit(node.right)

סדר תוכי (inorder traversal)[עריכת קוד מקור | עריכה]

קריאת תת-העץ השמאלי, לאחר מכן קריאת השורש (הצומת ממנו התחלנו), ולאחר מכן תת-העץ הימני.

function visit(node)
   if node.left  != null then visit(node.left)
   print node.value
   if node.right != null then visit(node.right)

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

סדר סופי (postorder traversal)[עריכת קוד מקור | עריכה]

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

function visit(node)
   if node.left  != null then visit(node.left)
   if node.right != null then visit(node.right)
   print node.value
עץ חיפוש בינארי
בעץ חיפוש זה,
  • סדר תחילי: F, B, A, D, C, E, G, I, H (שורש, בן שמאלי, בן ימני)
  • סדר תוכי: A, B, C, D, E, F, G, H, I (בן שמאלי, שורש, בן ימני)
  • סדר סופי: A, C, E, D, B, H, I, G, F (בן שמאלי, בן ימני, שורש)
  • מעבר רוחבי על רמות העומק בעץ: F, B, G, A, D, I, C, E, H


שיטה נוספת היא מעבר רוחבי על רמות העומק בעץ בזו אחר זו.

עצים לא בינאריים[עריכת קוד מקור | עריכה]

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

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

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