עץ בינארי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
דוגמה פשוטה לעץ בינארי

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

הגדרה רקורסיבית לעץ בינארי: עץ בינארי הינו עץ ריק (ללא צמתים), או עץ המורכב משורש ושני תתי-עצים בינאריים, ימני ושמאלי.

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

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

השורש הוא, על-פי ההגדרה, הצומת היחיד שאין לו אב. המרחק של צומת מן השורש הוא הרמה של הצומת; רמת השורש היא 0. הרמה הגבוהה ביותר של צמתים בעץ נקראת רמת העץ.

הגובה של העץ הוא אורכו של מסלול מהשורש לצומת בעל הרמה הגדולה ביותר. לעץ בעל צומת יחיד (השורש) גובה 0.

מספר הבנים של צומת נקרא הדרגה שלו (0, 1 או 2). אם לשני צמתים יש אב משותף, הם אחים; אחד מהם הוא הבן הימני, והשני הוא הבן השמאלי. האב של צומת a, וכן האבות הקדומים של אותו אב, נקראים אבות קדומים של a (זוהי הגדרה רקורסיבית). הצמתים ש- a הוא אב קדום שלהם, נקראים צאצאים של a, ויחד עם a הם יוצרים תת-עץ של העץ המקורי. לכל שני צמתים שאף אחד מהם אינו אב קדום של חבירו, יש אב קדום בעל רמה מקסימלית בין כל האבות הקדומים של שניהם; זהו האב המשותף שלהם.

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

עץ שאין בו אף צומת נקרא עץ ריק.

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

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

  • עץ בינארי מלא הוא עץ בו לכל צומת שאינו עלה יש שני בנים.
  • עץ בינארי מושלם הוא עץ בינארי מלא, בו כל העלים הם מאותה רמה.
  • אם לכל העלים רמה n או n-1, ולא קיים עלה בעל רמה n שמשמאלו נמצא עלה בעל רמה n-1, אז העץ כמעט מושלם.
  • עץ בינארי מאוזן מוגדר על פי רוב כעץ שבו ההפרש בין הגובה של שני תתי-עצים של אותו הצומת לעולם אינו גדול מאחד. עם זאת באופן כללי מגדירים אותו כעץ בו כל הרמה של כל עלה אינה הרבה יותר גבוהה מהרמה של כל עלה אחר, כאשר בכל שיטת איזון מגדירים באופן שונה את המשמעות של "הרבה יותר גבוהה". לעצים מאוזנים לפי ההגדרה הראשונה יש גובה חסום, השווה לערך השלם של \log_2(n) כאשר n הוא מספר הצמתים בעץ.
  • עץ בינארי מנוון הוא עץ בו לכל צומת שאינו עלה יש בן אחד בלבד.‏[1]

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

  • מספר הצמתים n בעץ בינארי מושלם ניתן בנוסחה n=2^{h+1}-1 כאשר h הוא גובה העץ.
  • מספר הצמתים n בעץ בינארי כמעט מושלם הוא בין n=2^h לבין n=2^{h+1}-1 כאשר h הוא גובה העץ.
  • מספר העלים L בעץ בינארי מושלם ניתן בנוסחה L=2^h כאשר h הוא גובה העץ.
  • בעץ בינארי כמעט מושלם, אם מספר הצמתים הוא n אז מספר הצמתים הפנימיים הוא \left\lceil n/2\right\rceil.
  • בכל עץ לא ריק עם n_0 עלים ו-n_2 צמתים עם מדרגה 2 מתקיים n_0 = n_2 + 1.‏ ‏[2]

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ שקפים מקורס תבניות בעיצוב תכנה, אוניברסיטת ת"א.
  2. ^ Mehta, Dinesh; Sartaj Sahni (2004). Handbook of Data Structures and Applications. Chapman and Hall. ISBN 1584884355.