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